[BOJ] 1138. 한 줄로 서기 (python)

✏️ 문제 (백준 1138. 한 줄로 서기)

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.
어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.
사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.
각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

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

 

🤖 알고리즘

 

#구현 

 

 

🤯 풀이 방법

 

키가 1인 사람부터 주어지기 때문에 어렵지 않은 문제였다.

자리를 저장할 배열을 만들고, 남은 자리의 인덱스값을 저장할 배열을 만든다.

1번의 입력값은 전체 인원에서 1번의 인덱스 자리를 뜻한다. 모든 사람은 1번보다 키가 클 테니까.

정답 배열의 해당 인덱스에 1을 넣고, 자리 배열에서 1번이 들어간 자리를 없앤다.

그다음 2번의 입력값은 남은 자리 중에서 2번이 몇번째에 해당하는지를 뜻한다

이런 식으로 자리 인덱스를 따로 굴리면서 한명씩 자기 자리를 찾아가면 됨

 

 

👾 구현 코드 (파이썬)

# [BOJ] 1138. 한 줄로 서기

import sys
input = sys.stdin.readline

N = int(input())  # 사람의 수
idx = [x for x in range(N)]	# 남은 자리의 인덱스
ans = [0] * N  # 줄서기 완료 저장 배열

people = list(map(int, input().split()))
for i in range(N):
    p = people[i]
    ans[idx[p]] = i + 1  # 남은 자리 중 내가 몇 번째에 위치해야 하는지
    idx.pop(p)

for a in ans:
    print(a, end=" ")

 

1138번: 한 줄로 서기