[Algorithm] 1138 - 한 줄로 서기

목차

---

1. 문제 설명

2. 접근 방식

3. 코드

4. 시간 복잡도 및 공간 복잡도 계산

 

 

 

 

 

1. 문제 설명

---

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

 

 

 

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. 

입력값으로 키가 1인 사람부터 차례대로 자기보다 큰 사람이 왼쪽에 몇 명 있었는지 주어지면, 실제로 줄을 선 순서대로 키를 출력해주면 된다. 

 

 

 

 

2. 접근 방식

---

예제 입력 1을 기준으로 아래와 같이 해석할 수 있다. 

 

키 1 : 왼쪽에 자기보다 키 큰 사람 2명

키 2 : 왼쪽에 자기보다 키 큰 사람 1명

키 3 : 왼쪽에 자기보다 키 큰 사람 1명

키 4 : 왼쪽에 자기보다 키 큰 사람 0명

 

int[] arr에 [ 2, 1, 1, 0 ] 을 저장한다고 가정할 때

 

✅️ 만약 작은 키 (키 1)부터 줄을 세우기 시작한다면

• 나보다 큰 사람이 왼쪽에 몇 명 있는가를 확인하기 위해 아직 줄에 들어오지 않은 큰 사람들이 어디에 올 지 알아야 한다.
• 작은 키를 먼저 배치하면 앞으로 올 사람들의 배치를 미리 알 수 없어서 조건을 맞추기 어렵다.

 

✅️ 만약 큰 키 (키 4)부터 줄을 세우기 시작한다면 

• 키 = N ) 자신보다 키 큰 사람이 없음 = 조건은 무조건 0명 = 줄 맨 앞에 둬야 한다.
• 키 = N - 1 ) 줄에 이미 서 있는 사람들은 전부 자기보다 큰 사람
  → 키 N - 1 인 사람의 arr 인덱스는 N - 2 (키 1 → 인덱스 0 이니까)
  → arr[N - 2] 위치에 꽂아넣으면 된다.
• 점점 작은 키로 내려갈수록, 이미 줄에 선 사람들은 자신보다 키가 크기 때문에 arr[i]번째 위치에 넣어주면 조건 충족

 

💡💡💡 즉, 큰 키부터 배치하면 arr[i] 값을 줄 서는 인덱스로 해석할 수 있다. 💡💡💡

 

index	[1]	[2]	[3]	[4]
arr[i]	2	1	1	0

 

 

list에 줄을 서는 순서대로 키를 저장하려고 할 때

index 4 ) list[0] = 4가 된다.  (줄 선 순서 : 4)

index 3 ) list[1] = 3이 된다.  (줄 선 순서 : 4 3)

 

index 2일 때 문제가 발생한다. 

arr[2]와 arr[3]이 모두 1로 같기 때문에 list[1] = 2을 넣게 되면 3이 증발 하게 된다. 

따라서 줄 선 순서가 자연스럽게 4 2 3 이 될 수 있도록 list 구현체를 LinkedList로 해주어야한다. 

 

이를 코드로 구현해보겠다.

 

 

 

3. 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

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[] arr = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray(); // 키가 1인 사람부터 자신보다 키 큰 사람이 왼쪽에 몇 명 있는지 저장하는 배열

        List<Integer> list = new LinkedList<>(); // 결과 저장용 리스트
        for(int i = N - 1; i >= 0; i--) {
            list.add(arr[i], i + 1);
        }

        for(Integer i : list) {
            System.out.print(i + " ");
        }
    }
}

 

 

 

 

4. 시간 복잡도 및 공간 복잡도 계산

---

List<Integer> list = new LinkedList<>(); // 결과 저장용 리스트
for(int i = N - 1; i >= 0; i--) {
    list.add(arr[i], i + 1);
}

 

반복문은 N번 연산하지만

LinkedList.add(index, value)는 지정된 index 위치만큼 앞에서부터 순서대로 탐색해야 하므로 O(N)이다. 

따라서 시간 복잡도는 O(N * N)이 된다.

공간 복잡도는 입력 배열 arr와 출력 저장용 list 모두 길이가 N이므로 O(N)이 된다. 

 

문제에서 N은 10보다 작은 자연수라고 주어졌기 때문에 주어진 시간과 메모리 내에서 충분히 실행 가능하다.