[JAVA 알고리즘]BAEKJOON 1015번 수열 정렬

생각정리/코딩테스트

[JAVA 알고리즘]BAEKJOON 1015번 수열 정렬

생각중임 2023. 12. 21. 22:36

정렬을 이용해서 문제를 해결하는 문제

수열 정렬

문제 설명

P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.

배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

제한사항

없음

입력

첫째 줄에 배열 A의 크기 N이 주어진다. 둘째 줄에는 배열 A의 원소가 0번부터 차례대로 주어진다. N은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 비내림차순으로 만드는 수열 P를 출력한다.

입출력 예

input	return
3 2 3 1	1 2 0
4 2 1 3 1	2 0 3 1
8 4 1 6 1 3 6 1 4	4 0 6 1 3 7 2 5

나의 문제풀이

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

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

        // 입력값으로 배열 생성
        int N = Integer.parseInt(bufferedReader.readLine());
        int[] number = new int[N];
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            number[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
        bufferedReader.close();

        // 입력받은 배열을 복사해 오름차순 정렬
        int[] sequence = number.clone();
        Arrays.sort(sequence);

        // 정렬된 배열을 순서에 매칭 되는 배열의 순서를 answer배열에 입력한다.
        int cnt = 0;
        int[] answer = new int[N];
        // 입력시 입력된 위치를 확인하기 위해 boolean 배열 사용
        boolean[] visited = new boolean[N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (sequence[i] == number[j] && !visited[j]) {
                    visited[j] = true;
                    answer[j] = cnt++;
                    break;
                }
            }
        }

        for (int i : answer) {
            System.out.print(i + " ");
        }
    }
}

N 크기의 배열 생성하고 입력받은 값들을 넣어준다.
입력 받은 배열을 복사한 뒤 오름차순으로 정렬해 준다.
배열의 크기만큼 이중 for문으로 반복한다.
- 오름차순 정렬을 한 배열을 순차적으로 반복해 기존의 배열과 비교한다.
- 입력된 위치에 배열이 사용되었는지 확인한다.
- 위 상태를 충족하면 사용처리를 해주고 해당 위치에 순서를 입력한다.

기본적인 배열들로 순서를 확인을 하고 visited 배열을 이용해서 구분을 주고 사용을 할 수 있도록 구현하였다. 전반적으로 정렬 문제는 어느 시점에 정렬을 사용할지만 해결이 되면 구현에는 따로 까다로운 점이 없는 것 같다.
레벨이 낮은 문제들에서 그럴지도 모르니 따로 정렬 문제에서도 높은 레벨의 문제를 풀어보면서 정렬에 대한 부분을 봐야겠다.