[백준] 한 줄로 서기 (그리디)

문제 소개

한 줄로 서기 - 백준 1138번 문제를 정리합니다.
이 문제는 각 사람마다 왼쪽에 자신보다 키 큰 사람이 몇 명 있었는지만 기억할 때, 전체 줄 서기 순서를 구하는 문제입니다.

문제 링크: 한 줄로 서기 - 백준 1138번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 사람들의 키는 1부터 N까지 정수이며, 입력 순서는 키 1부터 N까지 오름차순 기준
2. 키가 큰 사람부터 거꾸로 순회하며 줄을 세움 → 작은 사람보다 큰 사람이 먼저 줄에 들어가 있어야 삽입 위치가 정확히 계산됨
3. LinkedList를 사용해 원하는 위치에 빠르게 삽입
4. 각 사람은 본인이 기억하는 큰 사람 수만큼 왼쪽에 사람을 두고 해당 위치에 삽입

---

해결 과정 및 코드

핵심 아이디어

1. 입력의 i번째 값은 키가 i+1인 사람이 왼쪽에 있어야 할 키 큰 사람 수
2. 키 큰 사람부터 거꾸로 처리하면 이미 리스트에 있는 사람들은 항상 자신보다 크거나 같기 때문에,
   해당 위치에 삽입하는 것만으로 조건을 만족
3. 예를 들어 heights\[i]가 2라면 → 현재 줄에서 인덱스 2에 삽입
   → 앞에 있는 두 사람은 자신보다 큰 사람
4. 리스트 크기보다 큰 위치에 삽입하려는 경우에는 그냥 맨 뒤에 추가하면 됨

코드

시간 복잡도 : O(N²)

• 이유: LinkedList의 중간 삽입이 최악의 경우 O(N)이고, N명 반복

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = read();
        int[] heights = new int[N];
        List<Integer> orders = new LinkedList<>();

        // 키가 1부터 N까지인 사람의 '왼쪽에 몇 명의 큰 사람이 있었는지' 입력
        for (int i = 0; i < N; i++) {
            heights[i] = read();
        }

        // 키가 큰 사람부터 거꾸로 줄 세우기
        for (int i = N - 1; i >= 0; i--) {
            int person = i + 1;  // 키가 i+1
            int pos = heights[i]; // 왼쪽에 있어야 할 큰 사람 수
            if (pos >= orders.size()) {
                orders.add(person);  // 맨 뒤에 삽입
            } else {
                orders.add(pos, person);  // 지정된 위치에 삽입
            }
        }

        // 최종 줄 출력
        for (int n : orders) {
            bw.append(Integer.toString(n)).append(" ");
        }
        bw.flush();
    }

    // 빠른 입력 함수
    public static int read() throws IOException {
        int cur, n = System.in.read() & 15;
        boolean isNegative = (n == 13);
        if (isNegative) n = System.in.read() & 15;
        while((cur = System.in.read()) > 32) {
            n = (n << 3) + (n << 1) + (cur & 15);
        }
        return isNegative ? -n : n;
    }
}

참고

• 입력값을 역순으로 처리하는 이유
  작은 키부터 넣으면, 그 사람이 기억하는 "왼쪽의 큰 사람 수"가 아직 줄에 없는 사람 기준이라 정확한 계산이 어려움.
  그래서 큰 사람부터 미리 줄을 세워 두면, 삽입 위치만으로 정답이 완성됨
• LinkedList.add(index, value)
  중간 위치 삽입이 필요한 문제에서는 ArrayList보다 LinkedList가 효율적 (최악 시간은 같지만 실제 성능에서 차이 존재)