[Beakjoon] 백준 5619번 Python

Beakjoon 5619, 세 번째
solved.ac Silver2
Greedy 알고리즘

문제

서로 다른 자연수 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)

출력

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

Sulution

n = int(input())
data = []
for _ in range(n):
    d = int(input())
    data.append(d)
data.sort()

result = []
for i in data[:4]:
    for j in data[:4]:
        if i != j:
            r = int(str(i) + str(j))
            result.append(r)
result.sort()

print(result[2])

풀이

입력받을 최소의 수가 3이기 때문에 입력받은 숫 중에서 가장 작은 3개의 수만 가지고 숫자를 조합을 합니다.

• 모든 수를 비교해서 배열을 만들고 정렬을 하게 되면 메모리 초과를 일으킬 수 있습니다.
• 반복문을 range(4)로 걸어서 data[i]와 data[j]의 문자열을 더해서 list에 추가하게 되면 100% 상태에서 런타임 에러(index)가 뜨게 됩니다.

---

 

5619번: 세 번째