섹션6. Sort - 6. 장난꾸러기

📌 문제 설명

철수는 새 학기를 맞아 짝꿍보다 키가 크지만 앞 번호를 받기 위해 몰래 자리를 바꿨습니다.
학생들을 키순으로 세우고 앞에서부터 반 번호를 1번부터 부여했을 때 자리 바꾼 두 명(철수와 짝꿍)의 번호를 출력하는 프로그램을 작성하세요.

---

📝 입력 & 출력

입력

• 첫 줄에 자연수 N (5 ≤ N ≤ 100)
• 두 번째 줄에 일렬로 서있는 N명의 키 정보
  (키 값은 120 이상 180 이하의 자연수)

출력

• 자리를 바꾼 학생들의 반 번호를 오름차순으로 출력
  (단, 철수가 짝꿍보다 큼이 문제 조건)

---

🔸 예제 입력 & 출력

예제 입력

9  
120 125 152 130 135 135 143 127 160

 

예제 출력

3 8

💡 해결 방법

• 현재 입력된 순서가 자리 바꾼 상태이고, 정렬된 순서와 비교해서 서로 다른 위치 2개를 찾으면 그 자리가 철수와 짝꿍의 자리입니다.
• 단, 번호는 1부터 시작하므로 인덱스에 +1을 해야 합니다.

---

💻 코드 구현 (Java)

package partSort;

import java.util.*;

public class Problem6 {
	public void solution(int n, int[] arr){
		int[] sortedArr = arr.clone();     // 원본 보존
		Arrays.sort(sortedArr);           // 정렬된 배열 생성

		for(int i=0; i<n; i++) {
			if(arr[i] != sortedArr[i]) {
				System.out.print((i + 1) + " ");
			}
		}
	}

	public static void main(String[] args) {
		Problem6 T = new Problem6();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++) arr[i] = kb.nextInt();
		T.solution(n, arr);
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 원본 복사

int[] sortedArr = arr.clone();
Arrays.sort(sortedArr);

• arr의 원본 순서를 보존하면서 정렬된 배열을 생성

2️⃣ 서로 다른 위치 찾기

for(int i=0; i<n; i++) {
	if(arr[i] != sortedArr[i]) {
		System.out.print((i + 1) + " ");
	}
}

• 원본과 정렬된 배열을 비교해 위치가 다른 두 곳을 출력
• 인덱스는 1부터 출력

---

⏳ 시간 복잡도 분석

• Arrays.sort()는 O(N log N)
• 단일 루프 비교는 O(N)
• 총 시간 복잡도: O(N log N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런