2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
n=int(input())
l=[]
for i in range(n):
k=int(input())
l.append(k)
l.sort() #기본 정렬함수로 리스트 오름차순 정렬
for i in l:
print(i) #리스트(l) 원소 출력
결과는 시간 초과... <이것이 코딩테스트다> 교재를 보면서 시간복잡도 계산을 해보았다.
우선 Python은 C보다 연산 속도가 느리다..! (파이썬으로 백준 문제를 처음 풀어봤는데 채점 속도만 봐도 확연히 차이난다..)
기억하자! 파이썬은 1초에 2000만(=20,000,000)번의 연산이 가능하다.
파이썬 내장 기본 정렬함수는 O(NlogN)이다.
(*여기서 log아래 밑은 10이 아니라 2다!)
결과적으로 문제 조건에서 N이 최대 1,000,000이라고 했으므로
sort() 함수 사용이 가능하다!
-> 그럼 도대체 왜...? 시간 초과가 되었을까...?
문제의 해결방법을 찾던 중!
sys.stdin.readline()의 존재를 발견했다.
" 한 두줄 입력받는 문제들과 다르게, 반복문으로 여러줄을 입력 받아야 할 때는
input()으로 입력 받는다면 시간초과가 발생할 수 있습니다.
맨 첫줄 Test case를 입력받을 때는input()을 사용해도 무방합니다.
그러나 반복문으로 여러줄 입력받는 상황에서는 반드시sys.stdin.readline()을 사용해야 시간초과가 발생하지 않습니다. "
* 활용은 다음 글 참고 [Python 문법] 파이썬 입력 받기(sys.stdin.readline) (velog.io)
import sys #모듈 불러오기
n = int(sys.stdin.readline())
l = [int(sys.stdin.readline().strip()) for i in range(n)] #코드 줄이기!
l.sort()
for i in l:
print(i)
근데 시간을 좀 더 단축하고 싶어 다른 풀이를 찾아보던 중...
sys.stout.write로의 출력으로 시간이 더 확실히 줄 수 있다는 것을 확인하였다!
import sys
input=sys.stdin.readline #input으로 정의해 코드 간단히 정리
n = int(input())
l = [int(input().strip()) for i in range(n)]
l.sort()
for i in l:
sys.stdout.write(f'{i}\n') #출력함수 대신해 시간단축!
유사문제 더 풀어보기
2750번: 수 정렬하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
10989번: 수 정렬하기 3 (acmicpc.net)
10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
import sys
input = sys.stdin.readline
a=[0]*10001 #입력 가능한 최대 수(둘째줄)만큼 리스트 크기 0으로 지정
n = int(input())
for i in range(n) :
a[int(input())] += 1 #입력받은 수(인덱스) 배열(a)에 카운트 저장
for i in range(10001) :
if a[i] != 0 : #입력받은 수가 맞다면
for j in range(a[i]) : #입력받은 횟수(카운트)만큼 입력받은 수를 출력하기
sys.stdout.write(f'{i}\n')
어쩌다보니... 10989번 문제를 굉장히...
힘들게 힘들게 풀게 되어... 풀이를 추가합니다...
계수정렬을 사용하는 문제이고, 메모리 제한(8MB)를 맞춰 문제 풀이를 하는 것이 관건이었다!
휴... 그래도 메모리도 맞추고 시간도 최대한 적게 걸리게끔 코드 작성해서 약간 뿌듯하다:)
'Language > Python' 카테고리의 다른 글
| 백준 11047번 동전 0 (Python) (0) | 2023.01.24 |
|---|