이번에는 간단해보이는 문제를 들고 왔다. 색다른 풀이 방법이 나왔기에 기록하려고 한다.
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
5 5 4 3 2 1
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
1 2 3 4 5
풀이 과정
문제가 단순하지만, 실버 난이도에 시간 제한이 2초이고 N의 범위가 넓어서 평범하게 풀면 시간 초과가 뜰 것 같았다. 그런데...
0. 풀이
N = int(input()) arr = [int(input()) for i in range(N)] arr.sort() for i in arr: print(i)입력값 N만큼의 input을 받아서 정렬 후 값을 뽑는다.
이렇게 풀이할 시 시간초과가 발생할 줄 알았지만 무난하게 통과되었다??그래서 오늘은 스터디원이 아이디어를 제시했던 방법으로 다시 한 번 풀어보았다.
1. 입력값 설정하기
N = int(input()) arr = ['']*2000001 for i in range(N): n = int(input()) arr[n+1000000] = n숫자의 범위가 -1000000 ~ 1000000이므로 [''] * 2000001의 arr를 생성한다.
input값이 들어오면 2백만개의 '' 중 [n+1000000]에 해당하는 인덱스에 값이 기록된다.
2. 값 출력하기
for i in arr: if i != '': print(i)이미 인덱스로 인해 순서대로 정렬되었으므로, 기록된 숫자들을 출력한다.
이 방법도 시간초과가 아닐까 긴가민가했지만 다행히도 무난히 통과했다.
요즘 연습중인 내장함수 없이 문제 해결하기에 성공해서 더 기쁘고 신선하게 다가왔다.
- 답안
N = int(input())
arr = ['']*2000001
for i in range(N):
n = int(input())
arr[n+1000000] = n
for i in arr:
if i != '':
print(i)*모든 문제의 저작권은 백준 온라인 저지(https://www.acmicpc.net/) 원작자에게 있습니다.
백준 2751번(https://www.acmicpc.net/problem/2751)
