문제
N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.
어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.
사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.
각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.
출력
첫째 줄에 줄을 선 순서대로 키를 출력한다.
접근 방식 - 그리디 알고리즘
키가 1부터 N까지의 사람들 차례대로, 왼쪽 기준으로 자신보다 큰 사람이 몇 명인지 리스트로 받는다.
예제 1번으로 풀이하면 아래와 같다.
4명의 사람들이기 때문에 4개의 빈 자리 리스트를 만든다.
➡[0, 0, 0, 0]첫번째 사람 기준으로 본인보다 큰 사람이 2명이기 때문에 본인 앞에 빈 자리가 2자리 있으면 된다.
➡[0, 0, 1, 0]두번째 사람은 본인보다 큰 사람이 1명이므로, 본인 앞에 빈 자리가 1자리 있으면 된다.
➡[0, 2, 1, 0]세번째 사람은 본인보다 큰 사람이 1명이므로, 본인 앞에 빈 자리가 1자리 있으면 된다.
➡[0, 2, 1, 3]마지막 사람은 본인보다 큰 사람이 없고, 남은 빈 자리에 위치하면 된다.
➡[4, 2, 1, 3]
이러한 풀이를 통해 그리디 알고리즘으로 접근했다.
1. 본인보다 큰 사람의 수 = 빈 자리 수
2. 1번일 때, 해당 자리에 본인의 키를 대입한 후, 반복 종료
코드 구현
N = int(input())
heights = list(map(int, input().split()))
arr = [0 for _ in range(N)] # 사람들의 줄 서는 위치 저장할 리스트
for i in range(N):
taller_num = heights[i] # 왼쪽에 본인보다 큰 사람 몇 명
zero_cnt = 0
for j in range(N):
if arr[j] == 0: # 빈 자리이면, 1을 더해주고
zero_cnt += 1
if taller_num < zero_cnt: # 왼쪽에 본인보다 큰 사람(빈자리)이 cnt 개수보다 커지는 순간
arr[j] = i + 1 # 해당 자리를 본인의 키로 입력
break # 그리고 반복문 중단
시간복잡도
for문이 N번 돌아가고, 중첩 반복문이 있기 때문에 최악의 경우 O(N^2) 연산이 필요하다.
공간복잡도
heights와 arr 리스트 길이가 N이기 때문에 O(N)을 차지한다.
이외의 다른 변수들은 O(1)을 가진다.
즉, 전체 공간복잡도는 O(N)으로 입력 크기 N에 비례하여 증가한다.