백준 온라인 저지 10989번 ‘수 정렬하기 3’
파이썬 알고리즘 문제풀이
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
소스코드
실패 소스 1 - 메모리 초과
입력을 받아 sorted로 정렬
1
2
3
4
5
6
7
8
9
10
11
12
13
N = input()
N = int(N)
series = [input() for n in range(N)]
sorted_series = sorted(series)
# .sort()를 쓰면 NoneType Error 발생
# sorted_series = series.sort() - 사용 ㄴㄴ
for i in sorted_series:
print(i)
실패 소스 2 - 메모리 초과
입력 값의 범위를 정함
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
N = input()
N = int(N)
if N <=10000000:
series = []
while len(series) != N:
a = int(input())
if a <= 10000:
series.append(a)
sorted_series = sorted(series)
for i in sorted_series:
print(i)
실패 소스 3 - 메모리 초과
값이 들어갈 10,000,000개의 빈 배열을 만들어 놓고 시작
1
2
3
4
5
6
7
8
9
10
11
12
13
N = int(input())
series = [None] * 10000000
for i in range(N):
a = int(input())
series[a] = a
abc = [b for b in series if b != None]
for i in abc:
print(i)
실패 소스 4 - 메모리 초과
삽입정렬을 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
N = int(input())
series = [None] * N
for i in range(N):
series[i] = input()
for j in range(2, N):
key = series[j]
i = j - 1
while i>0 and series[i] > key:
series[i+1] = series[i]
i = i - 1
series[i+1] = key
for num in series:
print(num)
실패 소스 5 - 런타임 에러
10,000개의 빈 배열을 만들어 놓고 시작
중복된 개수를 적기 위한 배열이 하나 더 있음
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
N = int(input())
series = [None] * 10000
number = [None] * 10000
for i in range(N):
a = int(input())
if series[a] == None:
series[a] = a
number[a] = 1
else:
number[a] = number[a] + 1
for b in series:
if b != None:
for i in range(number[b]):
print(series[b])
실패 소스 6 - 런타임 에러
위에서 사용되었던 중복 개수 배열을 없애고 enumerate를 사용
1
2
3
4
5
6
7
8
9
10
11
12
N = int(input())
series = [0] * 10000
for i in range(N):
a = int(input())
series[a] = series[a] + 1
for c, num in enumerate(series):
if num != 0:
for d in range(num):
print(c)
실패 소스 7 - 런타임 에러
위의 enumerate 대신 len을 통해 index에 접근
입력 방법 변경 input() -> (sys.stdin.readline())
1
2
3
4
5
6
7
8
9
10
11
12
import sys
N = int(input())
series = [0] * 10000
for i in range(N):
a = int(sys.stdin.readline())
series[a] = series[a] + 1
for b in range(len(series)):
if series[b] !=0:
for c in range(series[b]):
print(b)
실패 소스 8 - 메모리 초과
counting sort 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
N = int(input())
series = []
for i in range(N):
series.append(int(sys.stdin.readline()))
counter = [0] * (max(series) + 1)
for i in series:
counter[i] += 1
ndx = 0
for i in range(len(counter)):
while 0 <counter[i]:
series[ndx] = i
ndx += 1
counter[i] -= 1
for num in series:
print(num)
성공 소스 1
최백준선생님의 코멘트에 따라 생성 리스트의 크기를 10,000에서 10,001로 바꾸었더니 성공..
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys
N = int(input())
series = [0] * 10001
for i in range(N):
a = int(sys.stdin.readline())
series[a] = series[a] + 1
for b in range(len(series)):
if series[b] !=0:
for c in range(series[b]):
print(b)
성공 소스 2
딕셔너리 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
N = int(input())
dic = {}
for i in range(N):
a = int(sys.stdin.readline())
if a in dic:
dic[a] = dic[a] +1
else:
dic[a] = 1
for sorted in sorted(dic.items()):
for i in range(sorted[1]):
print(sorted[0])
배운 것
위에 포함된 개념들 - ‘Counting Sort’ 및 ‘삽입정렬’과 그리고..
1. 딕셔너리에서 키를 찾을 때 없을 경우, None이 아니라 KerError를 raise 함.
그래서 아래와 같이 key 값이 있는지를 확인해야 함. == None 은 사용 불가
1
2
3
4
5
6
7
8
for i in range(N):
a = int(sys.stdin.readline())
if a in dic:
dic[a] = dic[a] +1
else:
dic[a] = 1
2. 배열을 초기화할 때는 아래와 같이 사용
1
new_list = [None] * n
3. sys.stdin.readline() 가 input()보다 빠르다고 한다.
코멘트
여덟시간 가까이 시도하면서 배운 것도 참 많다. 그리고 알고리즘 풀이는 재미있다.
그리고.. 문제를 제대로 읽고 꼼꼼하게 생각했으면 이렇게 오래 걸리지 않았을텐데, 내 경험과 능력도 부족했고 또 성급하기도 해서 한참을 돌아왔다. 배운 것도 참 많긴 하지만.. 뭐랄까 진짜로 하나 하나 배울수록 내가 얼마나 모르고, 그리고 컴퓨터라는 게 얼마나 복잡한지 알아가는 것 같다. 계산기라는 것의 원리도 한번 제대로 배우고 싶기도 하고..
