정렬-(1)

 

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

10989번: 수 정렬하기 3

수 정렬하기 3에서 제공하는 최대의 값이 10000이기때문에 계수 정렬을 사용하여 문제를 풀기로 하자.

계수정렬이란 입력받은 숫자중 가장 큰 값을 배열의 크기로 설정하고 입력받은 값을 배열의 index로 하여 해당 index에 숫자가 들어올때마다 +1을 넣어주고 0이 아닌 값들을 출력하는 정렬방법이다.

 

1. 메모리초과가 났던 코드

import sys
input = sys.stdin.readline

n=int(input())
list=[]

for i in range(0,n):
    list.append(int(input()))

min_num = min(list)
max_num = max(list)

list2=[0]*(max_num-min_num+1)

for i in range(0,len(list)):
    list2[list[i]-min_num]+=1


for i in range(0,len(list2)):
    if list2[i]!=0:
        for j in range(0,list2[i]):
            sys.stdout.write(str(i+1)+"\n")

list를 하나로 만들기가 필요해보임. => 메모리를 줄이자

2. 성공

import sys

input = sys.stdin.readline

n = int(input())

list2 = [0] * (10000 + 1)

for i in range(0, n):
    list2[int(input())] += 1

for i in range(1, len(list2)):
    for j in range(0, list2[i]):
        sys.stdout.write(str(i) + "\n")

---

8/19 스터디

 

백준  1715번 카드정렬하기 => 우선순위 큐를 활용한 정렬

# 카드 정렬하기

import sys, queue

input = sys.stdin.readline

queue = queue.PriorityQueue()

n = int(input())

for i in range(n):
    queue.put(int(input()))

sum = 0


while True:
    if n == 1:
        break
    x = queue.get() + queue.get()
    sum += x
    if not queue.empty():
        queue.put(x)
    else:
        break

if n == 1:
    sys.stdout.write(str(0))
else:
    sys.stdout.write(str(sum))

<<우선순위 큐 -> queue를 import후 PriorityQueue()를 불러와서 사용할 수 있음>>

 

우선순위 큐 => 들어온 순서와 상관없이 값 자체를 기준으로 정렬되는 큐

 

1. 값을 빼기

queue.get()을 활용해 값을 없애고 얻을 수 있음

 

2. 값을 넣기

queue.put(x) : x는 넣으려는 값을 의미

 

%1715번 주의사항%

시간초과의 이유 => 99%에서 시간초과가 나는 이유는 n=1일때 합칠 필요가 없기때문에 결과가 0이 된되어야하고 n=1일때의 경우를 따로 작성해주지 않는다면 while문에서 두개의 값을 get할 때 빠져나오지 못하는 점이 발생한다.