[백준] 5619번 - 세 번째 [Java]

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

 

[백준] 5619번 - 세 번째 [Java]

[백준] 5619번 - 세 번째 [Java]

---

1.  아이디어

 

두 수를 붙여서 만든 수들 중 세 번째로 작은 수를 구하는 문제로 수어진 수열을 크기 순으로 정렬했을 때 5번째 이상으로 큰 수를 사용해서 세 번째로 작은 수를 만들 수 없음을 이용했다.

---

2. 문제풀이

 

주어진 수열의 길이가 3일 경우 3가지 수의 조합들 중 정답이 있고, 주어진 수열의 길이가 4 이상일 경우 주어진 수열을 정렬했을 때 가장 작은 4가지 수들의 조합 중 정답이 있다. 해당 조합들을 우선순위 큐에 넣은 후 세 번째 수를 뽑아내는 방식으로 구현했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        int ans = find(Math.min(N, 4), arr);
        System.out.println(ans);
    }

    private static int find(int len, int[] arr) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                pq.add(Integer.parseInt(new StringBuilder().append(arr[i]).append(arr[j]).toString()));
                pq.add(Integer.parseInt(new StringBuilder().append(arr[j]).append(arr[i]).toString()));
            }
        }

        pq.remove();
        pq.remove();
        return pq.remove();
    }

}

---

4. 후기