[BOJ-1083] 소트 - Java

문제 링크

오랜만에 코테 문제를 풀어서 감도 익힐겸 비교적 쉬워 보였던(?) 문제를 가져왔다.

---

✍ 문제 설명

---

📝 문제 풀이

처음 문제를 보고 풀었을 때는 단순 버블 소트구나 생각이 들어 배열의 앞뒤 값만 바꾸어서 풀었다. 그런데 웬걸 테스트 통과가 되지 않는 것이었다. 그래서 반례를 생각해보니 교환 횟수를 간과하고 풀고 있었다는 것을 깨달았다.

예를 들어, 10개의 숫자에 17번의 교환 횟수가 있는 입력값이 들어왔다고 생각해보자.

input : 10
		1 2 3 4 5 6 7 8 9 10
		17

이런 입력값이 들어왔을 때, 출력값은 아래와 같이 나와야 한다.

output : 10 9 1 2 3 4 5 6 7 8

위 반례를 토대로 내가 푼 방식은 아래 설명과 같다.

• 숫자가 담긴 list에서 교환 횟수로 도달할 수 있는 범위를 파악
• 파악한 범위에서 최댓값(max)과 최댓값의 인덱스(maxIdx)를 따로 저장
• 그 값을 list에서 제거한 뒤 앞으로 가져옴
• 미리 저장해둔 maxIdx와 현재 index를 이용해 교환횟수를 차감

말로 설명하려니까 조금 난잡한 것 같다 ㅠㅠ. 아래 코드를 보면 조금 더 이해가 빠를 것이다.

---

✅ 정답 코드

- 코드 설명

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
		// 숫자 개수
		int N = Integer.parseInt(br.readLine());
		ArrayList<Integer> list = new ArrayList<>();

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}
        
		// 교환 횟수
		int S = Integer.parseInt(br.readLine());

		// 1. 교환 횟수가 남아있고 i가 N보다 작다면
        // (원래는 if(S <= 0) break; 라는 로직이었지만 for문 조건에 합쳤다.)
		for (int i = 0; i < N && 0 < S; i++) {
			int max = 0, maxIdx = 0;
			
            // 2. 현재 index(i)로부터 교환 횟수가 남아있고 j가 N보다 작다면
			for (int j = i; j < N && j <= S + i; j++) {
				if(max <= list.get(j)) {
                	// 3. 해당 범위에서 최댓값 추출
					max = list.get(j);
					maxIdx = j;
				}
			}				
			
            // 4. 해당 위치 최댓값을 현재 위치에 할당
			list.remove(maxIdx);
			list.add(i, max);
            
            // 5. 최댓값 index에서 현재 index의 차는 곧 값이 이동한 횟수이므로
            // 교환 횟수를 이동한 횟수만큼 차감
			S -= (maxIdx - i);
		}

		// 값 출력
		StringBuilder sb = new StringBuilder();
		for (int num : list) {
			sb.append(num).append(" ");
		}

		System.out.println(sb.toString());
	}
}

- 순수 코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		ArrayList<Integer> list = new ArrayList<>();

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}

		int S = Integer.parseInt(br.readLine());

		for (int i = 0; i < N && 0 < S; i++) {
			int max = 0, maxIdx = 0;
			
			for (int j = i; j < N && j <= S + i; j++) {
				if(max <= list.get(j)) {
					max = list.get(j);
					maxIdx = j;
				}
			}				
			
			list.remove(maxIdx);
			list.add(i, max);
			S -= (maxIdx - i);
		}

		StringBuilder sb = new StringBuilder();
		for (int num : list) {
			sb.append(num).append(" ");
		}

		System.out.println(sb.toString());
	}
}

---

🎈 후기

빨리 풀 수 있을 줄 알았는데, 의외로 시간이 좀 걸렸다 ㅋㅋ. 알고리즘은 역시 꾸준히 공부해야 안까먹나보다.