SWEA/D3

[SWEA] - 3809. 화섭이의 정수 나열 (D3)

0으하하0 2022. 5. 11. 14:52

[문제]

화섭이는 다음과 같은 흥미로운 추측에 대해 들었다.
“모든 정수는 π = 3.14159265…의 어떤 연속한 부분으로 나타난다.”
화섭이는 π에 대해 이것을 테스트해 보기는 힘들다고 생각했고, 그냥 유한한 정수열에 대해서 위처럼 연속한 부분을 끊어내어 보았다.
예를 들면 “3 0 1”같은 정수열로는 3, 0, 1, 30, 301을 만들 수 있다.
화섭이는 주어진 정수열로 만들 수 없으면서 가장 작은 정수가 무엇인지 궁금해졌다.
이를 구하는 프로그램을 작성하라. 위의 예에서는 0, 1은 나타나지만 2는 나타나지 않으므로 2가 답이 된다.
두 번째 테스트케이스를 예로 들면,

위 그림과 같이 0부터 11까지의 정수는 만들 수 있으나 12를 만들 수 없다. 그러므로 12가 답이 된다.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 N(1 ≤ N ≤ 103)이 주어진다.
다음으로는 N개의 정수 d1, d2, …, dN (0 ≤ di ≤ 9)이 순서대로 주어진다.
d들은 공백 하나 또는 줄바꿈으로 구분되어 있다.

[출력]
각 테스트 케이스마다 만들어낼 수 없는 가장 작은 정수를 출력한다.

 

문제 풀기

3809. 화섭이의 정수 나열

 


[풀이]

  • 주어진 수로 조합하여 만드는것이 아닌 연속되는 부분으로 만드는 경우이기 때문에 모든 숫자를 문자열로 붙여서 저장한다.
  • 0부터 시작해서 만들어둔 문자열에 포함되지 않는 수를 찾는다.
import java.util.Scanner;

class Solution {	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int tc=1; tc<=t; tc++) {
			int n = sc.nextInt();
			String str = "";
			
			for(int i=0; i<n; i++) 
				str += Integer.toString(sc.nextInt());
			
			for(int i=0; ; i++) {
				if(!str.contains(Integer.toString(i))) {
					System.out.format("#%d %d\n", tc, i);
					break;
				}
			}
		}
	}
}