일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- ChatGPT
- 코로나19
- Docker
- github
- SW Expert Academy
- Baekjoon
- 맥북
- PYTHON
- 편스토랑 우승상품
- 우분투
- leetcode
- programmers
- Real or Not? NLP with Disaster Tweets
- 파이썬
- Kaggle
- gs25
- 프로그래머스 파이썬
- 금융문자분석경진대회
- 캐치카페
- ubuntu
- 프로그래머스
- 백준
- Git
- dacon
- 데이콘
- 편스토랑
- hackerrank
- 더현대서울 맛집
- 자연어처리
- AI 경진대회
- Today
- Total
솜씨좋은장씨
[BaeKJoon] 10989번: 수정렬하기 3 (Python) 본문
1일 1문제 8일차!
다행히도 작심 3일에 끝나지 않고 작심 8일까지 왔습니다.
오늘 풀어볼 문제는 수 정렬하기 3 입니다.
왜.. 수 정렬하기 2가 있는데 ? 문제가 ...? 또있지...?
라는 생각이 들어 수 정렬하기 2에 제출했던 코드를 제출해보았습니다.
결과는...!!!
메모리 초과라는 결과가 나왔습니다.
왜 그러지? 하고 문제를 잘 살펴보니
수 정렬하기 2의 메모리 제한은 256MB였고 수 정렬하기 3의 메모리 제한은 8MB인것을 알 수 있었습니다.
어떤 방법을 써야할까 고민해보다가 Dictionary를 사용하면!
메모리도 적게 사용하고 시간도 빠르게 해결할 수 있을 것 같았습니다.
바로 시도해보았습니다.
N = int(input())
my_dict = {}
for i in range(N):
num = int(input())
if num not in my_dict.keys():
my_dict[num] = 1
else:
my_dict[num] = my_dict[num] + 1
sorted_dict = sorted(my_dict.items())
for i in range(len(sorted_dict)):
for j in range(sorted_dict[i][1]):
print(sorted_dict[i][0])
Python3로 제출한 결과
PyPy3로 제출한 결과
이런...
생각과 많이 달랐나봅니다.
뭔가 정렬하는 부분에서 시간초과와 메모리 초과가 발생하지 않았나 생각되는 부분입니다.
이번에는 문제의 조건을 잘 살펴 보았습니다.
여기서 입력받는 숫자는 0부터 10,000사이의 숫자만 입력 받습니다.
이번엔 0으로 가득차있는 길이가 10,000인 list를 생성하고 입력받는 수를 index값으로 하여 해당 index의 값을 +1 씩 증가해주고
해당 list를 처음부터 반복문을 돌면서 0이 아닐경우 해당 숫자만큼 해당 index를 출력하는 방법을 떠올려 보았습니다.
또 바로 코드로 구현해 보았습니다.
N = int(input())
check_list = [0] * 10000
for i in range(N):
input_num = int(input())
check_list[input_num - 1] = check_list[input_num - 1] + 1
for i in range(10000):
if check_list[i] != 0:
for j in range(check_list[i]):
print(i+1)
결과는!
인터넷을 검색해보니 10,001로 바꾸어 성공했다는 글을 보아 10,000의 길이를 10,001로 늘여 시도해보았습니다.
N = int(input())
check_list = [0] * 10001
for i in range(N):
input_num = int(input())
check_list[input_num] = check_list[input_num] + 1
for i in range(10001):
if check_list[i] != 0:
for j in range(check_list[i]):
print(i)
하지만 결과는
그러던 중 input()의 속도가 느려 잘 사용하지 않고 sys 라이브러리에 있는 sys.stdin.readline()을 사용한다는 글이 기억났습니다.
import sys
N = int(input())
check_list = [0] * 10001
for i in range(N):
input_num = int(sys.stdin.readline())
check_list[input_num] = check_list[input_num] + 1
for i in range(10001):
if check_list[i] != 0:
for j in range(check_list[i]):
print(i)
바꾸어 제출해보니!
드디어 성공!
백준문제는 정말 시간과 메모리 제한이 제일 어려운 것 같습니다.
그래도 더 효율적인 방법으로 정렬하지 않고도
정렬한 것 같은 효과를 내는 방법에 대해 알게되어 좋았습니다.
'Programming > 코딩 1일 1문제' 카테고리의 다른 글
[BaeKJoon] 11004번: K번째 수 (Python) (0) | 2020.02.16 |
---|---|
[BaeKJoon] 11652번: 카드 (Python) (0) | 2020.02.15 |
[BaeKJoon] 10825번: 국영수 (Python) (0) | 2020.02.13 |
[BaeKJoon] 10814번: 나이순 정렬 (Python) (0) | 2020.02.12 |
[BaeKJoon] 11651번: 좌표 정렬하기 2 (Python) (0) | 2020.02.11 |