[백준] 1138번 한줄로 서기 ! 👨‍👨‍👧‍👦 - Python 문제풀이

<백준 문제풀이>

 

---

해답)

 

import sys


def rl():
    return sys.stdin.readline()


def solution(N, people):
    origin = [0] * N  # 정답 담을 배열
    for height, how_many in enumerate(people):
        position = how_many  # 적어도 암에 있던 사람 수보단 뒤에있다.
        index = 0
        while how_many >= 0:  # 앞에 사람있던 수만큼 확인한다.
            if origin[index] != 0 and origin[index] < height+1:
                position += 1  # 키작은 사람이 있었으면 index늘리고
                how_many += 1  # 한 명 더 확인해본다.
            index += 1
            how_many -= 1
        origin[position] = height + 1

    # 출력
    for person in origin:
        print(person, end=" ")
    return True


N = int(rl())
people = list(map(int, rl().split()))

solution(N, people)

 

풀이)

input 으로 주어지는 자료를 잘 이해하는게 핵심이다.

가령 2 1 1 0 이 들어오면

 

인덱스 :        (1) (2) (3) (4)

더큰사람수 :   2   1   1   0 

 

이고 우리는 1번 앞에는 최소 2 명, 2번 앞에는 최소 1명 .... 임을 알 수 있다!

위치 인덱스의 초기값 = 더큰 사람 수 로 설정할 수 있다.

 

그것을 고려하면서 한명씩 차례대로 자리를 위치시켜준다.

그리고 앞 사람에 키작은 사람이 있었으면 index를 늘려준다.

(예를들어, 3의 앞에 사람으로 1이 있었다면, 더 큰 사람 수에 포함되지 않은 1이 있었던 것이므로 위치 인덱스가 올라간다.)

 

* 이 문제 및 로고의 저작권은 백준에 있습니다.