[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 조건 까지 추가해서 시간을 조금이라도 더 단축하도록 해봤다.
마지막으로 나의 노력들 ..,
