[백준] 1138 - 한 줄로 서기

문제

백준 1138번 한 줄로 서기

 

 

문제 풀이

이 문제는 왼쪽에 자신보다 큰 사람이 몇 명이 있었는지만을 기억하는 사람들의 리스트가 주어졌을 때의 열의 순서를 출력하는 문제이다. 키가 큰 사람의 수만 존재하며, 키에 대한 오름차순으로 배열이 주어졌으므로 이전 인덱스의 사람의 순서는 현재보다 반드시 작기 때문에 고려할 필요가 없다. 배열의 각 값은 현재 위치가 정해지지 않은 자리(visited 배열에 False로 된) 배열의 인덱스이다. 

예를 들어, 6명이 존재하고 visited이 [False, True, True, False, False, False] 일 때, 키가 3인 사람의 값이 1이라면, 4번째 자리에 사람 3이 위치하여야 한다.

앞에 몇 명이 올지 알 수 없는데 값이 3이라고 해서 5번째나 6번째가 아닌 4번째라고 확신할 수 있는 이유는, 키에 대해 오름차순으로 확인했기 때문에 이후에 3보다 작은 키를 가진 사람이 나올 리가 없다. 따라서 가장 왼쪽의 위치를 선택하여야 하는 것이다. 

이러한 방식으로 전개하면 그리디 알고리즘으로 문제를 해결하는 것이 된다.

 

 

코드

# 그리디
n=int(input())

lst=list(map(int,input().split(' ')))

visited=[False]*n
ans=[0 for _ in range(n)]

for i in range(n):
  idx=0
  unvisited=-1
  for j in range(n):
    if not visited[j]:
      unvisited+=1
    if lst[i]==unvisited:
      idx=j
      break
  visited[idx]=True
  ans[idx]=i+1

print(*ans)