[Baekjoon] 9440_숫자 더하기

Silver II

문제(출처: https://www.acmicpc.net/problem/9440)

---

< 숫자 더하기 >

 

문제 풀이 

 

작은 숫자를 만들기 위해 작은 값부터 뽑아 나열한다. 만약 1 2 7 8 9라면 179, 28로 두 수를 만든다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _9440_ { // 숫자 더하기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		String input = "";
		int zero = 0;
		PriorityQueue<Integer> queue = new PriorityQueue<>();

		while (!(input = (bf.readLine())).equals("0")) {
			st = new StringTokenizer(input);

			int n = Integer.parseInt(st.nextToken());

			for (int i = 0; i < n; i++) {
				int num = Integer.parseInt(st.nextToken());

				if (num != 0) {
					queue.add(num);
				} else {
					zero += 1;
				}
			}

			String str1 = "";
			String str2 = "";
			boolean flag = false;

			while (!queue.isEmpty()) {
				if (!flag) {
					if (str1.length() > 0 && zero > 0) {
						str1 += "0";
						zero -= 1;
					} else {
						str1 += Integer.toString(queue.poll());
					}
					flag = true;
				} else {
					if (str2.length() > 0 && zero > 0) {
						str2 += "0";
						zero -= 1;
					} else {
						str2 += Integer.toString(queue.poll());
					}
					flag = false;
				}
			}

			while (zero > 0) {
				if (str1.length() > str2.length()) {
					str2 += "0";
				} else {
					str1 += "0";
				}
				zero-=1;
			}

			bw.write((Integer.parseInt(str1) + Integer.parseInt(str2)) + "\n");

		}
		bw.flush();
	}
}

변수)
input : 입력 값
zero : 입력받은 수 중에 0의 개수
queue : 우선순위 큐
n : 연습문자에서 사용될 숫자의 개수
num : 사용될 n개의 숫자
str1, str2 : 만든 두 숫자

 

0이 아닐 때까지 연습 문제를 하나씩 입력받는다. 각 줄의 첫 번째 나오는 수를 연습문제에서 사용될 숫자의 개수이다. 연습 문자에서 사용될 숫자의 개수만큼 수를 입력받아 우선순위 큐에 저장한다. 이때 0이면 우선순위 큐에 저장하지 않고 zero값을 1 증가한다. 

 

우선순위 큐가 빌 때까지 다음 과정을 반복한다.

1) flag 값이 false이고 만약 문자열의 길이가 0보다 크고 zero 값이 0보다 크다면 0을 추가한다. str1 길이가 0이거나 zero값이 0이라면 str1에 우선순위 큐 값을 뽑아 문자열에 추가한다. 

2) flag 값이 true이고 만약 문자열의 길이가 0보다 크고 zero 값이 0보다 크다면 0을 추가한다. str2 길이가 0이거나 zero 값이 0이라면 str2에 우선순위 큐 값을 뽑아 문자열에 추가한다.

 

위 과정을 거친 후에도 zero 값이 0보다 크다면 zero 값이 0이 될 때까지 다음 과정을 반복한다.

1) str1의 길이가 str2의 길이보다 길다면 str2에 0을 추가한다.

2) str2의 길이가 str1의 길이보다 길다면 str1에 0을 추가한다.

3) zero 값을 1 감소한다.

 

구한 두 값을 더한 후 출력한다.

---

---