백준 - 한 줄로 서기(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/1138

 

[문제 설명]

[접근 방법]

완전탐색 태그로 본 문제다 보니, 바로 완전탐색밖에 떠오르지 않았다.

저번에 이렇게 아무 생각도 안하고 풀었다가 시간초과로 호되게 당한 적이 있기 때문에 완전탐색의 시간복잡도를 먼저 구했다.

 

N명의 사람들을 줄 세우는 방법은 O(N!), N은 최대 값이 9이므로 9!이 된다. 따라서 362,880이다.

여기서 끝나는 게 아니라 입력 받은 배열들이 세워진 줄과 조건이 일치하는지 확인해야한다.

첫번째 입력 예시로 들면 

2,1,1,0인데  이를 모든 줄과 비교해봐야 한다.

1,2,3,4 -> 2,1,1,0 만족안함

1,2,4,3 -> 2,1,1,0 만족안함

....

..

4,2,1,3 -> 2,1,1,0 만족함

-> 4 2 1 3 출력

이 작업은 n^2의 시간이 든다.

따라서, 이 방법을 사용했을 때 총 시간복잡도는 N!(모든 줄의 경우의 수)xN(줄의 길이)x(비교할 줄의 길이) -> O(N!*N^2)이 된다.

연산 횟수가 3600만으로 대략 통과가 되지만, 너무 생각도 안하고 태그만 보고 푸는 느낌이라 이 방법은 안썼다.

 

두번째 방법은 마지막 숫자부터 세워주는 방법이다.

2,1,1,0의 경우

마지막 숫자의 키는 4이고 앞의 자기보다 큰 수는 0이다.

따라서 0번째 위치에 넣는다.

-> 4

3번째 숫자는 자기보다 큰 수가 1개.

따라서 1번째 위치에 넣는다.

-> 4 3

2번째 숫자는 자기보다 큰 수가 1개다.

따라서 1번째 위치에 넣는다.

-> 4 2 3

1번째 숫자는 자기보다 큰 수가 2개다

따라서 2번째 위치에 넣는다

-> 4 2 1 3

이 방법의 시간복잡도는 N(인원수)xN(리스트에 삽입 연산 시간복잡도) => O(N^2)이 된다.

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numOfPeoples = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] arrayOfIndex = new int[numOfPeoples];
        List<Integer> list = new LinkedList<>();

        int index = 0;
        while (st.hasMoreTokens()) {
            arrayOfIndex[index++] = Integer.parseInt(st.nextToken());
        }

        int height = numOfPeoples;
        for (int i = arrayOfIndex.length - 1; i >= 0; i--) {
            list.add(arrayOfIndex[i], height--);
        }

        list.forEach(it -> System.out.print(it+" "));
    }
}