[구현/백준] 1138번 : 한 줄로 서기

- 문제 : https://www.acmicpc.net/problem/1138

 

문제 이해

- arr로 각 인덱스들 앞에 해당 인덱스 값보다 큰 수가 몇 개 있는지에 대한 정보가 주어진다. 

- 이제 그 순서에 맞춰서 숫자를 나열해야하는데, 방법은 다음과 같다. 

  - 작은 수부터 채워나가면 되는데, 큰 사람이 왼쪽에 몇 명 있어야 하는지 주어진 값만큼의 빈자리를 비워두고 다른 값을 채워나간다. 

- 예시로, 2 1 1 0 으로 주어진 경우에 다음과 같은 과정으로 진행 된다. 

  0번 인덱스(1번) : 0 0 1 0 (왼쪽에 두명이 있으므로 2칸을 비워두고 자리를 채운다)

  1번 인덱스(2번) : 0 2 1 0 (2번은 왼쪽에 자기보다 큰 값이 1개이므로)

  2번 인덱스 (3번) : 0 2 1 3

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

- 주어진 배열 값을 순차적으로 진행하면서, 왼쪽에 0의 값을 센 다음 그 값과 배열 값이 같고, 정답 배열 값도 0이라면 정답 배열에 추가될    수 있다. 이때, 정답 배열에 (해당 인덱스 + 1 값)을 저장하면 된다

 

정답 풀이 

n = int(input())

arr = list(map(int, input().split()))
answer = [0 for _ in range(n)]

for i in range(n):
    count = 0
    for j in range(n):
        if count == arr[i] and answer[j] == 0:
            answer[j] = i + 1
            break
        elif answer[j] == 0 : # count != arr[i]
            count += 1

print(' '.join(map(str, answer)))

 

참고 블로그 : https://gudwns1243.tistory.com/31