[백준/Python]15688: 수 정렬하기 5

문제

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

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

 

알고리즘: 정렬

---

풀이

N개의 수가 주어졌을 때, 이를 비내림차순으로 정렬하는 프로그램을 작성하시오.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.


첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이며, 같은 수가 여러 번 중복될 수도 있다.

 

비내림차순 = 오름차순으로 생각하면 된다.

11931: 수 정렬하기 4와 비슷하지만 이번엔 중복되는 경우를 염두해둬야 한다.

따라서 2,000,001 크기의 리스트를 생성하되, boolean 값이 아닌 0 으로 초기화해야한다.

nums = [0] * 2000001

 

그리고 입력값을 한줄씩 받아오면서 해당 인덱스의 값에 1씩 더해준다.

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

 

오름차순 출력이므로 -1,000,000 부터 1,000,001 까지 순회한다.

만약 nums[i] 값이 0이 아니라면 들어있는 값 만큼 i 를 출력한다.

for i in range(-1000000, 1000001):
    if nums[i] != 0:
        for j in range(nums[i]):
            print(i)

 

전체 코드

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


input = stdin.readline

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

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

for i in range(-1000000, 1000001):
    if nums[i] != 0:
        for j in range(nums[i]):
            print(i)

 

근데 이 문제... sort() 로도 통과된다.

다른 풀이들을 보니 sort()로도 되더라;;

sort로 통과되는 기준이 뭔진 모르겠지만 하여튼간에 수 정렬 5는 sort로 가능하다!

# 메모리: 87720KB / 시간: 16116ms
from sys import stdin


input = stdin.readline

N = int(input())
nums = [int(input()) for _ in range(N)]
nums.sort()

print(*nums)

 

물론 메모리는 곱절로 차이난다.