[boj] 5619번: 세 번째

출처 : https://www.acmicpc.net/problem/5619

5619번: 세 번째

 

 

1. 문제 설명

서로 다른 자연수 n개 a1, a2 ... an이 주어진다. 주어진 자연수 중에서 2개를 선택해 이어 붙여서 새로운 수를 만들 수 있다. 이때, 세 번째로 작은 수를 구하라. 

ex)

3과 4를 합치면 7이 아니라 34 또는 43이 된다. 

a1 =1, a4 = 11을 합쳐서 만든 111의 경우에 a1a4와 a4a1은 다른 수이다.

 

 

 

 

2. 접근 방식 

정렬을 통해 오름차순으로 나열한 뒤 2개를 선택해 붙여서 만들 수 있는 수들 중 세 번째로 작은 수를 찾아낸다.

 

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

import sys
input = sys.stdin.readline
T = int(input())  # 테스트 케이스
arr = []  # 각 수를 입력받기 위한 배열
for _ in range(T):
    arr.append(int(input()))
arr.sort()  # 오름차순 정렬해준다.
ans = []  # 정답 출력을 위한 배열
for i in arr[:4]:  # 세 번째로 작은 수를 출력하기 위해서는
    for j in arr[:4]:  # 모든 경우의 수를 탐색할 필요 없다.
        if i != j:  # 서로 중복되지 않은 수에 한해서만
            tmp = int(str(i)+str(j))  # 두 수를 이어붙여 정수형 변환해준다.
            ans.append(tmp)

ans.sort()
print(ans[2])  # 세 번째로 작은 수 출력(인덱스는 0부터 시작)

 

 

 

4. 분석

Time : O(nlogn)
Space : 
소요시간 : 1시간 
제출 횟수 (무작정 제출하기 않기)  : 3회
어려웠던 부분과 해결한 방법 : 모든 경우의 수를 찾는 방법밖에 떠오르지 않았다. 나중에 떠오른 아이디어는 어차피 세 번째로 작은 수를 찾는다면 모두 탐색할 필요가 없을 것이라는 것을 깨닫고 코드를 수정하였다. 
실수가 줄어들었는가 ? : 아직..