Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 1138 한줄로 서기
백준 1138 한줄로 서기
문제
N명의 사람들은 매일 아침 한 줄로 선다.
이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.
어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다.
그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.
사람들은 자기보다 큰 사람이 왼쪽에 몇 명이 있는지만을 기억한다.
N명의 사람이 있고 사람들의 키는 1부터 N까지 모두 다르다.
각 사람들이 기억하는 정보가 주어질 때 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.
입력
- 첫 번째 줄: 사람의 수 N
- 두 번째 줄: 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명 있었는지 주어진다.
출력
줄을 선 순서대로 키 출력
해결 방식
- 키가 작은 순으로 줄 세우기
- 원래 자신보다 키가 큰 사람 수 확인
- 자신보다 왼쪽에 선 키 큰 사람 수 확인
- 자신보다 왼쪽에 있는 사람수의 자리가 비어있는 경우 해당 자리 차지
- 비어있지 않은 경우는 자신보다 작은 사람이 있는 경우
- 다음 자리를 찾아서 줄을 선다.
예시
[2, 1, 1, 0]
- 1번째 사람: 왼쪽에 2명 있었다
- 1번보다 큰 사람은 총 3명
- 왼쪽에 2명만 있어야 하므로 3번째 자리
- 0 0 1 0
- 2번째 사람: 왼쪽에 1명 있었다
- 2번보다 큰 사람은 총 2명
- 1명만 왼쪽에 있어야 하므로 2번째 자리
- 0 2 1 0
- 3번째 사람: 왼쪽에 1명 있었다
- 3번보다 큰 사람은 총 1명
- 4번보다 뒤에 존재해야 하므로 맨 뒷자리
- x 2 1 3
- 4번째 사람: 왼쪽에 0명 있었다.
- 4번보다 큰 사람은 0명
- 남은 자리 차지
- 4 2 1 3
코드
n = int(input())
left = list(map(int, input().split()))
sequence = [0 for _ in range(n)]
for i in range(n):
count = 0
for j in range(n):
if sequence[j] == 0 and left[i] == count:
sequence[j] = i + 1
break
elif sequence[j] == 0:
count += 1
print(*sequence, sep=" ")
