[1543] 영어 검색 - 문자열, 브루트포스 (백준, 자바, 반례포함)

 

? 처음에 5분 만에 replace()로 풀었는데 77%에서 틀렸다. 따라서 startIdx로 wordLen 길이만큼잘라서 비교해서 통과했다.

근데 결국은 replace()로 하는 것도 맞는다 ?!

 

시행착오,,,,, 

정답만 보고싶다면 ? -> 제일 아래로 !

▶️처음 77%에서 틀렸던 코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String doc = br.readLine();
        String word = br.readLine();
        
        int docLen = doc.length();
        while (doc.length() > word.length()) {
            
            if (doc.contains(word)) {
                doc = doc.replace(word, ""); 
            } else {
                break;
            }
        }
        
        System.out.println((docLen - doc.length()) / word.length());
        br.close();
    }
}

이 코드로 모든 반례 다 해보고 AI로도 반례를 찾아달라고 했는데 절대 찾지 못 했다.

 

 

 

아 이런식으로 계속 반례 찾아달라고 했더니 우연히 일치하다고 ,, 자꾸

 

너무 쉽게 가려고 해서 그랬나 싶어서 정석으로 인덱스 기반 풀이로 변경해서 맞았다.

 

▶️인덱스 기반 브루트포스 적용해 푼 코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String doc = br.readLine();
        String word = br.readLine();
        
        int startIdx = 0;
        int answer = 0;
        
        int wordLen = word.length();
        
        while (startIdx <= doc.length() - wordLen) {
            String sub = doc.substring(startIdx, startIdx + wordLen);
            
            if (sub.equals(word)) {
                answer++;
                startIdx += wordLen;
            } else startIdx++;
        }
        
        System.out.println(answer);
        br.close();
    }
}

그러다 구글링을 해봤는데 replace()를 써서 맞은 코드를 발견했다.

너무도 간단하게 아래처럼 했더니 맞더라,,,,

 

▶️replace() 정답코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String doc = br.readLine();
        String word = br.readLine();
        
        int docLen = doc.length();
        
         doc = doc.replace(word, ""); 
        
        System.out.println((docLen - doc.length()) / word.length());
        br.close();
    }
}

내 코드와 비교하면

내 코드는 doc = doc.replace(word, “”) 를 while과 if가 감싸고 있다는 점만 달랐는데 그래서 오류가 난다고 하기엔 모든 조건을 다 검사하고 있다고 생각했다.

 

while(doc.length() > word.length()) 로 doc이 word보다 길 때만 치환 작업. (← 지금 생각해보니 이것도 같을 때는 비교하지 못 해 오류가 날 것이다 .ㅋㅋ )

 

if (doc.contains(word))로 doc에 word가 포함되어있어야만 replace 작업.

그렇지 않으면 빠르게 while 반복문 탈출.

 

사실 반복을 할 필요는 없었다. replace는 모든 일치하는 문자열을 찾아 치환해주기 때문에.

그래도 ? 틀릴 이유가 없었다고 생각했다.

 

 

대체 Y ? 모든 예제와 반례가 통과했는데 안 될까 .. 고민을 하다가 다음날까지 넘김.

너무 답답하고 반례를 기필코 찾고 싶었다.

 

그러면서 다른 여러 조건을 또 만들어봤다.

1. if (doc.contains(word)) doc = doc.replace(word, “”); //통과

2. if (doc.length() > word.length()) doc = doc.replace(word, “”);// 실패

    → doc “aa”, word “aa” 둘이 길이가 같을 때를 체크 못 함.

3. while (doc.contains(word)) doc = doc.replaceFirst(word, “”); //실패

replaceFirst로 바꿔본 이유는 while을 도는 이유를 굳이 만들어 보기 위해서였다.

처음 찾아진 문자열을 바꾸면 그다음에 나중에 나오는 단어를 찾기 위해 또 돌아야할테니까.

 

 

여기서 ! 어 그러면 치환돼서 원래는 떨어져있었다가 붙어버린 문자열이 word와 일치해버릴 수도 있구나 !라는 생각이 들었고 결국 아래와 같은 반례를 찾아내게 된다.

 

doc : “aabababb”

word : “ab”

정답 : 3

출력 : 4

 

 

결론은 replace를 통한 반복이 일어나게 되면 치환돼서 붙어버린 문자열들이 word랑 같아질 수도 있는 가능성 ..!

 

 

아니 이게 대체 뭐라고 지피티도 제미나이도 다 찾지 못하는 것인가 ?!?!?

다들 시간초과나 뭐 그런 얘기만 하고 반례를 절대 찾지 못 하더라 ,,,,,,

똑같이 고민하고 있던 분들께 조금이라도 도움이 되길 바라며 ,.,.,

 

 

▶️Solution Code

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

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

        String doc = br.readLine();
        String word = br.readLine();

        int docLen = doc.length();

        if (doc.length() >= word.length()) {
            doc = doc.replace(word, "");
        }

        System.out.println((docLen - doc.length()) / word.length());
        br.close();
    }
}

if 조건 까지 추가해서 시간을 조금이라도 더 단축하도록 해봤다.

 

 

마지막으로 나의 노력들 ..,