[그리디] 코딩테스트 문제 TIL (한 줄로 서기) - 백준 1138번

1. 오늘의 학습 키워드

• 구현
• 그리디

---

2. 문제: 1138. 한 줄로 서기

• 단계: 🥈 실버 2단계
• 주제:
  • 구현
  • 그리디 알고리즘
• 출처: https://www.acmicpc.net/problem/1138

문제

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

예제 입력 1 복사

4
2 1 1 0

예제 출력 1 복사

4 2 1 3

예제 입력 2 복사

5
0 0 0 0 0

예제 출력 2 복사

1 2 3 4 5

예제 입력 3 복사

6
5 4 3 2 1 0

예제 출력 3 복사

6 5 4 3 2 1

예제 입력 4 복사

7
6 1 1 1 2 0 0

예제 출력 4 복사

6 2 3 4 7 5 1

---

3. 문제 풀이

Step1. 문제 이해하기

이 문제는 각 사람이 기억하는 “왼쪽에 자신보다 큰 사람이 몇 명 있었는지”라는 조건을 만족하며 줄을 서는 문제입니다.

문제의 핵심은 다음과 같습니다:

• N명의 사람들이 있고, 각 사람의 키는 1부터 N까지 다릅니다.
• 각 사람은 자신의 키와 함께 “왼쪽에 자신보다 큰 사람이 몇 명 있었는지”를 기억합니다.
• 이 정보를 이용해 사람들이 줄을 서야 합니다.

입출력을 살펴보도록 하겠습니다.

• Input:
  • 첫째 줄에 사람의 수 N이 주어집니다. N은 10 이하의 자연수입니다.
  • 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇명이 있었는지 주어집니다.
• Output:
  • 첫째 줄에 줄을 선 순서대로 키를 출력합니다.

Step2. 문제 분석하기

1. 문제의 조건:
   • 각 사람이 기억하는 “왼쪽에 자신보다 큰 사람이 몇 명 있었는지”를 이용해 줄을 서야 합니다.
   • 그렇기 때문에, 키가 작은 사람부터 조건을 만족하며 줄을 세우면, 조건을 위배하지 않고 정렬할 수 있습니다.
2. 핵심 아이디어:
   • 키가 작은 사람부터 조건을 확인하며 빈자리에 배치합니다.
   • 조건이 의미하는 것은 “빈 자리 개수”입니다.
     • 예를 들어, 키가 1인 사람이 “왼쪽에 자신보다 큰 사람이 2명이 있었다”고 기억한다면, 왼쪽에서 빈자리 2개를 지나 세 번째 빈자리에 키가 1인 사람이 배치되야 합니다.
   • 키가 큰 사람부터 배치하면, 뒤에 배치될 사람의 조건이 틀어지기 때문에 키가 작은 사람부터 배치해야 합니다.
3. 어떻게 풀이?:
   • 결과를 담는 배열을 길이 N의 0으로 초기화하여 각 자리에 사람의 키를 배치합니다.
   • 키가 1인 사람부터 시작하여 조건에 맞는 자리를 찾아 삽입합니다.
   • 조건을 확인하며, 빈 자리를 하나씩 세면서 조건에 맞는 자리까지 진행합니다.

Step3. 코드 설계

• 입력 처리:
  • N과 각 사람의 조건을 입력받습니다.
• 결과 배열 초기화:
  • result 배열을 0으로 초기화하여 각 사람의 배치를 저장합니다.
• 키가 작은 사람부터 배치:
  • 1부터 N까지의 키를 반복하면서 각 사람의 조건(conditions)에 따라 빈 자리를 탐색합니다.
  • 빈 자리를 세어 조건에 맞는 위치를 찾으면 해당 위치에 키를 배치합니다.
• 출력 결과:
  • result 배열을 출력합니다.

Step4. 코드 구현

import sys
N = int(sys.stdin.readline().strip())
conditions = list(map(int, sys.stdin.readline().split()))

def sol(N, conditions):
    result = [0] * N
    
    for height in range(1, N + 1): # if N = 4, then height: 1, 2, 3, 4
        cnt = conditions[height - 1] # cnt = 2, 1, 1, 0
        empty_cnt = 0
        for i in range(N):
            if result[i] == 0:
                if empty_cnt == cnt:
                    result[i] = height
                    break
                empty_cnt += 1
    return result
print(*sol(N=N, conditions=conditions))

• 코드 설명:
  • 초기화:
    • result 배열을 0으로 초기화합니다. 각 위치에 사람의 키를 배치합니다.
    • 조건에 따라 빈자리를 탐색하며 배치합니다.
  • 키가 작은 사람부터 탐색:
    • 1부터 N까지 반복하면서 조건을 확인합니다.
    • 조건에 따라 빈 자리를 하나씩 카운트하고, 조건이 만족되는 위치에 현재 키를 배치합니다.
  • 배치 완료:
    • 모든 키가 배치되면 result 배열에 줄 선 순서가 저장됩니다.
• 시간 복잡도: $O(N^2)$
• 결과:

---

4. 마무리

이번 문제는 조건을 만족하며 배열을 구성해야 하는 구현 및 그리디 알고리즘 유형의 문제였습니다.

문제 해결 방법

• 키가 작은 사람부터 순차적으로 배치하며, 주어진 조건(왼쪽에 자신보다 큰 사람이 몇 명 있는지)을 만족하도록 진행했습니다.
• 그리디 알고리즘 방식으로 조건을 만족하는 첫 번째 빈자리에 키를 배치하므로 최적의 결과를 보장합니다.
• break를 사용하여 불필요한 탐색을 방지하고, 성능을 최적화했습니다.

배운 점

1. 문제를 단순화하여 접근하기: 입력 조건을 만족하면서 최적화된 값을 구성하는 문제에서, 작은 단위로 문제를 나누어 해결하는 접근법을 익혔습니다.
2. 반복문과 조건문 활용: 조건에 맞는 위치를 찾기 위해 반복문과 조건문을 적절히 활용하고, 조건을 만족하면 반복문을 종료(break)하여 성능을 개선할 수 있었습니다.
3. 구현 과정에서의 효율성: 입력 조건에 의해 한 번만 배치되더라도, 불필요한 탐색을 줄이는 방법(break)을 통해 효율성을 고려한 구현을 익혔습니다.

시간 복잡도

• 키의 순서에 따라 N명의 사람을 반복하면서, 각 사람이 적절한 위치를 찾기 위해 최대 N번 탐색합니다.
• 따라서 전체 시간 복잡도는 $O(N^2)$입니다.
• 문제에서 N의 최대값이 10이므로, 해당 시간 복잡도는 충분히 효율적입니다.

이번 문제는 조건에 맞는 위치를 효율적으로 배치하는 연습과 함께, 코드의 효율성을 고려한 설계 방법을 배울 수 있는 좋은 사례였습니다. 앞으로도 조건 처리와 반복문 최적화에 집중해 다양한 문제를 해결해보도록 하겠습니다.

글 읽어주셔서 감사합니다.

매일매일 발전합시다!!