[BoJ] - 1015번 수열 정렬

백준 링크 : https://www.acmicpc.net/problem/1015

 

 

문제 설명 

 

처음 문제를 읽어보았을때 정말 이해하기가 어려워서 10번이상을 똑같은 문장을 반복해서 봤다 이해가 안되었문장은 이거였다 

 

B[P[i]] = A[i] 이다. 배열 A가 주어졌을떄 수열 P를 적용한 결과 비 내림차순이 되는 수열을 찾는 프로그램을 작성하세요

 

B[P[i]] = A[i] 이게 도대체 무슨 의미인가 고민을 했고 이해하기 어려워 질문 게시판을 확인해보았을때 정확히 뭘 요구하는지 이해할수 있었다.

 

즉 문제가 요구하는 건 "주어진 수열을 정렬시키는 수열 " 이다. 즉 B[P[i]] = A[i] 를 그대로 해석하면 오름차순이 된 B배열의 P[i]는 인덱스 값이다 

 

예를 들면 

 

A : 2 3 1 

B : 1 2 3 

B[1] = A[0]

B[2] = A[1]

B[0] = A[2]

 

그렇 다면 P는 1 2 0 이다 

 

이걸 생각하느라 시간이 많이 걸렸고 코드로 구현하는건 그렇게 어렵지 않았다. 

 

나의 풀이는 아래와 같다 

1. 배열 a 와 a를 오름차순 정렬한 b 배열을 생성 

2. A를 for 문 돌면서 B배열의 같은수의 인덱스를 반환 

3. 만약 B배열의 A값을 찾으면 MAX_VALUE 로 변경하여 사용된 값이라는걸 표시 (N은 50보다 작은 조건을 확인)

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

public class Main {

    private static BufferedReader br;
    private static int[] a;
    private static int[] b;
    private static StringBuffer answer;
    public static void main(String[] args) throws IOException{
        br = new BufferedReader(new InputStreamReader(System.in));
        answer = new StringBuffer();
        Integer N = Integer.parseInt(br.readLine());
        String tc = br.readLine();
        StringTokenizer st = new StringTokenizer (tc , " ");
        a = new int[N];
        b = new int[N];
        
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            a[i] = num;
            b[i] = num;
        }
        Arrays.sort(b);

        for (int i = 0; i < N; i++) {
            answer.append(searchA(a[i])).append(' ');
        }
        

        System.out.println(answer.toString());
    }

    public static int searchA(int ANum) {
        int index = 0;
        for (int i = 0; i < b.length; i++) {
            if(b[i] == ANum){
                b[i] = Integer.MAX_VALUE;
                index = i;
                break;
            }
            
        }
        return index;
    } 

}

 

배열을 계속적으로 처음부터 탐색을 해야하는게 시간 복잡도를 많이 잡아 먹을것 같은데 시간 제한이 2초다 보니 통과가 된것 같다. 

시간 복잡도를 줄이는 방법이 있다면 찾아서 적용하는것도 좋은 리뷰가 될것 같다