정렬 응용

문제. 

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

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

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

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

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

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

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

 

 

입력 예시

9
120 125 152 130 135 135 143 127 160

 

 

답 : 3 8

public class Main {	
	public ArrayList<Integer> solution(int n, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<>();
		int ck=1; 
		for(int i=0; i<n-1; i++) {
			// 배열의 앞이 뒤보다 클 때 
			if(arr[i]>arr[i+1]) {
				// ck==1이 철수가 앞자리 간 경우, ck==2가 철수짝궁의 자리 
				if(ck==1)answer.add(i+1);
				else answer.add(i+2); 
				ck++; 
			}
		}
		return answer;
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n]; 
		for( int i=0; i<n; i++ ) {
			arr[i] = sc.nextInt();
		}
		for(int x: T.solution(n, arr)) {
			System.out.print(x + " " );
		}
	}
}

 

오답 

만약 173 175 175 175 180 175 이고 철수의 키가 180이고 짝꿍이 175라면 ck는 1번만 일어나게 된다. 

따라서 이는 오답이다. 

 

 

정정 답변

public class Main {	
	public ArrayList<Integer> solution(int n, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<>();
		int[] brr=new int[n];
		brr=arr.clone();
		Arrays.sort(arr);
		for( int i=0; i<n; i++) {
			if(arr[i]!=brr[i]) {
				answer.add(i+1);
			}
		}
		return answer;
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n]; 
		for( int i=0; i<n; i++ ) {
			arr[i] = sc.nextInt();
		}
		for(int x: T.solution(n, arr)) {
			System.out.print(x + " " );
		}
	}
}

 

작은 키와 큰 키가 서로 바뀌었기 때문에 키순대로 정렬을 하면 틀린부분이 2 부분이 생긴다. 

그것이 철수와 철수 짝꿍의 위치이고 인덱스값에서 +1을 해주어야 번호값이 된다. 

 

 

 

 

 

 

 

참고 자료 출처 : https://cote.inflearn.com/contest/10/problem/06-06