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

문제 소개

한 줄로 서기 - 백준 1138번 문제를 Kotlin으로 정리합니다.
이 문제는 각 사람이 기억하는 "왼쪽에 있는 자신보다 큰 사람 수"를 기반으로 줄을 재구성하는 구현 문제입니다.

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

---

문제 접근 방식

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

1. 사람들은 키가 1부터 N까지 모두 다르고 중복 없음
2. 각 사람은 자신보다 키 큰 사람이 왼쪽에 몇 명 있었는지를 기억
3. 입력은 키가 1인 사람부터 N인 사람까지의 기억 순서
4. 키가 큰 사람부터 차례대로 줄에 삽입하면, 조건을 정확히 만족하는 줄을 만들 수 있음
5. 삽입에는 LinkedList를 사용해 중간 위치에 삽입을 쉽게 처리

---

해결 과정 및 코드

핵심 아이디어

1. 키가 큰 사람부터 줄에 세움 → 이미 배치된 사람들은 자신보다 크거나 같으므로
   본인이 기억하는 숫자(input[i]) 만큼 앞으로 몇 명을 건너뛰고 삽입하면 됨
2. Kotlin에서는 LinkedList.add(index, value)를 사용해 중간 삽입을 직접 처리
3. 마지막에 joinToString(" ")으로 리스트를 출력 형태에 맞게 변환

코드

시간 복잡도 : O(N²)

import java.util.LinkedList

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val input = readLine().split(" ").map { it.toInt() }
    val result = LinkedList<Int>()

    for (i in n - 1 downTo 0)
        result.add(input[i], i + 1)

    println(result.joinToString(" "))
}

참고

java 버전과 접근은 동일합니다. 단, 서술을 더 풀어 정리했습니다.

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