BEAKJOON / 백준 - JAVA 32290번 MEX vs OR

2024.11.21기준 - 브론즈1

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

🟥 풀이

이 문제는 입력 받는 l부터 r까지의 모든 수를 x와 비트연산자 or을 이용해 배열에 넣고 배열에 해당하지 않는 수 중 가장 작은 수를 출력하는 문제입니다.

 

저의 접근은

1. 범위가 0 ~ 1000이기 때문에 이 중 가장 큰 수는 1023입니다. 그러므로 비트연산자로 계산된 수를 boolean 배열로 체크를 해줍니다.
2. 0부터 시작해 boolean 배열이 false인 수를 만나면 그 인덱스를 출력해줍니다.

1. 입력받은 수를 저장하고, 빈 boolean 배열을 선언합니다.

int l = Integer.parseInt(st.nextToken()); // 시작 번호
int r = Integer.parseInt(st.nextToken()); // 끝 번호
int x = Integer.parseInt(st.nextToken()); // or 번호

boolean[] visit = new boolean[1100]; // 최대값은 1023이므로 길이를 1100으로 지정

 

2. l부터 r까지의 수를 x와 or 비트연산자를 계산해 visit에 체크해줍니다.

for (int i = l; i <= r; i++) {
    visit[i | x] = true;
}

 

3. 인덱스 0번 부터 시작해 visit가 false가 나오면 인덱스를 출력하고 반복문을 멈춰줍니다.

int result = 0;
for (int i = 0; i < 1100; i++) {
    // mex가 포함하지 않은 수 중 가장 작은 수를 구하는 조건문
    if (!visit[i]) {
        result = i;
        break;
    }
}

 

 

🟪 코드

package Main;

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int l = Integer.parseInt(st.nextToken()); // 시작 번호
		int r = Integer.parseInt(st.nextToken()); // 끝 번호
		int x = Integer.parseInt(st.nextToken()); // or 번호
		
		boolean[] visit = new boolean[1100]; // 최대값은 1023이므로 길이를 1100으로 지정
		
		for (int i = l; i <= r; i++) {
			visit[i | x] = true;
		}
		
		int result = 0;
		for (int i = 0; i < 1100; i++) {
			// mex가 포함하지 않은 수 중 가장 작은 수를 구하는 조건문
			if (!visit[i]) {
				result = i;
				break;
			}
		}
		
		bw.write(Integer.toString(result));
		bw.flush();
		bw.close();
		br.close();
	}
}