[백준] 10989: 수 정렬하기 3

문제

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

10989번: 수 정렬하기 3

난이도 보고 덤볐다가 백준의 매운맛을 3일동안 제대로 맛 본 문제

시간, 메모리 제한 쪽으로 너무 깐깐해서 두손 두발 다 들었다.

 

그 덕분에 버블, 삽입, 선택, 퀵, 병합 정렬만 알던 내가 계수 정렬 까지 알게 됐으니 

고마운 문제기도 하다.

 

내 풀이

N = int(input())
arr = []
for _ in range(N):
  arr.append(int(input()))
  
count = [0] * (max(arr) + 1)
for i in arr:
  count[i] += 1
  
answer = []
for j in range(len(count)):
  answer.extend([j] * count[j])
  
for x in answer:
  print(x)

계수 정렬을 배운 뒤 바로 써먹은 내 첫 풀이다.

그냥 계수 정렬 코드 그 자체인데 계속 헤매다가 여기서 해당 문제의 조건에 맞게 바꿔야 하는 부분들이 있다는 걸 깨달았다.

 

수정 필요 부분

1. input(), print() 사용

뭐 때문인진 모르겠는데 sys 가 아닌 input()이랑 print() 사용 시 시간 초과가 뜬다.

https://www.acmicpc.net/board/view/855

좀 찾아보니 위의 문제로 sys를 사용하는게 더 유리한 것 같다.

input() -> sys.stdin.readline()
print() -> sys.stdout.write()

앞으론 이렇게 쓰는걸로

 

2. 입력값 받자마자 count 리스트에 +1 추가, count 리스트 길이 지정

N을 입력받은 후 나머지 값들에 대해 받으며 arr에 담은 뒤

다시 꺼내 count 리스트에서 카운팅해줬는데

이 과정도 입력값을 받자마자 count 리스트에 +1을 추가해주는 과정을 통해 압축할 수 있었다.

 

다만, 그럴려면 count 리스트가 미리 존재해야 하는데

문제 입력 조건에서 N 이후 주어지는 입력 값의 범위는 1 <= x <= 10000인 것임을 힌트로 줬으므로

count = [0] * 10001

미리 선언이 가능하다.

 

3. 출력 로직 압축

나는 위에서 answer에 출력할 값들을 담았기에 다시 for문을 돌려야 문제에서 원하는 출력을 할 수 있었는데

for i in range(1,10001):
  for _ in range(count[i]):

이렇게 i에 대해 i까지의 값으로 돌면 i가 0일 경우 그냥 패스되고 i가 2이면 0, 1 이렇게 두 번 돌게 되니

그만큼 i를 출력하게 하면 된다.

 

이렇게 위의 세가지 사항에 대해 모두 고려하여 수정한다면 아래의 풀이 코드대로 바뀌게 된다.

근데 변수명만 같지 완전 다른 코드 아닌가

 

다른 풀이

import sys
N = int(sys.stdin.readline())

count = [0] * 10001
for _ in range(N):
  count[int(sys.stdin.readline())] += 1
  
for i in range(1,10001):
  for _ in range(count[i]):
      sys.stdout.write(str(i)+'\n')

 

사실 다른 코드가 맞다. 

너무 답답해서 어떻게 해결할 수 있는지 보려고 구글링해서 변수명 빼고 그대로 복붙했으니까

 

웃긴게 여기서 조금이라도 수정하거나 코드를 추가하면 바로 시간 초과, 메모리 초과가 나온다.

 

통과된 풀이를 보면서 드는 생각은 

처음에는 '아 내가 못했지'였는데

복기할수록 이렇게 자유도 없는 문제가 있나 하면서 너무너무 괘씸해졌다.

 

그래도 이번이 백준에서 딱 5번째 문제였는데 이정도면 나쁘지 않았다고 생각하며

sys와 계수 정렬도 알게됐으니 앞으로 비슷한 상황을 겪을 때 좀 더 유연하게 대처할 수 있지 않을까 싶다.

 

 

 

 

참고한 곳

https://soohee410.github.io/coding1

[BOJ] 10989번: 수 정렬하기3 | Python