https://www.acmicpc.net/problem/5619
5619번: 세 번째
서로 다른 자연수 n개 a1, a2, ..., an이 주어진다. 이때, a1, ... an에서 2개를 선택해서 붙여서 새로운 수를 만들 수 있다. 이때, 세 번째로 작은 수를 구하는 프로그램을 작성하시오. 예를 들어, 3과 4
www.acmicpc.net
* 문제 요약
서로 다른 자연수 n개 a1, a2, ... an 이 주어진다. 이때 a1, .... an 에서 2개를 선택해서 붙여서 새로운 수를 만들 수 있다.
이때, 세 번째로 작은 수를 구하는 프로그램을 작성하시오.
예를 들어 3과 4를 합치면 34 나 43 이 된다. 또 a1 = 1, a4 = 11 을 합쳐서 111을 만든 경우에 a1a4 와 a4a1 은 서로 다른 수이다.
* 입력
첫째 줄에 수의 갯수 n (3 <= n <= 10^8) 이 주어진다.
다음 줄 부터 한 줄에 하나씩 ai 가 주어진다. (1 <= ai <= 10,000)
* 출력
세 번째로 작은 수를 출력한다.
* 예시
* 해결 과정
각 숫자에 대한 입력을 배열에 받고 난 다음 해당 배열을 오름차순 정렬해 준 후 첫번째, 두번째, 세번째 인자까지만 따로 꺼내어 새로 배열을 만든 뒤, 다음과 같은 로직을 수행한다.
1. 새로 만든 배열을 대상으로 이중 반복문을 통해 2가지 인자를 이용해 만들 수 있는 모든 숫자 조합을 만들고, 만들어진 숫자를 우선순위 큐에 저장한다.
2. 우선순위 큐에서 3번째로 작은 수를 출력한다.
어차피 입력받은 숫자들 중에서 2가지 숫자를 활용하여 만들 수 있는 모든 숫자들 중 3번째로 작은 숫자 하나만 찾으면 되는 것이므로, 입력받은 값들을 정렬해준 다음 만들어지는 숫자들의 갯수를 최소화 하기 위해 입력받은 값들 중 가장 작은 3개의 숫자들을 대상으로만 숫자 조합을 만들어주었다.
그 숫자들 중에서 2가지 숫자를 통해 만들 수 있는 새로운 숫자들 중 3번째로 작은 숫자가 곧 구하고자 하는 세 번째 수의 정답에 가장 가까운 값이 될 것이다.
* 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
new Main().solution();
}
private void solution() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int count = Integer.parseInt(br.readLine());
int[] array = new int[count];
for (int i = 0; i < count; i++) {
array[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(array);
int result = 0;
if (array.length == 3) {
result = searchThird(array);
} else if (array.length > 3) {
int[] cloneArray = Arrays.copyOfRange(array, 0, 4);
result = searchThird(cloneArray);
}
bw.write(result + "\n");
bw.flush();
bw.close();
br.close();
}
private int searchThird(int[] array) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length; j++) {
if (i == j)
continue;
else {
StringBuilder sb = new StringBuilder();
sb.append(String.valueOf(array[i]));
sb.append(String.valueOf(array[j]));
priorityQueue.offer(Integer.parseInt(sb.toString()));
}
}
}
priorityQueue.poll();
priorityQueue.poll();
return priorityQueue.poll();
}
}
현재 상황에서 최적의 해답을 선택한다. -> 추출된 가장 크기가 작은 3개의 숫자를 통해 매 반복마다 만들 수 있는 숫자 조합을 만들어준다.
선택된 해답이 조건을 만족하는지 검사한다. -> 만들 수 있는 모든 조합의 숫자들이 다 만들어지기 전 까지는 세 번째로 작은 숫자를 특정할 수 없으므로 만들 수 있는 조합들이 모두 만들어질 때 까지 계속 반복문을 지속해주고, 반복문이 종료되고 나면 우선순위 큐에서 3번째 순서로 저장된 숫자를 출력해준다.
위와 같은 방식으로 문제를 풀었으므로 그리디 알고리즘 문제에 해당된다.
'코딩 테스트 > 그리디' 카테고리의 다른 글
백준 11501 - 주식 (자바 - 그리디) (0) | 2023.06.07 |
---|---|
백준 7507 - 올림픽 게임 (자바 - 그리디) (1) | 2023.06.07 |
백준 5002 - 도어맨 (자바 - 그리디) (1) | 2023.06.07 |
백준 3088 - 화분 부수기 (자바 - 그리디) (0) | 2023.06.04 |
백준 2785 - 체인 (자바 - 그리디) (0) | 2023.06.04 |