SWEA - 새로운 불면증 치료법

그냥 풀 수도 있지만 비트마스킹을 활용하여 풀 수도 있는 문제

 

package algo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/*
 * 1. 양세기 : 첫 번째 N번 양, 두 번째 2N번 양 ... k번째 kN번양
 * 2. 현재 본 숫자 : ex) 1295양 -> 1, 2, 9, 5
 * 3. 0~9 모든 숫자를 보면 양 세기 멈춤  
 */
public class swea_새로운불면증치료법 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t = 1; t <= T; t++) {
			int N = Integer.parseInt(br.readLine()); //첫번째 양 번호
			
			int visited = 0; //현재까지 본 숫자를 비트로 표현, 0000000000(2)
			int goal = (1 << 10) - 1; //모든 숫자를 보게 되었을 때의 값, 10000000000 - 1 = 111111111(2)
			
			int x = 1;
			while(true) {
				int sheep = x * N; //x번째 양 번호
				
				char[] chs = String.valueOf(sheep).toCharArray();
				for(int i = 0; i < chs.length; i++) {
					int num = chs[i] - '0';
					visited = visited | (1 << num); //해당 숫자가 보게 되어 1로 변경
				}
				
				if(visited == goal) break; //모든 숫자가 등장하면 종료
				
				x++;
			}
			
			sb.append("#" + t + " " + x * N + "\n");
		}
		System.out.println(sb);
	}

}

 

 

 

 

 

결과