[백준 1543번] 문서 검색(Java 풀이)

백준알고리즘 1543번 : 문서 검색

 

 

문서내에 특정 단어가 몇번이나 등장하는지 출력하는 문제이다.
처음에는 이중 for문을 사용하지 않고, 단일 for문을 이용하여 첫 글자부터 하나씩 check한 뒤에 한 글자라도 틀리면 다시 첫 글자부터 돌아가서 check하는 방식을 취했는데,
이러한 방식에는 문제가 있었다.
예를들어 단어의 길이가 길고, 뒷부분에서 틀린 글자가 발견되어 다시 첫글자부터 count를 하게되면, 문서내에 해당 단어의 패턴이 있었다고 하더라도 count를 못하게되어 찾지 못하는 불상사가 일어나게 된다.

예시로
abaabaa
abaa 가 그렇다.

따라서 문서의 길이와 단어의 길이의 최댓값을 고려해도 이중 for문으로 풀어도 괜찮겠다 싶어 푸는 방식을 변경하였다. 

풀이 과정

---

1. 이중 for문을 생성한다.
2. 문자의 길이만큼 문서의 글자가 모두 일치하면 count를 하나 늘린다.
3. count를 늘렸던 문서의 끝부분을 check하여, 중복되지 않는 선에서 문자를 반복적으로 check한다.

 

 

 

소스 ▽

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

public class Main {// No1543 : 문서 검색

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] docu = br.readLine().split("");
        String[] word = br.readLine().split("");

        int ans = 0;
        int cnt = 0;
        int fin = -1;
        for (int i = 0; i < docu.length - word.length + 1; i++) {
            for (int j = 0; j < word.length; j++) {
                if (word[j].equals(docu[i + j])) {
                    cnt++;
                }
            }
            if (fin < i && cnt == word.length) {
                ans++;
                fin = i + word.length - 1;
            }
            cnt = 0;

        }
        System.out.println(ans);
    }
}