[Python] 백준 한 줄로 서기 1138 - 구현 문제

 

1. 문제 

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

1138번: 한 줄로 서기

 

2. 문제 요약

• 자기보다 큰 사람이 왼쪽에 몇 명인지 알 수 있다.
• 줄을 선 순서대로 출력한다.

 

3. 아이디어 정리

키가 작은 학생부터 왼쪽에 나보다 키가 큰 사람 수만큼 자리를 비우고 맞는 순서에 배치한다. 예제 입력을 통해 직접 순서를 구현해보면 아래와 같다.

 

 

4. 문제 풀이

4-1. 내 풀이

"""
단순 구현 - 작은 사람부터 차례대로 채우기
"""
import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
result = [0] * n

# 1. 키 작은 사람부터 결과 넣기
for i, a in enumerate(arr):
    count = 0  # 앞에 키큰 사람 넣은 횟수
    for j, res in enumerate(result):
        # 2. 아직 아무도 안 채워지고, 앞에 키큰 사람으로 더 채워야하는 경우: count 늘리기
        if res == 0 and count < a:
            count += 1
         # 3. 아직 아무도 안 채워지고, count 와 a가 동일한 경우: 현재 학생 넣기
        elif res == 0 and count == a:
            result[j] = i + 1
            break
print(*result)

 

5. 결론

단순 구현 문제이다.