백준 1543 문서 검색 자바 풀이

[백준/자바] 1543

 

📌 문제 

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.
세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

 

 

⚔ 입력

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

 

 

📣 출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

 

 

 

 

---

 

 

 

💡 코드 구현

 

처음 구현한 알고리즘 

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

public class Main {
	private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

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

		// StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		String word1 = bufferedReader.readLine();
		String word2 = bufferedReader.readLine().trim();

		int answer = 0;
		int secondWordCountIndex = 0;
		int rollbackPoint = 0;
		boolean isRollbackSet = false;
		char firstAlphabet = word2.charAt(0);

		for (int i = 0; i < word1.length(); i++) {
			if (isAlphabetMatch(word1, word2, secondWordCountIndex, i) || isAlphabetMatch(word1, word2, secondWordCountIndex=0, i)) {

				if (word1.charAt(i) == firstAlphabet && secondWordCountIndex !=0 && !isRollbackSet){
					rollbackPoint = i-1;
					isRollbackSet= true;
				}

				if (isAllMatch(word2, secondWordCountIndex)) {
					secondWordCountIndex = 0;
					answer++;
					rollbackPoint=0;
					continue;
				}
				secondWordCountIndex++;
				continue;
			}
			if (rollbackPoint !=0){
				i = rollbackPoint;
				rollbackPoint=0;
				isRollbackSet= false;
			}
		}

		System.out.println(answer);
	}

	private static boolean isAllMatch(String word2, int secondWordCountIndex) {
		return word2.length() == secondWordCountIndex + 1;
	}

	private static boolean isAlphabetMatch(String word1, String word2, int secondWordCountIndex, int i) {
		return word1.charAt(i) == word2.charAt(secondWordCountIndex);
	}
}

 

단순하게 문서를 순서대로 탐색하며 알파벳을 발견하면 그 인덱스를 주욱 이어나가면서 탐색하고, 성공하면 카운팅한다. 

 

이때 실패시에 롤백이 되어 앞에서부터 다시 되도록 flag를 이용했다. 

 

사실 계속 틀려서 수정에 수정을 거듭했지만 결국 순차 탐색 + 롤백 알고리즘으로는 풀지를 못했다. 

나와있는 모든 반례를 전부 넣어서 있는 예시로는 통과했지만 실제에서는 통과하지 못했다. 다른 반례가 어떤 것이 있는지 모르겠다.

딱 봐도 코드가 지저분하고 깔끔하지 못해서 별로 좋지 못한 구현이라고 생각한다. 

 

주요 반례 :

- aabb / ab

- ababaa / abaa

- abababc / ababc 

- aababa / aba

=> 전부 통과 

 

 

 

 

방법을 바꿔서 단어를 통째로 검사해주도록 구현했다. 

 

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

public class Main {
   private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

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

      // StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      String document = bufferedReader.readLine();
      String word = bufferedReader.readLine();

      int count = 0;
      for (int i = 0; i < document.length() - word.length() +1; i++) {
         if (document.startsWith(word, i)){
            count++;
            i = i + word.length() -1;
         }
      }

      System.out.println(count);
   }
}

 

 

 

 

문제가 틀릴 때 접근 자체가 틀린 경우가 있다. 이번 경우에도 그랬던 거 같다. 

 

간단하게 풀 수 있는 문제도 접근이 틀려버리면 시간만 소요되고 복잡해지기만 하고 결국 해결도 못한다. 이처럼 패러다임 자체를 변환해주는 발상의 전환 같은 것으로 문제를 해결 하는 경우들이 있다. 

 

 

---