자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 장난 꾸러기

 

https://hyejin.tistory.com/1244

자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 중복 확

-> 이전 문제 풀이 

 

 

6. 장난 꾸러기 

설명

새 학기가 시작되었습니다. 철수는 새 짝꿍을 만나 너무 신이 났습니다.

철수네 반에는 N명의 학생들이 있습니다.

선생님은 반 학생들에게 반 번호를 정해 주기 위해 운동장에 반 학생들을 키가 가장 작은 학생부터 일렬로 키순으로 세웠습니다.

 

제일 앞에 가장 작은 학생부터 반 번호를 1번부터 N번까지 부여합니다. 철수는 짝꿍보다 키가 큽니다.

그런데 철수가 앞 번호를 받고 싶어 짝꿍과 자리를 바꿨습니다.

선생님은 이 사실을 모르고 학생들에게 서있는 순서대로 번호를 부여했습니다.

철수와 짝꿍이 자리를 바꾼 반 학생들의 일렬로 서있는 키 정보가 주어질 때 철수가 받은 번호와 철수 짝꿍이 받은 번호를

차례로 출력하는 프로그램을 작성하세요.

 

입력

첫 번째 줄에 자연수 N(5<=N<=100)이 주어진다.

두 번째 줄에 제일 앞에부터 일렬로 서있는 학생들의 키가 주어진다.

키(높이) 값 H는 (120<=H<=180)의 자연수 입니다.

 

출력

첫 번째 줄에 철수의 반 번호와 짝꿍의 반 번호를 차례로 출력합니다.

 

예시 입력 1 

9
120 125 152 130 135 135 143 127 160

 

예시 출력 1

3 8

 

힌트

출력해설 : 키 정보 152가 철수이고, 127이 철수 짝꿍입니다.

 

 

문제 풀이 1

public ArrayList<Integer> solution(int n, int[] arr)
{
   ArrayList<Integer> answer = new ArrayList<>();
   int[] copyArrs = Arrays.copyOf(arr, arr.length);
   Arrays.sort(arr);
   
   for (int i = 0; i < n; i++)
   {
      if (arr[i] != copyArrs[i]) {
         answer.add(i+1);
      }
   }
   
   return answer;
}

 

👩🏻‍💻 : 이 문제를 정렬해서 푸는 방법 말고 처음에는 다른 방법으로 풀어보려고 했는데 키가 같은 학생이 여러명 나오는 예시에서 자꾸 오답이 나와서.. 결국 정렬로 푸는 방법을 찾아서 위에 풀이 방식으로 정답이 나왔다. 

 

먼저 Arrays.copyOf 메서드를 이용해서 arr를 arr.length 만큼 복사를 해서 copyArrs 로 주어진 arr 배열과 똑같은 배열을 만들어주고, 

그 다음 Arrays.sort 메서드를 이용해서 copyArrs 배열을 오름차순으로 정렬해줬다.

 

그다음 for문을 돌면서 copyArrs와 arr이 서로 다른 값이 존재할 때, 거기가 철수가 키가 작은 학생과 자리를 바꾼 것이 되기 때문에 Arraylist에 해당 학생의 i + 1 위치를 add 해줬다. 

 

 

문제 풀이 2

public ArrayList<Integer> solution2(int n, int[] arr) {
   ArrayList<Integer> answer = new ArrayList<>();
   int[] tmp = arr.clone(); // 깊은 복사
   Arrays.sort(tmp);

   for (int i = 0; i < n; i++) {
      if (arr[i] != tmp[i]) {
         answer.add(i + 1);
      }
   }
   return answer;
}

 

👾 : 강사님도 마찬가지로 정렬을 이용해서 푸셨다. 이 문제를 정렬로 풀면 굉장히 빠르고 간단하게 풀 수 있기 때문이다. 

주어진 배열 arr를 깊은 복사 clone() 메서드를 이용해서 tmp 배열을 만들고, 

for문을 이용해서 arr[i] 와 tmp[i]의 값이 다르면 자리를 바꿨다는 것이므로 그 학생들의 i 위치 + 1 을 answer 에 담아줬다. 

i+ 1 을 담는 이유는 배열은 0 부터 시작이지만, 학생들의 위치는 1부터 시작하기 때문이다.