[자바] 백준 1083 - 소트 (java)

목차

문제 : boj1083

 

 

필요 알고리즘

• 그리디 알고리즘
  
  • 최선의 방법을 정해 매번 시도하면 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

생각 과정은 다음과 같다.

 

1. N이 50인데 S가 100만?! -> 버블 정렬 생각해보면 결국 N(1+N)/2번 수행되면 어차피 내림차순으로 가능하므로, S가 큰건 의미가 없다. S가 1275 초과일 경우 어차피 의미 없는 값이므로, 100만이라도 문제없음!

if (n*(1+n)/2 < s) {	// 1+2+...+N 번 초과할 경우
    Arrays.sort(arr);	// 그냥 내림차순으로 출력
    printAnswer(n, arr, true);
    return;
}

 

 

2. '1'을 통과한 경우, 사전순으로 가장 뒷서는걸 찾으려면 결국 좌측에 가능한 큰 수가 와야한다. 우선 가장 좌측 숫자만 생각해보자!

5
1 2 3 4 5
3

위의 경우라면 어떻게 될까? S가 3이니 가장 좌측부터 S로 교환 가능한 최대치 부분 중 가장 큰 수는 '4'이다.

따라서 '4'가 가장 좌측으로 오는 것만 생각하면 된다! 즉, '4 1 2 3 5'가 답이 된다.

S가 2이었다면? 3 1 2 4 5

S가 4였다면? 5 1 2 3 4

 

 

3. 가장 좌측 숫자는 '2'로 처리된다. 그럼 그 이후 자리수는 어떨까? 마찬가지다. 가장 좌측 숫자가 S로 교환 가능한 가장 큰 수가 왔는데도 S가 남는다면 그 다음 자리수도 마찬가지 방식으로 가능한 가장 큰 수가 오면 된다.

 

위 케이스에서 S가 7이었다면?

S를 4 써서 5 1 2 3 4 를 만드는건 확정이다. 남은 S는 3이다.

그럼 이제 2번째 자리수도 남은 S로 도달 가능한 가장 큰 값을 가져오면 된다.

즉, 5 4 1 2 3 이 된다.

 

S가 9였다면?

1 2 3 4 5 -> 5 1 2 3 4 -> 5 4 1 2 3 하고도 2가 남는다.

그럼 이제 3번째 자리도 확인한다.

5 4 3 1 2가 될 것이다.

 

 

4. 이걸 코드로 옮길 수 있게 로직을 생각해보면 다음과 같다.

for (int k = 0; k < n && s > 0; k++) {

    int max = arr[k];
    int idx = -1;
    for (int i = k+1; i < n && i <= k+s; i++) {	// k+1부터 k+s 중 k번째 자리보다 큰 값 중 가장 큰 값을 찾는다.
        if (arr[i] > max) {
            max = arr[i];
            idx = i;
        }
    }

    if (idx == -1) continue;	// 큰 값을 못찾았다면 교환하지 않고 k를 증가시킨다.

    s -= idx-k;	// 자리수 차이만큼 s에서 제외한다.
    for (int i = idx; i >= k+1; i--) {	// 남은 s로 도달 가능한 값 중 가장 큰 값을 k로 가져온다.
        int tmp = arr[i];
        arr[i] = arr[i-1];
        arr[i-1] = tmp;
    }
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int s = Integer.parseInt(br.readLine());

        if (n*(1+n)/2 < s) {
            Arrays.sort(arr);
            printAnswer(n, arr, true);
            return;
        }

        for (int k = 0; k < n && s > 0; k++) {

            int max = arr[k];
            int idx = -1;
            for (int i = k+1; i < n && i <= k+s; i++) {
                if (arr[i] > max) {
                    max = arr[i];
                    idx = i;
                }
            }

            if (idx == -1) continue;

            s -= idx-k;
            for (int i = idx; i >= k+1; i--) {
                int tmp = arr[i];
                arr[i] = arr[i-1];
                arr[i-1] = tmp;
            }
        }

        printAnswer(n, arr, false);
    }

    private static void printAnswer(final int n, final int[] arr, final boolean reverse) {
        StringBuilder sb = new StringBuilder();
        if (reverse) {
            for (int i = n - 1; i >= 0; i--)
                sb.append(arr[i]).append(' ');
        } else {
            for (int i = 0; i < n; i++)
                sb.append(arr[i]).append(' ');
        }
        System.out.println(sb);
    }
}