[Silver II] 세 번째 - 5619 (구현)

[Silver II] 세 번째 - 5619

문제 링크

성능 요약

메모리: 30840 KB, 시간: 372 ms

분류

브루트포스 알고리즘(bruteforcing), 구현(implementation), 수학(math)

문제 설명

서로 다른 자연수 n개 a1, a2, ..., an이 주어진다. 이때, a1, ... an에서 2개를 선택해서 붙여서 새로운 수를 만들 수 있다. 이때, 세 번째로 작은 수를 구하는 프로그램을 작성하시오.

예를 들어, 3과 4를 합치면 34나 43이 된다. 또, a1 = 1, a4 = 11을 합쳐서 111을 만든 경우에, a1a4와 a4a1은 다른 수이다.

입력

첫째 줄에 수의 개수 n(3 ≤ n ≤ 108)이 주어진다. 다음 줄부터 한 줄에 하나씩 ai가 주어진다. (1 ≤ ai ≤ 10000)

출력

세 번째로 작은 수를 출력한다.

from itertools import permutations
n = int(input())
answer = []
for i in range(n):
  answer.append(int(input()))
answer.sort()
ans = []
a = list(permutations(answer[:4], 2))
for i in a:
  ans.append(int(str(i[0])+str(i[1])))
ans.sort()
print(ans[2])

세 번째로 작은 수를 구하려면 오름차순으로 정렬 후, 2개씩 순열로 뽑아서 다시 정렬 후, 3번째 값을 찾아주면 해결.

여기서 n의 범위가 10^8까지인데 서로 다른 자연수를 뽑아와야하고, a는 10000이하인 범위를 봐서는 n이 10^8까지 갈 일은 없다고 생각하고 풀어야 하는 것 같다.