[백준] 💧 1071 소트

📌 난이도

💧 Platinum 5

📌 문제

https://www.acmicpc.net/problem/1071

📌 풀이

코딩 테스트 공부를 하면서 슬슬 여러가지 알고리즘에 대해서 감이 잡히기 시작하고, 골드가 풀리기 시작해서 기념비적인 느낌으로 플레티넘 문제를 도전해보았다.

처음 이 문제를 보자마자 한 생각은 일단 정렬은 해보자라는 생각이였다.
그래서 시간복잡도를 계산해보니 단순하게 Arrays.sort 를 사용해도 o(n^2) = 1억 ≒ 1초라 정렬을 하고 시작했다.

그리고 n개의 숫자가 들어오면 n크기의 배열을 만들어서 작은 순서대로 숫자를 채워넣었다.
이때 다음으로 들어오는 숫자가 이전 값+1이라면 int index라는 변수에 그 주소값을 집어넣은후, 그 다음 위치에 숫자를 집어넣었다.
그리고 index는 기본적으로 final int notExist = 10001 라는 상수를 만들어서 초기화를 해주었는데, 만약 숫자를 넣기 전에 index 값이 notExist가 아니라면 index 이전 주소에 있는 값과 비교해서 이전 주소의 값 + 1 이 아니라면 넣으면서 index 를 notExist 로 초기화해주고, 같을시 뒤에 추가로 넣어주었다.

따라서 다음 그림과 같이 정상적으로 작동하였다.

하지만 이런식의 풀이에는 아직 한가지 반례가 남아있었다.
그 반례는 바로 다음과 같이 index에 값이 채워지지 않은 상태로 종료되는 것이였다.

이를 해결하기 위하여 만약 index != notExist 이면 가장 처음부터 마지막 주소의 숫자 - 1 가 나오는 주소값을 찾아서 index와 빼주고, 그 주소값부터 i까지 마지막 주소의 숫자를 넣어주고, index부터는 그 숫자에 -1를 한값을 끝까지 넣어주었다.
이후 출력은 마지막 주소 - 1 까지 출력하니 답이 나왔다.

플레티넘 문제를 풀고 느낀 점은 생각보다 그렇게 어렵지는 않고, 제대로 알고리즘을 파악한 후 풀면 생각보다 쉽게 풀린다는 것이였다.

처음으로 풀어본 플레티넘 문제여서 행복했다. 😎

📌 Code

package BOJ.Greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class N1071 {
    static int[] input;
    static int[] output;
    static final int notExist = 10001;

    static int N;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        input = new int[N];
        output = new int[N + 1];
        Arrays.fill(output, notExist);
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(input);
        SortDict();
    }

    static void SortDict() {
        int index = notExist;
        int curindex = 0;
        if (N != 0) {
            output[curindex++] = input[0];
        }
        for (int i = 1; i < N; i++) {
            if (index == notExist) {
                if (output[curindex - 1] + 1 != input[i]) {
                    output[curindex] = input[i];
                    curindex++;
                } else {
                    index = curindex++;
                    output[curindex++] = input[i];
                }
            } else {
                if (output[index - 1] + 1 != input[i]) {
                    output[index] = input[i];
                    index = notExist;
                } else {
                    output[curindex++] = input[i];
                }
            }
        }
        if (index != notExist) {
            int flag = index - 1;
            while (flag >= 0 && output[flag] + 1 == output[N]) {
                flag--;
            }
            flag++;

            int count = index - flag;
            for (int i = index + 1; i < N + 1; i++) {
                output[flag++] = output[N];
            }
            for (int i = 0; i < count; i++) {
                output[flag++] = output[N] - 1;
            }
        }
        ShowAll();
    }

    static void ShowAll() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(output[i] + " ");
        }
        System.out.println(sb);
    }

    static void ShowTest() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N + 1; i++) {
            if (output[i] == notExist) {
                sb.append(". ");
            } else {
                sb.append(output[i] + " ");
            }
        }
        System.out.println(sb);
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁