1013 Contact [JAVA]

문제 분석

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

주어진 정규식에 해당하는 문자열인지 판단하는 로직을 만들면 되는 문제다.

 

난도 자체는 쉽겠지만 문제는 경우의 수를 정말 잘 따져야 한다..

 

나는 문자를 1개씩 붙여보며 가능성이 있는 지 판단하는 방식으로 구현했다.

 

idx를 증가시켜가며 StringBuilder에 char를 계속 append하고

해당 StringBuilder의 크기를 기준으로

1 -> 패턴이 될 가능성이 있음

2 -> 01은 패턴이니 sb 초기화 ,10 은 패턴이 될 가능성이 있음

3-> 100은 패턴이 될 가능성이 있음

4up ->

          0이 추가된 경우

                -> 직전이 0이였다면 100000...의 형태로 패턴이 될 가능성이 있음

                -> 직전이 1이였다면 100....1.... 0의 형태 이기에 직전까지가 패턴이고 0은 01이 될 가능성이 있음

          1이 추가된 경우

                -> 직전이 0이였다면 100...01의 형태이므로 패턴이고, 다음 char를 덧붙여도 패턴이 될 가능성이 있고, 현재 idx                      까지만 패턴일 수 있음

                -> 직전이 1이였다면 100....1....1 1의 형태로 패턴을 유지하고 있고, 다음 char를 덧붙여도 패턴이 유지될 수 있                        고, 직전 idx 또한 1이기에 직전까지가 패턴이고 현재 idx부터는 새로운 패턴의 시작이 될 가능성이 있음                               (100...1...1 / 1 ~~)

 

배열의 끝까지 검사한 경우 -> sb가 초기화 되어있거나 (그러면 마지막 원소까지 포함하는 패턴이 생성된 것이니) 현재 패턴의 마지막이 1인 경우 (해당하는 경우는 4up case에서 패턴이 유지되는 경우밖에없음) ==> 이 2가지 경우에 해당한다면 주어진 문자열은 패턴을 준수하고 있기에 이를 마킹한다.

 

 

뭔가 말로하니 좀 더 헷갈리는거같으니 코드를 보고 위의 설명과 맞춰 이해를 해보자.

 

코드

import java.util.*;

public class Main {

    static char[] line;

    static boolean isPossible;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < t; i++) {
            line = sc.nextLine().toCharArray();
            isPossible = false;
            dfs(0,new StringBuilder());
            String ans = isPossible ? "YES" : "NO";
            System.out.println(ans);

        }
    }

    static void dfs(int idx, StringBuilder sb){
        if(isPossible)
            return;

        if(idx == line.length){
            //reached endpoint
            isPossible = sb.length()==0 || (sb.length()>3 && sb.charAt(sb.length()-1) =='1');
            return;
        }


        sb.append(line[idx]);

        if(sb.length() == 1){
            dfs(idx+1, sb);
        }else if(sb.length() == 2){
            if(sb.toString().equals("01")){
                dfs(idx+1, new StringBuilder());
            }else if(sb.toString().equals("10")){
                dfs(idx+1, sb);
            }
            //delete 00,11
        }else if(sb.length() == 3){
            if(sb.toString().equals("100"))
                dfs(idx+1,sb);
        } else{
            //only can be first pattern

            //case '0'-1. 10 0...0 => can be pattern
            //case '0'-2. 100000 0(last) => fail
            //case '0'-3. 100..0 11..111 0(not last) => can be start with 0
            if(line[idx] == '0'){
                if(idx < line.length-1){
                    if(line[idx-1] == '0')
                        dfs(idx+1, sb);
                    else dfs(idx+1, new StringBuilder("0"));
                }
                //case 0-2
            }else{
                //case '1'-1. 100..0001
                if(line[idx-1] == '0'){
                    dfs(idx+1, sb);
                    dfs(idx+1, new StringBuilder());
                }else {
                    dfs(idx + 1, sb);
                    dfs(idx + 1, new StringBuilder("1"));
                }
                //case '1'-2. 1001..1 1

            }

        }

    }
}