백준 1138번 한 줄로 서기 Python

백준 1138번 한 줄로 서기 Python

문제

문제

N명의 사람이 있습니다.
사람들의 키는 1부터 N까지 모두 다릅니다.
즉, 키 1, 키 2, 키 3 … 키 N 형태로 번호가 부여된 셈입니다.

모든 사람은 자신보다 키가 큰 사람이 왼쪽에 몇 명 있었는지를 기억합니다.
이 정보가 입력으로 주어지며,
입력의 순서는 “키가 작은 사람부터”입니다.

즉, 입력의 첫 번째 수는 키 1인 사람의 기억,
두 번째 수는 키 2인 사람의 기억,
마지막 수는 키 N인 사람의 기억입니다.

이 정보를 바탕으로,
줄의 실제 순서를 복원해야 합니다.

테스트케이스

예제 입력 1

4
2 1 1 0

예제 출력 1

4 2 1 3

예제 입력 2

5
0 0 0 0 0

예제 출력 2

1 2 3 4 5

예제 입력 3

6
5 4 3 2 1 0

예제 출력 3

6 5 4 3 2 1

예제 입력 4

7
6 1 1 1 2 0 0

예제 출력 4

6 2 3 4 7 5 1

---

문제 아이디어

---

(1) 문제 풀이 논리

이 문제는 각 사람이 기억하는 정보를 이용해 줄의 순서를 복원하는 문제입니다.
각 사람은 자기보다 키가 큰 사람이 왼쪽에 몇 명 있었는가만 기억하고 있습니다.
즉, 줄의 왼쪽부터 보았을 때, 자신보다 큰 사람의 수가 정확히 주어진 값과 일치해야 합니다.

사람들의 키는 모두 1부터 N까지 다릅니다.
따라서 가장 키가 큰 사람은 왼쪽에 자기보다 큰 사람이 없으며,
가장 키가 작은 사람은 왼쪽에 자기보다 큰 사람이 모두 존재해야 합니다.

이 규칙에 따라, 우리는 큰 사람부터 차례대로 줄을 채워 나가면
각 사람의 “왼쪽의 큰 사람 수” 조건을 빈칸 기준으로 정확히 맞출 수 있습니다.

(2) “자기보다 큰 값이 주어진 숫자만큼 있어야 한다”의 의미

예를 들어 “자기보다 큰 값이 6개 있다”는 말은,
왼쪽에서 자신보다 큰 사람 6명이 이미 서 있어야 한다는 뜻입니다.
하지만 줄이 비어 있다면,
아직 아무도 없기 때문에 실제로는 “왼쪽에서 6개의 빈자리를 건너뛰고 그다음 자리에 서면”
결국 자기보다 큰 사람 6명이 왼쪽에 있는 것과 같은 결과가 됩니다.

즉,

‘왼쪽에 큰 사람이 6명 있다’ = ‘왼쪽의 빈칸을 6개 비워두고 그다음 칸에 선다’

이것이 바로 빈칸을 세는 논리입니다.
이 논리를 그대로 적용해 한 사람씩 자리를 찾아갑니다.

(3) 실제 줄 형성 과정

입력

7
6 1 1 1 2 0 0

초기 상태

_ _ _ _ _ _ _

(빈칸은 아무도 서지 않은 자리입니다.)

---

① 키 1 — “왼쪽에 자신보다 큰 사람이 6명 있다”

이 사람은 전체 중에서 가장 키가 작습니다.
자기보다 큰 사람은 2, 3, 4, 5, 6, 7의 6명입니다.
따라서 왼쪽에서 6개의 자리를 비워두고 그다음 칸에 서야 합니다.

이제 왼쪽에서 빈칸을 하나씩 세기 시작합니다.
빈칸을 셀 때마다 카운터(cnt)가 하나씩 증가합니다.

---

첫 번째 빈칸을 셉니다.

_ _ _ _ _ _ _
↑

현재 카운트(cnt) = 1
아직 조건 “6개의 빈칸을 비워야 함”을 만족하지 못했습니다.

두 번째 빈칸을 셉니다.

_ _ _ _ _ _ _
  ↑

현재 cnt = 2
아직도 조건에 미달입니다.

세 번째 빈칸을 셉니다.

_ _ _ _ _ _ _
    ↑

현재 cnt = 3
조건 6보다 작습니다.

네 번째 빈칸을 셉니다.

_ _ _ _ _ _ _
      ↑

현재 cnt = 4
아직 조건 미달입니다.

다섯 번째 빈칸을 셉니다.

_ _ _ _ _ _ _
        ↑

현재 cnt = 5
아직 조건에 도달하지 않았습니다.

여섯 번째 빈칸을 셉니다.

_ _ _ _ _ _ _
          ↑

현재 cnt = 6
이제 주어진 조건과 일치합니다.
다음 칸이 바로 자신의 자리입니다.

일곱 번째 칸에 자신을 배치합니다.

_ _ _ _ _ _ 1

(키 1은 자기보다 큰 사람 6명이 왼쪽에 있도록 서게 되었습니다.)

② 키 2 — “왼쪽에 자신보다 큰 사람이 1명 있다”

현재 줄 상태

_ _ _ _ _ _ 1

이제 키 2의 사람은 왼쪽에서 빈칸 1개를 비우고 그다음 칸에 서야 합니다.

첫 번째 빈칸을 셉니다.

_ _ _ _ _ _ 1
↑

현재 cnt = 1
조건(왼쪽 큰 사람 1명)에 도달했습니다.
다음 칸이 바로 자신의 자리입니다.

두 번째 칸에 자신을 배치합니다.

_ 2 _ _ _ _ 1

③ 키 3 — “왼쪽에 자신보다 큰 사람이 1명 있다”

현재 줄 상태

_ 2 _ _ _ _ 1

첫 번째 빈칸을 셉니다.

_ 2 _ _ _ _ 1
↑

현재 cnt = 1
조건 충족 → 다음 칸이 자리입니다.

세 번째 칸에 자신을 배치합니다.

_ 2 3 _ _ _ 1

④ 키 4 — “왼쪽에 자신보다 큰 사람이 1명 있다”

현재 줄 상태

_ 2 3 _ _ _ 1

첫 번째 빈칸을 셉니다.

_ 2 3 _ _ _ 1
↑

현재 cnt = 1
조건 도달 → 다음 칸이 자신의 자리입니다.

네 번째 칸에 자신을 배치합니다.

_ 2 3 4 _ _ 1

⑤ 키 5 — “왼쪽에 자신보다 큰 사람이 2명 있다”

현재 줄 상태

_ 2 3 4 _ _ 1

첫 번째 빈칸을 셉니다.

_ 2 3 4 _ _ 1
↑

현재 cnt = 1

두 번째 빈칸을 셉니다.

_ 2 3 4 _ _ 1
      ↑

현재 cnt = 2
조건 충족 → 다음 칸이 자신의 자리입니다.

다섯 번째 칸에 자신을 배치합니다.

_ 2 3 4 5 _ 1

⑥ 키 6 — “왼쪽에 자신보다 큰 사람이 0명 있다”

현재 줄 상태

_ 2 3 4 5 _ 1

첫 번째 칸 바로 자리에 서야 합니다.

조건이 0이므로 첫 번째 자리 자체가 곧 자신의 자리입니다.

6 2 3 4 5 _ 1

⑦ 키 7 — “왼쪽에 자신보다 큰 사람이 0명 있다”

현재 줄 상태

6 2 3 4 5 _ 1

첫 번째 칸부터 빈칸을 확인합니다.

1번째 칸은 이미 찼습니다.
2번째 칸도 찼습니다.
3번째 칸도 찼습니다.
4번째 칸도 찼습니다.
5번째 칸도 찼습니다.
6번째 칸이 비어 있습니다.
조건(0명)을 만족했으므로 여기에 섭니다.

6 2 3 4 7 5 1

---

(결과)

최종 줄 상태는 다음과 같습니다.

6 2 3 4 7 5 1

이 줄은 모든 사람의 “왼쪽에 자신보다 큰 사람 수” 조건을 정확히 만족합니다.

---

전체 코드

N=int(input())
arr=list(map(int,input().split()))
ans=[11 for _ in range(N)]

for i in range(N):
    cnt=0
    for j in range(N):
        if ans[j]==11:
            if arr[i]==cnt:
                ans[j]=i+1
                break
            else:
                cnt+=1

for i in range(N):
    print(ans[i],end=' ')

---

결론

이 문제는 단순한 정렬 문제가 아니라,
왼쪽의 큰 사람 수를 기준으로 줄 전체를 복원하는 논리형 문제입니다.

핵심은 큰 사람부터 차례로 배치하며,
왼쪽의 빈자리 수를 arr[i]와 비교해 정확히 맞을 때 그 자리에 배치한다는 아이디어입니다.

이 방식은 각 사람의 조건을 하나씩 만족시키며,
줄 전체를 완성할 수 있는 유일하고 결정적인 접근입니다.

결국, 입력 2 1 1 0에서
최종 줄은 4 2 1 3이 되며,
이는 모든 사람의 기억(왼쪽의 큰 사람 수)을 완벽히 만족하는 결과입니다.