[BOJ/JAVA] 1543번: 문서 검색

1543번: 문서 검색

1543번: 문서 검색

키워드

그 단어가 최대 몇 번 중복되지 않게 등장하는지

---

구현

단어의 길이는 50이고, 문서의 길이는 최대 2500이다. 따라서 단순 문자열 비교 알고리즘을 사용하여 구현해도 무방하다.

가장 앞부터 단어를 만족하는지 체크하고, 그 단어 길이 이후 인덱스 부터 다시 문자열 비교 알고리즘을 사용한다.

왜 가장 앞 부터 단어를 만족하는지 체크하는가?

→ 최대 몇 번 중복되지 않게 등장하는지 체크하기 위해서,

다음 예시를 보자

문서 : AAAAAAAA

단어 : AA

[0] 인덱스로 시작해도 만족하고, [1] 인덱스로 시작해도 만족한다.

[0] 인덱스 부터 시작을 체크한다면, [2] 인덱스 부터 다시 찾기 시작한다.

[1] 인덱스 부터 시작을 체크한다면, [3] 인덱스 부터 다시 찾기 시작한다.

[0] 인덱스 부터 찾기 시작하면 4개가 나오고

[1] 인덱스 부터 찾기 시작하면 3개가 나온다.

따라서 우리는 가장 낮은 인덱스 부터 중복되지 않게 찾기 시작해야 한다.

---

코드

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

public class java_1543 {
    static String docs;
    static String word;

    // docs에서 index부터 시작하는 부분 문자열이
    // word와 같은가?
    static boolean isIn(int index) {

        for (int i = 0; i < word.length(); i++) {
            if (word.charAt(i) != docs.charAt(i + index)) {
                return false;
            }
        }

        return true;
    }

    // docs 에서 word가 중복되지 않고, 몇 번 들어가는지 체크
    static int findCount() {
        int count = 0;

        // docs : abab == 4
        // word : ab == 2

        // index는 2까지만 해도 상관 없음

        // => docs.length() - word.length() + 1
        for (int i = 0; i < docs.length() - word.length() + 1;) {
            // i번 부터 탐색을 시작했을 때, 단어가 맞아 떨어진다면...
            // i+단어길이 이후부터 탐색하자
            if (isIn(i)) {
                count++;
                i += word.length();
            } else {
                i++;
            }
        }

        return count;
    }

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

        // 문서
        docs = br.readLine();
        // 찾고 싶은 단어
        word = br.readLine();

        // 중복되지 않게 선택
        // 중복되지 않게 선택은 -> 앞부터 찾아나가고, 찾으면 그 다음부터 또 찾는다. n^2
        int result = findCount();

        System.out.println(result);

        br.close();
    }
}

---