백준1138 - 한 줄로 서기 (그리디) Python

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

문제는 원소의 수와, 차례대로 자기보다 큰 원소가 왼쪽에 몇 개가 존재하는지 주어질 때 

주어진 조건에 맞춰 순서대로 줄을 세워 반환하는 문제다.

 

예시를 설명하면 다음과 같다.

즉, arr = [2,1,1,0] 일 때,
arr[0] == 2 인 경우 => 1보다 큰 수가 앞에 두 개 존재한단 의미
[x,x,1,x]

arr[1] == 1 인 경우 => 2보다 큰 수가 앞에 한 개 존재한단 의미
[x,2,1,x]

arr[2] == 1 인 경우 => 3보다 큰 수가 앞에 한 개 존재한단 의미
[x,2,1,3]

arr[3] == 0 인 경우 => 4보다 큰 수가 앞에 존재하지 않는다는 의미
[4,2,1,3]

 

풀이한 방식은 다음과 같다.

입력값에서 주어진 수만큼의 값은 '빈 자리'로 유지한 채, 작은 수부터 자리를 채워나가면 된다.

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  [N], arr = map(lambda x : list(map(int, x.split())), data)
  # 기본값 0으로 채운 리스트 선언
  result = [0] * N

  for i in range(N) :
    # 다음 들어올 수의 자리를 마련하기 위한 empty 변수
    empty = 0
    for j in range(N) :
      # 뒤에 들어올 수의 자리를 마련하고 and 해당 배열 자리가 비어있다면 재할당
      if empty == arr[i] and result[j] == 0 :
        result[j] = i + 1
        break
      # 자리가 비어있는 경우 empty += 1
      elif result[j] == 0 :
        empty += 1
  print(*result)

solution(input_data)