[BOJ] 백준 1013 Contact - Python/Java

문제

https://www.acmicpc.net/problem/1013

1013번: Contact

해설

이 문제의 포인트는 정규표현식 (100+1+ | 01)+ 을 통해 앞에서부터 문자열 매칭을 시도하면 '틀린다'는 것입니다.

 

그 이유는 기본적으로 Greedy한 선택이 이 문제의 정답을 보장하지 않기 때문인데요. 

 

예를 들어 100011001 이라는 문자열을 보겠습니다. 정규표현식을 통해 앞에서부터 최대한 많은 문자열을 매칭시키면 아래와 같은 결과가 나옵니다.

 

[정규표현식 이용]

String = 100011001 [1000 제거, 연속한 1 모두 제거]

String = 001 [매칭 불가능]

결과 : 실패

 

그러나 아래와 같이 문자열을 매칭할 수도 있습니다.

String = 100011001 [1000 제거, 1 하나만 제거]

String = 1001 [100 제거, 1 하나 제거]

결과 : 성공

 

여기에서 보시다시피 100+이 나온 뒤 1을 제거할 때 모든 1을 제거할 것인가 Or 1을 남겨둠으로써 다시 100+에 걸리는 패턴을 만들어줄 것인가를 구분해주어야 합니다. 이는 아래 코드의 주석을 보면서 이해하시는 게 더 빠를 것 같습니다.

 

풀이는 아래와 같습니다.

 

풀이 - 파이썬

import sys
input = sys.stdin.readline

n = int(input()) # (100+1+ | 01)+
for _ in range(n):
    signal = input().rstrip()
    isRightPattern = True
    
    while len(signal) > 0:
        if signal.startswith("01"): # 01로 시작
            signal = signal[2:]

        elif signal.startswith("100"): # 100으로 시작
            signal = signal[3:]
            
            while len(signal) > 0 and signal[0] == '0': # 이어지는 0 소거
                signal = signal[1:]
            if len(signal) == 0: # 뒤에 1이 하나는 나와야 함
                isRightPattern = False
                break

            signal = signal[1:] # 처음에 이어지는 1 소거

            while len(signal) > 0 and signal[0] == '1':
                if len(signal) >= 3 and signal[1] == '0' and signal[2] == '0':
                    break # 100이 다시 나오는 패턴을 위해 보류
                else: # 이어지는 1 소거
                    signal = signal[1:]

        else:
            isRightPattern = False
            break
    if isRightPattern: print("YES")
    else: print("NO")

풀이 - 자바

package PS;

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

public class B_1013 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++){
            String signal = br.readLine();
            boolean isRightPattern = true;

            while(signal.length() > 0) {
                if(signal.startsWith("01")) // 01로 시작
                    signal = signal.substring(2);

                else if(signal.startsWith("100")){ // 100으로 시작
                    signal = signal.substring(3);


                    while(signal.length() > 0 && signal.charAt(0) == '0'){
                        signal = signal.substring(1); // 이어지는 0 소거
                    }
                    if(signal.length() == 0){ // 뒤에 1이 하나는 나와야 함
                        isRightPattern = false;
                        break;
                    }
                    signal = signal.substring(1); // 처음에 이어지는 1 소거

                    while(signal.length() > 0 && signal.charAt(0) == '1'){
                        if(signal.length() >= 3){
                            if(signal.charAt(1) == '0' && signal.charAt(2) == '0'){
                                break; // 100이 다시 나오는 패턴을 위해 보류
                            }
                        }
                        signal = signal.substring(1);
                    }
                }
                else{
                    isRightPattern = false;
                    break;
                }
            }
            String answer = isRightPattern ?  "YES" : "NO";
            System.out.println(answer);
        }
    }
}