Greedy(17)_한줄로서기(1138)

작성일 | In

BJO 1138 한 줄로 서기

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

N은 10보다 작거나 같은 자연수 둘 째 줄에는 키가 1인 사람부터 차례대로 자기보다 키 큰 사람이 왼쪽에 몇 명 있었는지 주어진다,

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

단순히 떠오르는 생각

키가 1인 사람의 수는 우선 바로 알 수 잇다. 숫자는 차례대로 키가 1인 사람부터 차례대로 왼쪽에 몇 명 있었는지 주어진다. 2 1 1 0 키가 1인 사람, 즉 예제를 살펴보면 인덱스가 2인 곳에 위치한다. 가장 작은 수이기 때문에, 왼쪽에 있는 수들은모두 자신보다 큰 수다.

참고한 블로그를 살펴보니 이해가 갔다.

  • 키큰 사람 순으로 처리해보자.
  • 현재 리스트에 나보다 큰 사람만 있고, 나의 왼쪽에 나보다 큰 사람이 i명 있으면, 나는 i번째에 들어가면 된다.

코드

N = int(input())
H = list(map(int, input().split()))
arr = []
for i in range(N-1, -1, -1):  # 큰 수부터 리스트에 넣는다.
    arr.insert(H[i], i+1)  # 큰 수의 위치는
for elem in arr:
    print(elem, end=" ")

느낀점

알고보면 정말 간단한 문제일 줄 알았지만, 정말 간단한 문제다. insert를 활용할 생각을 했다면 조금 더 쉬웠을 것 같다.

참고자료 [참고블로그]https://blog.encrypted.gg/452

0%