백준 12919 JAVA 문제풀이

문제

풀이

먼저 어떠한 패턴이 있을 것이라는 생각을 하였다. 그리고 몇번 연산을 해보니 연산후의 문자열의 형태는 2가지 형태를 띄는 것을 알게 돼었다. S가 뒤집힌 형태를 포함할때와 그냥 S형태를 포함할 때이다.

 

i) S형태를 포함할 때는

 

앞의  string                 뒤의 string

B..A..A..B..A..A /  S  /..A..A..B..A..A..B..A ..A 

 

위의 형태와 같이 S를 기준으로 앞의 string은 맨앞에 B가 오고 A는 아무데나 위치할 수 있고 뒤의 string은 B의 위치는 상관이 없고 갯수가 앞의 string에서의 B의 갯수와 같다는 것이다.

즉 B가 맨앞에 올때 앞의 string의 B의갯수를 세서 뒤의 string과 같으면 연산이 가능한 형태인 것이다. 

 

 

ii) S가 뒤집힌 형태를 포함할때는 (S2라고하겠다)

 

앞의  string                 뒤의 string

B..A..A..B..A..A B..A../  S2  /..A..A..B..A..A..B..A ..A

 

위의 형태와 같이 S를 기준으로 앞의 string은 맨앞에 B가 오고 A는 아무데나 위치할 수 있고 뒤의 string은 B의 위치는 상관이 없고 갯수가 앞의 string에서의 B의 갯수보다 1개 적다는 것이다.

즉 B가 맨앞에 올때 앞의 string의 B의갯수를 세서 뒤의 string 보다 1개가 많으면 연산이 가능한 형태인 것이다. 

 

i), ii)의 조건에 맞춰서 알고리즘을 짜보았는데 사실 좀 복잡한 면이 있긴하다.

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

public class Main{
    static int det(String S, String T){

        char[] strS=S.toCharArray();
        char[] strS2=new char[strS.length];
        for(int i=0;i<strS.length;i++) {
            strS2[strS.length - 1 - i] = strS[i];
        }
        char[] strT=T.toCharArray();
        for(int i=0;i<strT.length-strS.length;i++){
            int same=0;
            //i번째부터 strS의 길이만큼 비교하여 같은것이 있는가?
            for(int j=0;j<strS.length;j++){
                if(strS[j]==strT[i+j]){
                    same=1;
                }
                else{
                    same=0;
                    break;
                }
            }
            if(same==1) {
                int front = 0;
                int back = 0;
                if(strT[0]=='B') {
                    for (int j = 0; j < i; j++) {
                        if (strT[j] == 'B') {
                            front++;
                        }
                    }
                    for (int j = i + strS.length; j < strT.length; j++) {
                        if (strT[j] == 'B') {
                            back++;
                        }
                    }
                    if (front == back) {
                        return 1;
                    }
                }
                else{
                    for (int j = i + strS.length; j < strT.length; j++) {
                        if (strT[j] == 'B') {
                            back++;
                        }
                    }
                    if(back==0&&i==0){
                        return 1;
                    };
                }
            }
        }

        //뒤집은 것
        for(int i=0;i<strT.length-strS2.length+1;i++){
            int same=0;
            //i번째부터 strS2의 길이만큼 비교하여 같은것이 있는가?
            for(int j=0;j<strS2.length;j++){
                if(strS2[j]==strT[i+j]){
                    same=1;
                }
                else{
                    same=0;
                    break;
                } //BABA  BBABA
            }
            if(same==1) {
                //0부터 i-1번째 까지 i+strS.length부터 strT.length-1 까지
                //둘다 맨앞에 B여야 한다 그리고 B의 갯수가 같아야 한다
                int front = 0;
                int back = 0;
                //front의 첫번째도 B back의 첫번째도 B
                if(strT[0]=='B') {
                    for(int j=0;j<i;j++){
                        if(strT[j]=='B'){
                            front++;
                        }
                    }
                for(int j=(i+strS2.length);j<strT.length;j++){
                    if(strT[j]=='B'){
                        back++;
                    }
                }
                if(front==back+1){
                    return 1;
                }
                }
            }
        }
        //strS2와 비교 B를더해서 뒤집은값
        return 0;
    }


    public static void main(String args[])throws IOException{
        Scanner scan=new Scanner(System.in);
        String S=scan.next();
        String T=scan.next();
        System.out.print(det(S,T));
    }
}

 

피드백

문제를 풀다가 너무 어렵게 푸는게 아닌가 싶어서 찾아보니 재귀를 사용하여서 푸는 문제였다.

결국 나의 방식대로해서 문제를 맞추긴 했지만 출제자의 의도가 재귀로 푸는 것인 만큼 재귀로 푸는 것이 맞는 풀이법이였던 것 같다.