문제

문제 바로가기

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

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

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

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

입력

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

출력

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

예제 입력

7
6 1 1 1 2 0 0

예제 출력

6 2 3 4 7 5 1

문제 검토

N의 최대 길이가 10밖에 되지 않기 때문에 완전 탐색을 떠올렸다.
반복문을 사용하는데 있어서 주저 없이 사용하면 될 것 같다.

풀이(python)

Python

n = int(input())
s = list(map(int,input().split()))
arr = []

cnt=0

#주어진 배열과 정해진 키로 이루어진 이차원 리스트 초기화
for x in range(0,n): 
    l=[s[x],x+1]
    arr.append(l)
    
#키 순으로 내림참순 정렬
arr=sorted(arr,key=lambda x:x[1],reverse=True) 

#조건 완료할 때까지 무한 반복
while True: 
    check=True #
    for x in range(n):
        cnt=0
        #체킹
        for y in range(x):
            if arr[y][1]>arr[x][1]:
                cnt+=1
        #주어진 값과 체킹한 값이 맞지 않으면 스왑
        if arr[x][0] > cnt:
            arr[x],arr[x+1] = arr[x+1],arr[x]
            check=False
        elif arr[x][0] < cnt:
            arr[x],arr[x-1] = arr[x-1],arr[x]
            check=False
    if check:
        break
    
for x in range(n):
    print(arr[x][1],end=' ')
    
    

n번씩 반복할 때마다 한 인덱스단위로 조건에 부합하는지 체킹하고 부합하지 않는다면 자리를 옮겨 주었다.
리스타가 조건에 부합할 때까지 무한 반복한다.

걸린 시간

33분 53초

총평

구상한 알고리즘대로 구현하다가 코드가 길어져서 불안했는데, 오히려 한번에 성공했다.
여러번 제출하는 것보다 오래걸리더라도 알고리즘을 잘 구상하고 한번에 좋은 코드를 뽑는 것이 더 좋은 방향인 것 같다.

이 문제는 그리디 기법으로 해결한다면 더 좋은 풀이가 나올 수 있다.

빈 인덱스에 숫자를 오름차순으로 조건에 맞게 삽입하는 방식으로 해결한다면 더 좋은 시간복잡도를 얻을 수 있다.