[백준(JAVA)] 1138번: 한 줄로 서기

문제

✔ 난이도 - Silver 2

설명1

두 개의 방법이 있음!
1번째 방법은 정석적인 방법이고, 2번째 방법은 반대로 생각한 느낌! 2번이 더 간단하긴 하다!

1번째 방법

n개의 배열 마련해놓고
키 작은사람부터 확인하면서 자기보다 큰 사람의 수만큼 빈 공간 두고 그 다음칸에 넣기.
앞으로 확인할 사람은 나보다 큰 사람이니까 그 사람이 들어갈 공간을 앞에 둬놓는거야.

---

2번째 방법

ArrayList로 중간에 끼어들 수 있게 정답 받음
키 큰 사람부터 확인하면서 자기보다 큰 사람의 수를 index로 하여 ArrayList에 끼워넣기 함.
-> 큰 사람부터 확인하니까 어차피 다음에 나올 사람은 나보다 작은 사람임. 그럼 나보다 큰 사람의 수에 영향을 주는 사람이 이후에 없을거라는 뜻.
-> 따라서 자기보다 큰 사람의 수를 index로 하면 나중에 내 앞에 끼어드는 사람이 있다고 해도 여전히 나보다 큰 사람의 수는 동일함.
(ArrayList 자료구조를 쓴 이유임! 중간에 인덱스가 끼어들어도 그 뒤는 알아서 자연스럽게 뒤로 밀리니까!)

풀이1

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

        int N = Integer.parseInt(br.readLine());
        int[] inputArr = new int[N+1];
        int[] answerArr = new int[N+1];

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

        for (int i = 1; i <= N; i++){
            int tallerNum = inputArr[i];
            int count = 0;
            for (int j = 1; j <= N; j++){
                if (answerArr[j] != 0) continue;
                if (tallerNum == count){
                    answerArr[j] = i;
                }
                count++;
            }
        }

        for (int i = 1; i <= N; i++) {
            sb.append(answerArr[i]).append(" ");
        }

        
        System.out.println(sb);
    }
}

풀이2

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

        int N = Integer.parseInt(br.readLine());
        int[] inputArr = new int[N+1];

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

        ArrayList<Integer> answerList = new ArrayList<>();

        for (int i = N; i >= 1; i--){
            int tallerNum = inputArr[i];
            answerList.add(tallerNum, i);
        }

        for (int i = 0; i < N; i++){
            sb.append(answerList.get(i)).append(" ");
        }
        
        System.out.println(sb);
    }
}

⏰ 시간복잡도

O(N^2)

두번째 방법은 왜 $O(N^2)$ 일까?

• 바깥쪽 루프: $N$번 반복 ($O(N)$)
• answerList.add(index, value) <- 여기도 $O(N)$

ArrayList는 내부적으로 배열을 사용한다.
특정 인덱스에 값을 끼워넣으려면, 그 뒤에 있는 데이터들을 한 칸씩 뒤로 밀어내는 작업이 필요한데, 데이터가 많아질수록 밀어내야 하는 칸수도 늘어나므로 이 작업의 시간 복잡도는 $O(N)$

$N$번의 루프 $\times$ 각 루프당 최대 $O(N)$의 밀어내기 연산 = $O(N^2)$

만약 LinkedList를 썼다면?
LinkedList는 데이터를 밀어낼 필요는 없지만, 해당 인덱스까지 찾아가는 과정이 $O(N)$이라 결과적으로는 똑같이 $O(N^2)$