[ABC301] D - Bitmask (AtCoder Beginner Contest 301 in Java)

목차

문제 : ABC301 - D

 

필요 알고리즘

• 문자열, 수학
  
  • 이진수에 대한 수학적인 사고가 좀 필요한 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

1. 우선 '?'를 전부 '0'으로 바꿔본다. (만들 수 있는 최소값)

  그게 n과 동일하다면 n이 답이고, n보다 크다면 애초에 불가능한 경우이므로 -1을 출력하고 끝낸다.

 

2. 다음으로 '?'를 전부 '1'로 바꿔본다. (만들 수 있는 최대값)

  그게 n 이하라면 그 값이 답이다.

 

3. 그럼 이제 남은건 언제나 n 이하의 답이 있는 경우 뿐이다.

  여기서 케이스가 크게 3개로 나뉜다.

S 문자열의 각 문자와, N을 2진수 문자열로 변경한 문자열을 문자 하나씩 비교해본다고 했을 때 S의 문자를 c1, N의 문자를 c2라 하겠다.

 

- c1이 '?'인 경우엔 일단은 c2와 동일한 문자를 넣어주면 된다.

 

- c2가 '1'이고 c1이 '0'인 경우엔 쉽다. 그 경우가 발생한 문자 이후로 모든 '?'를 '1'로 바꿔주면 된다.

예를들어 S = "??0??", N(2진수) = "10100" 라고 하자.

처음 두 ??는 동일하게 "10"으로 넣으면 되고, 3번째 문자가 얘기한 케이스이므로 그 뒤 ?는 전부 '1'로 바꿔준다. 그럼 "10011"이 된다. 이진수의 특성을 이용한 방식이다.

 

- c2가 '0'이고 c1이 '1'인 경우엔 좀 복잡하다.

이 경우가 발생한 문자 이전 문자들 중 가장 우측의 c2가 '1'이고 c1이 '?'인 부분을 '0'으로 바꿔주고, 그렇게 '0'으로 바꿔준 위치 기준으로 뒤의 모든 '?'를 '1'로 바꿔주면 된다. 참고로 '1', '2'에서 이미 예외처리를 해줬으므로 '3'까지 내려왔다면 .c1이 '?'이고 c2가 '1'인 경우는 반드시 존재한다.

예를들어 S = "???1?", N(2진수) = "11000" 인 경우 위 방식대로 만든 "10111"이 답이다.

  

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
 
    private void solution() throws Exception {
        String s = br.readLine();
        long n = Long.parseLong(br.readLine());
 
        long lowNum = Long.parseLong(s.replaceAll("\\?", "0"), 2);
        if (lowNum > n) {
            System.out.println(-1);
            return;
        }
        if (n == lowNum) {
            System.out.println(n);
            return;
        }
 
        long highNum = Long.parseLong(s.replaceAll("\\?", "1"), 2);
        if (highNum <= n) {
            System.out.println(highNum);
            return;
        }
 
        String num = Long.toString(n, 2);
        int numLen = num.length();
        for (int i = 0; i < s.length()-numLen; i++) {
            num = "0" + num;
        }
 
        StringBuilder sb = new StringBuilder();
        int idxTmp = -1;
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = num.charAt(i);
 
            if (c1 == '?' && c2 == '1') idxTmp = i;
 
            if (c1 == c2) {
                sb.append(c1);
                continue;
            }
 
            if (c1 == '0' && c2 == '1') {
                for (int j = i; j < s.length(); j++) {
                    sb.append(s.charAt(j) == '?' ? '1' : s.charAt(j));
                }
                break;
            }
 
            if (c1 == '1' && c2 == '0') {
                sb = new StringBuilder();
                for (int j = 0; j < idxTmp; j++) {
                    sb.append(num.charAt(j));
                }
                sb.append('0');
 
                for (int j = idxTmp+1; j < s.length(); j++) {
                    sb.append(s.charAt(j) == '?' ? '1' : s.charAt(j));
                }
                break;
            }
 
            sb.append(c2);
        }
 
        System.out.println(Long.parseLong(sb.toString(), 2));
    }
}