문제 설명

세준이는 영어로 이루어진 문서에서 특정 단어가 몇 번 등장하는지 찾는 프로그램을 만들려고 한다.

하지만 이 문제에서는 다음 조건이 있다.

• 겹치는 경우는 세지 않는다.

예를 들어

문서: ababababa
단어: aba

가능한 위치는 다음과 같다.

0번째: aba
2번째: aba
4번째: aba

하지만 문제 조건에 따라 겹치는 경우는 동시에 세지 못한다.

그래서 가능한 경우는

0번째
3번째

총 2번이다.

---

입력 조건

• 첫째 줄: 문서 문자열
• 둘째 줄: 찾을 단어

문서 길이

최대 2500

단어 길이

최대 50

문자 구성

알파벳 소문자 + 공백

---

출력

문서에서 겹치지 않게 등장하는 최대 횟수를 출력한다.

---

입력 예시

ababababa
aba

출력 예시

2

---

문제 해결 아이디어

이 문제의 핵심은

겹치지 않게 단어를 찾는 것

이다.

문서를 왼쪽부터 탐색하면서

1. 현재 위치에서 단어가 시작하는지 확인
2. 같다면 개수 증가
3. 단어 길이만큼 건너뛰기

이 과정을 반복하면 된다.

---

내가 작성한 풀이

문자열을 직접 잘라 비교하는 방식으로 구현했다.

현재 위치에서 단어 길이만큼 잘라서
찾는 단어와 같은지 비교한다.

같다면

count++

하고

단어 길이만큼 이동

하여 겹치는 경우를 방지한다.

코드

import java.util.*;

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

        String input = sc.nextLine();
        String input2 = sc.nextLine();
        int count = 0;
        
        for(int i = 0; i < input.length(); i++) {

            if(i + input2.length() <= input.length() &&
               input.substring(i, i + input2.length()).equals(input2)) {

                count++;
                i += input2.length() - 1;
            }

        }

        System.out.println(count);
    }
}

---

강의 풀이 방식

강의에서는 Java의 문자열 검색 함수인

indexOf()

를 사용하여 문제를 해결했다.

동작 방식

1. indexOf()로 단어가 등장하는 위치 찾기
2. 찾으면 count++
3. 시작 위치를 단어 길이만큼 이동
4. 다시 검색

코드 흐름

int count = 0;
int startIndex = 0;

while(true) {

    int findIndex = doc.indexOf(word, startIndex);

    if(findIndex < 0)
        break;

    count++;
    startIndex = findIndex + word.length();

}

---

두 풀이 방식 비교

방식	설명
substring 비교	직접 문자열을 잘라 비교
indexOf 사용	문자열 검색 함수 활용

두 방법 모두

겹치지 않게 탐색

한다는 점에서 핵심 아이디어는 동일하다.

---

시간 복잡도

문서 길이를 N이라고 하면

O(N)

문자열을 왼쪽부터 탐색하면서
필요한 위치만 검사하기 때문에 충분히 빠르게 동작한다.

문제에서 주어진 최대 길이

2500

에서도 시간 제한에 걸리지 않는다.

---

핵심 개념 정리

이 문제에서 중요한 개념은 다음과 같다.

1. 문자열을 왼쪽부터 탐색
2. 단어가 발견되면 단어 길이만큼 이동
3. 겹치는 경우는 세지 않는다

문자열 문제에서 자주 등장하는
문자열 탐색 패턴을 연습할 수 있는 문제이다.