[백준][Java] 1015. 수열 정렬

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

 

 

문제

P[i] : 0 ~ N-1 까지 수를 한 번 씩 포함하고 있는 수열입니다.
B[P[i]] = A[i] 가 되도록 할 때,
배열 A가 주어지고, 수열 B가 비내림차순이 되는 수열이 되도록 만드는 P 수열을 출력해주세요.
만약, 그러한 P 수열이 여러 개라면 사전 순으로 앞서는 것을 출력합니다.

 

비내림차순 : 앞의 원소보다 크거나 같은 경우.

 

 

---

 

정답 코드

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

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[] A = new int[N];
        int[] B = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            B[i] = A[i];
        }

        Arrays.sort(B);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(A[i] == B[j]) {
                    sb.append(j + " ");
                    B[j] = -1;
                    break;
                }
            }
        }

        System.out.println(sb);
    }
}

 

 

풀이 설명

처음 풀이를 했을 때(오답), 모든 경우의 수를 다 따져야 한다고 생각해 BFS로 풀이를 했더니 메모리 초과로 실패하였습니다.

이 문제는 정렬이 들어가 있기 때문에 모든 경우의 수를 따지는 것이 아니라, 경우에 적합한 수를 찾아나가는 것이 맞는 풀이였던 것 같습니다.

 

이후, B배열에 들어가는 수는 A 배열의 값과 같기 때문에 초기에 A배열에 있는 수들로 초기화를 해줍니다.

그리고 B 배열이 비내림차순이 되기 위해 Arrays.sort(B)를 이용해 정렬해줍니다.

이 때, A 배열과 B 배열의 각 값이 같을 때, 그때의 B의 인덱스 값이 P가 될 것입니다. 

 

문제를 잘 이해하고 푼다면, 잘 작성되지만 섣불리 풀었다가 당하는 문제였던 듯 하네요 ;;;