[백준] A와 B 2 12919번(🥇골드5)

사이트

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

문제

분석

매우 화가나는 문제이다.

 

일단 문제 자체는 어렵지 않았다. 이게 골드 문제가 맞는 문제인지 싶었다... 왜냐하면 너무 쉬웠기 때문이다.

 

하지만 문제를 풀어보니 계속 틀림... 일단 분석을 해보자 

 

이해

일단 이문제는 S와 T를 입력하고 나서

S의 문자열의 뒤에 연산을 더해서 T와 같으면 1 아니면 0을 반환하는 문제이다.

이때 연산은 첫번째 A를 더하기, 두번째 B를 더하고 뒤집기 이다. 

 

그래서 필자는 처음에 S 문자열 2가지의 연산 방법을 활용해서 T를 구하는 식으로 구했으나.....  

실수1

public class Bra12919 {
    static String s;

    static String t;

    static int len = 0;

    static StringBuilder sb;

    static boolean flag;

    static int correct = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine();
        t = br.readLine();

        sb = new StringBuilder();
        sb.append(s);


        len = t.length() - s.length();

        dfs(0);
        System.out.println(correct);
    }

    private static int dfs(int level) {
        String string = sb.toString();
        if (string.equals(t)) {
            flag = true;
            correct = 1;
            return 1;
        }

        if (s.length() >= t.length()) {
            return 0;
        }

        for (int i = level; i < len; i++) {
            if (!flag) {
                sb.append('A');
                dfs(level + 1);
                String substring_a = sb.substring(0, sb.length() - 1);
                sb = new StringBuilder();
                sb.append(substring_a);
            }

            if (!flag) {
                sb.append('B');
                sb.reverse();
                dfs(level + 1);
                String substring_b = sb.substring(1, sb.length());
                sb = new StringBuilder();
                sb.append(substring_b);
            }
        }
        return 0;
    }
}

위와 같이 코드를 작성하였다.

하지만 이 코드의 문제점은 2가지의 연산을 적용한 모든 경우의 수를 구해야되고 이는 즉 시간초과를 유래한다.

 

시간 초과를 막고 싶어서 S의 문자열 중 T의 문자열 부분의 일치하는 부분만 동작하도록 할려했다.   

이때 B연산을 추가할때 문자열을 뒤집힌 채로 T의 문자열과 비교를 해야한다. 

 

하지만 왠지 모르게 계속 틀렸습니다가 떴다.... 원래라면 시간초과가 떠야되는데 계속 안되서 필자는 이 방법은 포기했다. 

 

생각한게 거꾸로 구현을 하면 어떨까??? 

 

즉 이번에 T의 문자열을 하나씩 제거하면서 S와 맞는지 확인하는 방법이다.

실수2

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

public class Main {
    static String s;


    static int len = 0;

    static StringBuilder sb;

    static boolean flag;

    static boolean bol;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine();
        String t = br.readLine();

        len = t.length() - s.length();

        dfs(t);
        if (flag) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    private static int dfs(String message) {

        if (message.equals(s)) {
            flag = true;
            bol=true;
            return 1;
        }

        if (message.length() == s.length()) {
            bol=true;
            return 0;
        }
        if(message.length()<s.length()){
            bol=true;
        }

        while (!bol) {
            int length = message.length();
            char core = message.charAt(length - 1);
            if (core == 'A') {
                String substring = message.substring(0, length - 1);
                dfs(substring);
            } else {
                sb = new StringBuilder();
                String substring = message.substring(1, length);
                sb.append(substring);
                sb.reverse();
                dfs(String.valueOf(sb));
            }
        }

        return 1;
    }
}

 

코드는 간단해서 생략을 하겠다. 

하지만 이 방법도 틀렸다 한다.... 왜일까???? 

곰곰히 생각을 해봤는데 

 

만약 T 문자열이 BAA 이고 S 문자열이 A라고 가정했을때, 

저 코드대로 하면 T의 문자열 중 A 부터 제거된다. 

즉 틀렸다. B부터 제거되야 된다. 

 

왜냐하면 AA 다음에 B가 추가되면서 뒤집히면서 BAA가 된건데 즉 마지막으로 추가된 문자가 B인것이다! 

 

그래서 앞에 B가 온다는 것은 마지막으로 추가된것이므로 B를 제거하고 문자열을 뒤집어야된다. 

실수3

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

public class Main {
    static String s;


    static int len = 0;

    static StringBuilder sb;

    static boolean flag;

    static boolean bol;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine();
        String t = br.readLine();

        len = t.length() - s.length();

        dfs(t);
        if (flag) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    private static int dfs(String message) {

        if (message.equals(s)) {
            flag = true;
            bol=true;
            return 1;
        }

        if (message.length() == s.length()) {
            bol=true;
            return 0;
        }
        while (!bol) {
            int length = message.length();
            if (message.startsWith("B")) {
                sb = new StringBuilder();
                String substring = message.substring(1, length);
                sb.append(substring);
                sb.reverse();
                dfs(String.valueOf(sb));
            } else {
                String substring = message.substring(0, length - 1);
                dfs(substring);
            }
        }

        return 1;
    }
}

 

그래서 위와 같이 이번에 B를 먼저 if 문에 넣어 비교를 해봤다. 

즉 B가 문자 맨앞에 있을시 제거하고 아닐때는 마지막 문자를 제거하는 방법을 사용했다. 

 

하지만 역시나 틀렸다.... 

 

또 곰곰히 고민을 해봤다. 바로 정답이 나왔다. 

 

만약 "BABA" 가 T이고 S가 "A" 일시 저 코드대로 동작을 해봤을때 

 

첫번째 B가 제거되고 뒤집히면 ABA가 된다. 

 

두번째 뒤에 A가 제거되고 AB가 된다. 

 

세번째 앞자리가 B가 아니므로 뒤에 문자 A가 당연히 제거 될 줄알았는데 B가 제거된다... 

 

이는 곧 정합성이 떨어지고 당연히 틀렸다. 

 

해결

static String s;
static boolean flag;
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    s = br.readLine();
    String t = br.readLine();

    dfs(t);
    if (flag) {
        System.out.println(1);
    } else {
        System.out.println(0);
    }
}

private static void dfs(String message) {
    if (message.length() == s.length()) {
        if (message.equals(s)) {
            flag = true;
        }
        return;
    }

    if (message.endsWith("A")) {
        dfs(message.substring(0, message.length() - 1));
    }
    if (message.startsWith("B")) {
        dfs(new StringBuilder(message.substring(1)).reverse().toString());
    }

}

 

그래서 모든 방법을 동원해서 위와 같이 해결했다.

일단 while 문은 굳이 안써도 된다. 왜냐하면 재귀함수여서 계속 반복되니깐!! 

 

코드 동작을 설명하겠다. 

T가 BABA 이고 S가 A로 가정하겠다. 

 

첫번째

A if문에 들어오게 된다. 마지막 문자열이 A이므로 이때 BAB로 바뀌고 재귀함수를 호출한다. 

 

두번째 이번에 A if문이 아닌 B if 문으로 들어오게 된다. 앞자리가 B이고 뒷자리도 B이므로! 

 

이렇게 돌아가면서 일치하면 1을 반환하고 아니면 0을 반환한다. 

 

운이 좋아서 한번에 도는 거지 만약에 경우의 수에 걸릴때는 트리처럼 즉 가짓수처럼 해결하게 되므로 틀린것이 아니다.

 

 

전체코드

package bra;

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

public class Bra12919 {
    static String s;
    static boolean flag;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine();
        String t = br.readLine();

        dfs(t);
        if (flag) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    private static void dfs(String message) {
        if (message.length() == s.length()) {
            if (message.equals(s)) {
                flag = true;
            }
            return;
        }

        if (message.endsWith("A")) {
            dfs(message.substring(0, message.length() - 1));
        }
        if (message.startsWith("B")) {
            dfs(new StringBuilder(message.substring(1)).reverse().toString());
        }

    }
}

결과

느낀점

문제 이해는 골드 문제 답지 않게 쉬웠지만 좀 애먹은 문제였다.... 반성하고 또 반성해서 앞으로 나아가자