[구현] 백준 Silver2 1138번 한 줄로 서기 (Python 파이썬)

💡문제 링크

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

 

💡문제 분석 요약

문제

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

일단 입력리스트의 맨 뒤부터 탐색해야겠다고 생각했다.

입력 리스트에는 '나보다 키 큰 사람이 왼쪽에 몇 명 있는지'에 대한 정보가 있으니

키 큰 사람을 먼저 줄 세워야겠다고 판단했다.

💡알고리즘 설계

1. 뒤에서부터 탐색

n = 7
height = [6, 1, 1, 1, 2, 0, 0]

 

키	0(비워두기)	1	2	3	4	5	6	7
자기보다 키 큰 사람이 왼쪽에 몇 명 있는지	0(인덱싱할 때 편하려고 비워두기)	6	1	1	1	2	0	0

맨 처음에는 키가 7이고 자기보다 키가 큰 사람이 왼쪽에 height[7](=0)명 있는 사람을 줄세운다.

그 다음에는 키가 6이고 자기보다 키가 큰 사람이 왼쪽에 height[6](=0)명 있는 사람을 줄세운다.

...

마지막으로 키가 1이고 자기보다 키가 큰 사람이 왼쪽에 height[1](=6)명 있는 사람을 줄세운다.

for k in range(n, 0, -1): 
    target = k # 줄 세울 사람의 키
    info = height[k] # 줄 세울 사람보다 키가 큰 사람의 수

1. 만약 자기보다 키가 큰 사람이 왼쪽에 0명 있다면 이건 '내가 맨 앞에 있다'는 말과 같으므로 리스트의 맨 앞에 넣는다.

if info == 0:
    answer.insert(0, target)

2. 자기보다 키가 큰 사람이 왼쪽에 몇 명 있는지 판단하여 줄을 세우는 반복문을 만든다.

count = 0
for i in range(len(answer)):
    if answer[i] > target: 
        count += 1
    if count == info:
        answer.insert(i+1, target)
        break

결과적으로 answer에는 사람들이 줄 서는 위치 정보가 담기게 된다. 

이거를 마지막에 문자열로 출력해주기만 하면 끝!

print(' '.join([str(a) for a in answer]))

💡코드

n = int(input())
height = [0] + list(map(int, input().split()))
answer = []

for k in range(n, 0, -1): 
    target = k
    info = height[k]
    count = 0
    if info == 0:
        answer.insert(0, target)
    else:
        for i in range(len(answer)):
            if answer[i] > target: 
                count += 1
            if count == info:
                answer.insert(i+1, target)
                break
print(' '.join([str(a) for a in answer]))

 

💡 오답 풀이

...

 

💡 다른 풀이

r=[]
n=int(input())
for q in input().split()[::-1]:
    r.insert(int(q),n)
    n-=1
print(*r)

어나더레벨..

 

💡 느낀점 or 기억할정보

1. 리스트.insert(인덱스, 원소)를 통해 새로운 윈소를 원하는 인덱스 위치에 넣을 수 있다.

2. 딱 30분 걸려서 푼 문제. 매번 '틀렸습니다' 여러 번 뜨고, 코드를 수정하다가 결국 통과되는데, 이번에는 바로 통과되어서 뿌-듯(처음에 틀린 건 그냥 마지막에 출력할 때 띄어쓰기 안 한 사소한 실수)

3.