https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18_yw6I9MCFAZN
** 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
package day1;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Set;
import java.util.StringTokenizer;
public class No1 {
static int n,m,k;
static int[][] arr;
static int total;
static StringTokenizer st;
static StringBuilder sb;
static Set<Integer> set;
static boolean[] visited;
static long max;
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int tc = Integer.parseInt(br.readLine());
for(int q=0; q<tc; q++) {
n = Integer.parseInt(br.readLine());
int test = (1<<10)-1;
int save=0;
int tmp=0;
int index=0;
while(true) {
while(tmp>0) {
int temp = tmp%10;
save = save|(1<<temp);
tmp /= 10;
}
if(save==test) {
break;
}
tmp = n*(index++);
}
System.out.println("#"+(q+1)+" "+(n*(index-1)));
}
br.close();
bw.close();
}
}
|
cs |
기존 풀이 방법에는 Visited라는 크기 10의 배열을 사용해서 각각의 숫자 1개씩 들어올 떄마다 false를 true로 바꾸는 형태로 많이 풀었었다.
이번 풀이 방식은 Bit Mask로 각각의 숫자를 bit로 표기하여 문제를 풀었다.
** 풀이 내용
문제의 내용이 0~9까지의 숫자가 모두 사용된 순간의 값을 출력하는 것이기 때문에 한개의 int 변수에 bit로 저장하였다.
예를들어 초기의 값은 아래와 같을 것이다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
이 상태에서 첫번째 입력값인 "1295"를 입력받는다. 이를 while 반복문을 통해 숫자를 1의자리 하나씩 지워가보면 과정은 다음과 같다
1 << 5 --> 1 0 0 0 0 0
save = save | (1<<5)
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
1 << 9 --> 1 0 0 0 0 0 0 0 0 0
save = save | (1<<9)
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
1 << 2 --> 1 0 0
save = save | (1<<2)
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
1 << 1 --> 1 0
save = save | (1<<1)
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
이 과정으로 save의 모든 bit가 켜져 값이 1023이 되면 종료다.
'알고리즘 > SWEA' 카테고리의 다른 글
| [D2] 이진수 표현(비트마스크, BitMask) (1) | 2024.01.28 |
|---|