백준 5619번 - 세 번째

# 문제

5619번 : 세 번째

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

 

 

두 수를 조합해서 만들수 있는 수 중에 3번째로 작은 수를 구하는 문제이다.

문제를 잘 읽어보면 전체를 고려할 필요가 없고 앞에있는 몇개의 수만 고려하면 된다.

작성한 코드에서는 모든 수를 입력받고 정렬한 후에 인덱스 10번까지만 고려해서 문제를 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws NumberFormatException, 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);
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < Math.min(N, 10); i++) {
        	for (int j = 0; j < Math.min(N, 10); j++) {
        		if (i == j) continue;
        		int a = arr[i];
        		int b = arr[j];

                int digits = 1;
                while (b >= digits) digits *= 10;
                int num = a * digits + b;
                if (set.contains(num)) continue;
        		pq.add(num);
        		if (pq.size() > 3) pq.poll();
        	}
        }
        System.out.println(pq.poll());
    }
}

내림차순으로 배열되는 우선순위 큐에 생성되는 값을 집어넣고 만약 큐의 크기가 3을 넘으면 빼주는 방식으로 세번째로 작은 수가 큐의 가장 앞에 오도록 구현했다.