[백준/Python]11931: 수 정렬하기 4

문제

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

백준 문제집 - 0x0E강 - 정렬 I

 

알고리즘: 정렬

---

풀이

N개의 수가 주어졌을 때, 이를 내림차순으로 정렬하는 프로그램을 작성하시오.

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

사실 수 정렬하기 시리즈는 리스트의 기본 함수인 sort()를 이용하면 굉장히 쉽다.

하지만 그랬다면 문제로 나오지 않았겠지?

 

우선 조건에 맞춰 리스트를 생성해준다.

주어지는 N개의 숫자들은 절댓값이 1,000,000 이하인 정수다.

그럼 숫자의 가능 범위는 -1,000,000 ~ 1,000,000 이 되겠다.

그리고 0 까지 포함하면 가능한 숫자의 갯수는 2,000,001 개가 된다.

 

Python은 리스트 인덱스값으로 음수를 지정할 수 있다.

N개의 원소로 이루어진 리스트가 존재할때, -1은 N번째 원소, -2는 N-1번째 원소 ... 이런식으로 계산된다.

따라서 0과 양의 정수 (0 ~ 1,000,000)는 [0] ~ [1000000] 인덱스, 음의 정수 (-1,000,000 ~ -1)는 [-1000000] ~ [-1] 인덱스, 즉 [1000001] ~ [2000000] 인덱스가 된다.

 

이제 2,000,001개만큼의 리스트를 생성하고, 해당 숫자를 인덱스 삼아 체크해나간다.

수는 중복되지 않는다고 했으니 단순히 True or False 로만 체크해도 된다.

nums = [False] * 2000001

for _ in range(N):
    n = int(input())
    nums[n] = True

 

출력은 내림차순으로 해야한다.

1,000,000 부터 -1,000,000 까지 거꾸로 순회하면서 해당 인덱스의 값이 True라면 출력한다.

# 내림차순으로 출력해야하므로 거꾸로 순회
for i in range(1000000, -1000001, -1):
    if nums[i]:
        print(i)

 

전체 코드

# 메모리: 46744KB / 시간: 1108ms
from sys import stdin


input = stdin.readline

N = int(input())
nums = [False] * 2000001

for _ in range(N):
    n = int(input())
    nums[n] = True

# 내림차순으로 출력해야하므로 거꾸로 순회
for i in range(1000000, -1000001, -1):
    if nums[i]:
        print(i)