[알고리즘/구현] 1138번 : 한 줄로 서기 - python

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

1138번: 한 줄로 서기

 

---

• 문제
• 소요시간: 19분 41초

---

• 설계하기(접근방법) 

1. 입력받기

int와 list를 입력받는다

2. 구현하기

 

list가 

[3,2,1,1,0]일 때

list는 키가 1, 2, 3, 4, 5 인 사람들의 정보가 들어있다

그 정보는 각각 사람 앞에 자기보다 키 큰 사람이 몇이나 있는지에 대한 정보다.

 

일단 1인 사람은 모든 사람이 자기보다 크니

해당하는 3 + 1 번째에 넣어주면 된다

 

2인 사람을 생각해보면, 1을 제외한 모든 사람은 자기보다 크다

즉 앞에서부터 한칸씩 검사할 때마다 자기보다 작은 사람을 제외하고는 +1을 하면서

2가 되는 경우 stop을 하고, 만약 리스트에 그 자리가 비어있으면 넣어주면 된다.

 

순서에 중복이 일어나는 경우는 없으니, 그 자리가 차 있는 경우에는 무조건 2보다 작은 수 일것이기 때문에

빈 자리가 나타날 때 까지 한 칸씩 미뤄주면서 검사하면 된다. 그 후 빈 곳에 넣어준다

 

[0,0,0,0,0]인 배열을 선언하고

1번째

[0,0,0,1,0] checker가 3일 때 stop

2번째

[0,0,2,1,0] 즉 checker가 2일 때 stop

3번째

[0,3,2,1,0] checker가 1일 때 stop

4번 째

[0,3,2,1,0] 에서 4의 checker가 1이지만 3과 겹치므로 continue

그리고 2,1 도 continue한 후 빈 자리인 0에 넣어준다

5번째

[5,3,2,1,4] 로 배열이 마무리된다

 

3. 출력하기

리스트를 출력한다

 

---

• 코드(출력)

n = int(input())
height_list = list(map(int, input().split()))
order_list = [0] * 10


# i 는 1부터이다
for i in range(1, n + 1):
    checker = 0
    for j in range(n):
        if order_list[j] != 0:
            continue
        if checker == height_list[i - 1]:
            if order_list[j] == 0:
                order_list[j] = i
                break
            else: continue
        if i > order_list[j] :
            checker += 1

for i in range(n):
    print(order_list[i], end = ' ')

---

• 얻어갈 부분

1. 해법이 보이지 않는 경우 테스트 케이스를 써보면서 규칙성을 찾아보자, 앞에서부터 검사를 하든, 뒤에서 부터 검사를 하든 작은 숫자부터, 큰 숫자부터 등등 clue를 찾자