[정렬/브루트포스] 백준 1015 수열 정렬 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1015번: 수열 정렬

 

 

 

2. 문제 풀이

 길이가 N인 수열이 주어집니다. 수열 내에서의 대소관계를 파악해서, 작은 수부터 0 ~ N-1까지 순위를 매깁니다.

 

입력: 2 3 1

=> 제일 작은 수 1은 '0'번
=> 두번째로 작은 수 2는 '1'번
=> 제일 큰 수 3은 '2'번으로 순위가 매겨집니다.

출력: 1 2 0

 만약 같은 숫자가 있다면, 왼쪽에 있는 숫자가 순위가 낮습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
numlist = list(map(int, input().split()))

# 대소관계 파악
cnt = 0
for num in range(1, 1001):
    for i in range(N):
        if numlist[i] == num:
            numlist[i] = str(cnt)
            cnt += 1

        if cnt == N:
            # 출력
            print(" ".join(numlist))
            exit()

 해시맵을 이용하거나 따로 리스트에 순위값을 저장할 수도 있겠으나, 저는 단순하게 '브루트포스' 방식으로 완전 탐색했습니다. 배열의 원소가 1~1000 사이이고, 원소의 개수가 50개 이하이므로 가능한 방식입니다.

 숫자를 1부터 1000까지 1씩 늘려가며, 리스트에 같은 원소가 있는지 판별합니다. 같으면, 순위를 매기고 순위를 +1합니다. 만약 순위가 N에 도달했으면, 대소관계 파악이 끝난 것이므로 종료합니다.