[Baekjoon 8120] Coding of Permutations - JAVA

[Gold III] Coding of Permutations - 8120

문제 링크

성능 요약

메모리: 19844 KB, 시간: 1712 ms

분류

이분 탐색, 자료 구조, 세그먼트 트리

문제 설명

Every permutation A = (a₁, ..., a_n) of numbers 1, ..., n can be coded by a sequence B = (b₁, ..., b_n) in which b_i equals the number of all a_j such that (j < i & a_j > a_i), for i = 1, ..., n.

The sequence B = (0, 0, 1, 0, 2, 0, 4) is the code of the permutation A = (1, 5, 2, 6, 4, 7, 3).

Write a program that:

• reads from the standard input the length n and successive elements of the sequence B,
• examines whether it is a code of some permutation of numbers 1, ..., n,
• if so, it finds that permutation and writes it in the standard output,
• otherwise it writes in the standard output one word NIE ("no").

입력

• In the first line of the standard input there is a positive integer n ≤ 30,000. It is the number of elements of the sequence B.
• In each of the following n lines there is one nonnegative integer not greater than 30,000. It is the successive element of the sequence B.

출력

The standard output should contain:

• in each of n consecutive lines - one element of the permutation A, whose code is the sequence B written in the standard input,
• one word NIE, if the sequence B is not a code of any permutation.

문제 풀이

1. 입력값: N (수열의 길이)
2. 수열: input[1], input[2], ..., input[N]

우선, 주어진 배열 input을 역순으로 정렬하여 input_sorted 배열을 만든다. 이후에 ans 배열에 결과를 저장하면 된다.

• input_sorted[i]는 input 배열을 내림차순으로 정렬한 것이므로, 현재 위치보다 크거나 같은 값의 개수를 의미한다.

그렇다면 다음과 같이 점화식으로 나타낼 수 있다

ans[i] = input_sorted[i] + 1

이 점화식은 ans 배열의 각 위치에 해당하는 값을 계산하는 방법을 나타내며, 각 위치마다 가능한 가장 큰 값을 구해준다.
ans 배열의 값들을 계산하면 정답이 나온다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int N = Integer.parseInt(br.readLine());
        int[] input = new int[30001];
        int[] ans = new int[30001];
        boolean[] check = new boolean[30001];

        for (int i = 1; i <= N; i++) {
            input[i] = Integer.parseInt(br.readLine());
        }

        boolean flag = false;
        for (int i = N; i >= 1; i--) {
            int c = 0, j = N;
            while (!(c == input[i] && !check[j])) {
                if (!check[j])
                    c++;
                j--;
            }
            if (j < 1) {
                flag = true;
                break;
            }
            ans[i] = j;
            check[j] = true;
        }

        if (flag)
            System.out.println("NIE");
        else {
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= N; i++) {
                sb.append(ans[i]).append("\n");
            }
            System.out.print(sb);
        }
    }
}

코드 풀이

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

        int N = Integer.parseInt(br.readLine());
        int[] input = new int[30001];
        int[] ans = new int[30001];
        boolean[] check = new boolean[30001];

• N: 수열의 길이
• input, ans, check: 입력값을 저장하거나 조건을 체크하기 위한 배열

        for (int i = 1; i <= N; i++) {
            input[i] = Integer.parseInt(br.readLine());
        }

• N개의 입력 값을 input 배열에 저장한다
• input[i]에 i번째 입력값이 저장된다.

        boolean flag = false;
        for (int i = N; i >= 1; i--) {
            int c = 0, j = N;
            while (!(c == input[i] && !check[j])) {
                if (!check[j])
                    c++;
                j--;
            }
            if (j < 1) {
                flag = true;
                break;
            }
            ans[i] = j;
            check[j] = true;
        }

• 입력값을 처리하며, ans 배열과 check 배열을 사용하여 조건을 만족하는 값을 계산한다.
• c는 현재까지 사용한 값의 개수, j는 가능한 값 중 가장 큰 값을 찾기 위한 인덱스다.
• while 루프를 사용하여 조건을 만족하는 값을 찾아냅니다. 즉, input[i]가 몇 번째로 큰 값인지를 찾는다.
• flag는 가능한 경우인지 여부를 나타냅니다. j가 1보다 작다면 불가능한 경우로 플래그를 설정하고 루프를 종료한다.
• 그렇지 않으면 ans 배열에 값을 저장하고 해당 값이 사용되었다는 것을 check 배열에 표시한다.

        if (flag)
            System.out.println("NIE");
        else {
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= N; i++) {
                sb.append(ans[i]).append("\n");
            }
            System.out.print(sb);
        }
    }
}

• flag가 true라면 "NIE"를 출력하며, 그렇지 않으면 ans 배열을 사용하여 결과를 출력한다.
• StringBuilder를 사용하여 결과를 빠르게 구성하여 출력한다.