[JAVA-D3] SWEA 3809 - 화섭이의 정수 나열

SW Expert Academy

 

✅ 문제 요약

n만큼 수가 주어졌을 때, 해당 숫자들로 수를 이루어라, 이때 이루지 못한 수 중에서

가장 작은 수를 출력하라

 

🤔 문제 풀이

처음 문제를 보고 완전 탐색으로 접근하려고 했었다. 

하지만 주어지는 숫자의 개수를 보고 바로 다른 방법을 생각해보았다.

 

주어지는 숫자로 수를 이룰 때 특징은 반드시 주어지는 순서대로 이루어야 한다는 것,

예를들어 3, 0, 1이 주어졌을 때 3, 0, 1, 30, 31, 301이 가능하지만 13이나 130 같은 수는

이룰 수 없다. 

따라서 모든 수 입력 값들을 입력받는 순서대로 하나의 문자열에 더하고

0부터 시작하여 어떤 수 I가 문자열에 contains되지 않는다면 I를 정답으로 채택하도록 했다.

 

🚨CODE

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

public class Solution {

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

		int testCase = Integer.parseInt(br.readLine());
		for (int t = 1; t <= testCase; t++) {
			int n = Integer.parseInt(br.readLine());
			String nums = "";
			int count = 0;
			
			while(true) {
				if(count == n)
					break;
				StringTokenizer st = new StringTokenizer(br.readLine());
				while(st.hasMoreTokens()) {
					String num = st.nextToken();
					nums = nums.concat(num);
					count++;
				}
			}
			
			int answer;
			for(int i = 0; ; i++) {
				if(nums.contains(String.valueOf(i)))
					continue;
				else{
					answer = i;
					break;
				}
			}
			
			bw.write(String.format("#%d %d\n", t, answer));
		} // testcase
		bw.flush();
	}
}