[알고리즘 문제] 백준1543 - 문서검색

문제는 문자열에서 단어가 중복없이 최대 몇번 나오는지 검사하는 문제이다.

여기서 중복이란 문자열 ababababa에서 aba를 찾을 때, [aba]b[aba]ba 이렇게 찾은 문자열에서 index가 겹치게 사용할 수 없다는 것이다.

 

아이디어는 문서의 0번째 인덱스부터 끝까지 단어의 크기만큼 비교하는 것이다. 

aba와 aba

bab와 aba

aba와 aba

bab와 aba

baba와 aba

aba와 aba

 

시간복잡도는 O(N^2)지만 입력받는 문자열의 길이가 길지 않기 때문에 신경쓰지 않아도 될 것 같았다.

 

그리고 하나씩 비교하는데 만약 단어가 같다면 단어크기만큼 index를 증가하고 다시 비교한다. 단어가 같지 않으면 그냥 index++를 한다.

ababababa에서 처음 [aba]bababa는 aba와 같기 때문에 다음 비교할 때는 aba[bab]aba부터 검사하는 것이다.

 

그리고 이 문제에서 애매한 부분은 입력받는 문서와 단어가 소문자와 "공백"으로 이루어져 있다는 것이다.

그렇기 때문에 공백도 같이 입력받아야 하는데, 그냥 next()로 입력받으면 공백을 무시해버린다. "asd qwe zxc"를 입력하면 asd/qwe/zxc로 입력받아 지게 된다. 그렇기 때문에 한줄 단위로 입력받는 nextLine()를 사용해야 한다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String doc = sc.nextLine();
        String word = sc.nextLine();

        doc = doc.replaceAll("\\s", "");
        word = word.replaceAll("\\s", "");

        int docLength = doc.length();
        int wordLength = word.length();

        int start = 0;
        int count = 0;
        int charSameCount;

        while (start <= docLength - wordLength) {
            charSameCount = 0;
            for (int i = 0; i < wordLength; i++) {
                if (doc.charAt(start + i) == word.charAt(i)) {
                    charSameCount++;
                }
            }
            if (charSameCount == wordLength) {
                count++;
                start += wordLength;
            } else {
                start++;
            }
        }

        System.out.println(count);
    }
}