BOJ 2385 Secret Sharing
BOJ 2385 Secret Sharing
문제 내용
숫자로만 이루어진 문자열이 개 주어집니다. 이를 배열하여 0으로 시작하지 않는 수 중 가장 작은 수를 만들어 출력하세요. 그러한 수가 존재하지 않으면 INVALID를 출력하세요.
입력
첫 줄에 문자열의 개수 이 주어집니다. ()
다음 줄에는 개의 문자열이 한 줄에 주어집니다. 각 문자열의 길이는 5 이하입니다.
문제 풀이
스포일러
먼저, 모든 문자열이 0으로 시작하면 자명하게 불가능하며, 그 외에는 자명하게 가능합니다.
0으로 시작하지 않는 문자열 중 하나를 맨 앞에 두고 큰 수 만들기 알고리즘을 사용하면 되는데, 단순히 큰 수 만들기 기준으로 최소인 문자열을 앞에 두면 다음과 같은 반례가 존재합니다.
3
3 301 00이때 정답은 300301이지만, 큰 수 만들기 기준으로 301이 3보다 앞에 와야 하므로 틀린 코드는 301003을 출력합니다.
이 크지 않으므로, 0으로 시작하지 않는 문자열 각각을 맨 앞에 둬 보고 그 결과 중 최소를 골라 출력하면 됩니다.
Last updated on