본문 바로가기

카테고리 없음

[백준 16496번] 큰 수 만들기 (Python3)

import sys
input = sys.stdin.readline

N = int(input())
data = [*input().split()]

maxL = 0
for d in data:
  maxL = max(maxL,len(d))

maxL *= 2
nums = []
for d in data:
  newd = d*(maxL//len(d))
  for i in range(maxL%len(d)):
    newd += d[i]
  nums.append((newd,len(d)))

nums.sort(reverse = True)

result = ""
for n,l in nums:
  for i in range(l):
    result += n[i]

if result[0]=="0":
  print(0)
else:
  print(result)

 

알고리즘을 요약하면,

1. 가장 길이가 긴 문자열의 길이(maxL)를 구한다.

2. maxL에 두배를 한만큼 모든 숫자문자열을 반복시킨다. (maxL*2가 8이고 숫자가 123이라면 12312312)

3. 정렬하고 합친다

 

아주 간단하고 생각해내기도 쉽다. 그런데 문제는 의외의 반례가 많았다.

 

 

제일 처음에 틀렸던 이유는 0 때문이었다. 0 0 0 0 이 입력으로 주어질 경우 0으로 출력해야 하는데 0000응로 출력했던 것

 

두번째로 틀린 이유는, maxL의 두배만큼 반복시키는 것이 아니라 maxL만큼만 반복시킨 것이 문제였다. 이렇게 되면 1211, 121 이라는 입력이 주어졌을 때, 두 숫자 모두 1211이 되어 정렬할 수 없게된다.

 

두번째 이유는 질문게시판에서 반례를 통해서 알아냈는데, 사실 이렇게 풀면 안된다고 생각한다.

앞으로는 직접 반례를 찾아가면서 스스로 디버깅할 수 있도록 더 노력해야할 것이다.

 

 

오늘의 교훈) 다른 사람들의 반례에 의존하지 말고 직접 디버깅하자