(백준) 10989: 숫자 정렬 3

by

문제

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

10989호: 분류번호 3

'추천 관련글,

숫자 N(1 ≤ N ≤ 10,000,000)의 수는 첫 번째 줄에 표시됩니다. 번호는 두 번째 줄부터 N줄로 제공됩니다. 이 숫자는 10,000보다 작거나 같은 자연수입니다.

www.acmicpc.net

난이도를 보고 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()를 사용하면 timeout이 발생합니다.


(백준) 10989: 숫자 정렬 3 1
https://www.acmicpc.net/board/view/855

약간의 연구 끝에 위의 문제에 대해 sys를 사용하는 것이 더 유리한 것으로 보입니다.

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

이렇게 써서

2. 입력 값을 수신하자마자 카운트 목록에 +1을 추가하고 카운트 목록의 길이를 지정하십시오.


(백준) 10989: 숫자 정렬 3 2

N 수신 후 나머지 값을 수신하여 arr에 저장

다시 꺼내서 카운트 리스트에 세었다.

이 프로세스는 입력 값을 수신하자마자 카운트 목록에 +1을 추가하여 압축할 수도 있습니다.

단, 그러기 위해서는 카운트 목록이 미리 존재해야 합니다.

문제 입력 조건에서 N 이후에 주어지는 입력 값의 범위는 1 <= x <= 10000 임을 암시하므로

count = (0) * 10001

사전에 선언할 수 있습니다.

3. 출력 논리 압축

출력할 값을 위의 답에 넣었기 때문에 문제에서 원하는 출력을 얻기 위해서는 for 문을 다시 실행해야 했습니다.

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

이와 같이 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 | 파이썬

(BOJ) 제10989호: 숫자 정렬 3 | Python 2021년 2월 20일 게시됨 문제 N개의 숫자가 주어지면 오름차순으로 정렬하는 프로그램을 작성하십시오. 입력 첫 번째 줄의 숫자 N(1 ≤ N ≤ 10,000,000)의 개수가 메인

soohee410.github.io