[백준 1361] 두 스트링 마스크 - JAVA

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

 

브루트포스 + 문자열 처리 문제

 

핵심 조건

1. 그리디 or 많은 조건 분기로 푸는 방법은 없거나 매우 까다롭다.

2. A 혹은 B보다 더 긴 문자열을 집어넣어서 최적인 경우는 없다.

 

접근법 세우기

1번에 의해 브루트포스를 해야하며,

2번에 의해 N=50일 때 복잡도를 O( 50(50-1)/2 * 50(50-1)/2) == O(150만) 정도로 잡아서 적용할 수 있다고 생각했다.

 

아이디어

1. str1, str2에 대해 *을 기준으로 head와 tail을 나눈다.

 

2.

String comp1 = head1 + sub2 + tail1;

String comp2 = head2 + sub1 + tail2;

 

comp1 == comp2라면, 정답을 갱신한다.

 

---

 

근데 메모리초과??

https://www.acmicpc.net/board/view/156497

 

일단 gc가 리터럴에 저장한 문자열을 제대로 지우지 않아서 메모리가 터졌다고 가정했다.

이후 StringBuilder로 삭제 시점을 정했더니 ac를 받았다. (or 가지치기로 탐색 자체를 줄여도 됐음)

 

자세한 이유는 답변을 들어봐야 알 것 같다.

 

최종 제출 코드

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

class Main {

  public static void main(String[] args) throws IOException {

    StringBuilder comp1 = new StringBuilder();
    StringBuilder comp2 = new StringBuilder();

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String INF = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
    String ans = INF;

    String input1 = br.readLine();
    String input2 = br.readLine();

    int star1 = -1;
    int star2 = -1;

    for (int i = 0; i < input1.length(); i++) {
      if (input1.charAt(i) == '*') {
        star1 = i;
        break;
      }
    }
    for (int i = 0; i < input2.length(); i++) {
      if (input2.charAt(i) == '*') {
        star2 = i;
        break;
      }
    }

    String str1 = input1.replaceFirst("\\*", "");
    String str2 = input2.replaceFirst("\\*", "");

    String head1 = str1.substring(0, star1);
    String tail1 = str1.substring(star1);
    String head2 = str2.substring(0, star2);
    String tail2 = str2.substring(star2);

    int S1 = str1.length();
    int S2 = str2.length();

    for (int i = 0; i <= S1; i++) {
      for (int j = i; j <= S1; j++) {
        comp1.append(head2).append(str1, i, j).append(tail2);
        int C = comp1.length();

        // 가지치기
        if (C >= ans.length()) {
          comp1.setLength(0);
          continue;
        }

        for (int p = 0; p <= S2; p++) {
          for (int q = p; q <= S2; q++) {
            comp2.append(head1).append(str2, p, q).append(tail1);

            // 가지치기
            if (C != comp2.length()) {
              comp2.setLength(0);
              continue;
            }

            if (comp1.toString().equals(comp2.toString())) {
              ans = comp1.toString();
            }
            comp2.setLength(0);
          }
        }
        comp1.setLength(0);
      }
    }

    System.out.println(ans.equals(INF) ? -1 : ans);
  }
}