[백준](2024) 문서 검색 (설명/코드/정답)

 

문제 링크 : https://www.acmicpc.net/problem/1543

 

 

난이도		알고리즘
	실버5	문자열, 완전탐색

 

 

1. 요구 사항 이해

시간, 메모리 제한 : 2초 / 128MB

 

영어로만 이루어진 문서에 입력한 단어가 몇 번 등장하는지 식별

문서 최대 2,500자

단어의 최대 길이 50

문서와 단어의 입력은 소문자 또는 공백

중복X

 

 

 

 

 

2. 설계/검증 

문서와 단어의 입력

- nextLine()

문서를 순회하며 단어의 순서와 일치하면 리턴

단어의 철자 인덱스가 중복 X

- 조회 성공 후 word의 길이만큼 이동한 후 다음 조회 시작  

 

 

시간 복잡도	최악의 경우	공간 복잡도
O(N * M)	125,000	O(N + M)

 

 

 

 

3. 정상 코드

이중 for문

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        String document = scan.nextLine();
        String word = scan.nextLine();
        int count = 0;

        // 문서를 순회하며 단어가 등장하는지 검사
        for (int i = 0; i < document.length(); i++) {
            boolean isMatch = true;
            // 단어를 순회하며 각 문자가 일치하는지 확인
            for (int j = 0; j < word.length(); j++) {
                int documentIndex = i + j; // 현재 위치부터 단어의 길이만큼 이동한 인덱스 계산
                //문서 범위를 벗어나거나 현재 운자가 단어의 문자와 일치하지 않는 경우
                // 플래그를 flase로 설정하고 반복문 탈출
                if (documentIndex >= document.length() || document.charAt(documentIndex) != word.charAt(j)) {
                    isMatch = false;
                    break;
                }
            }
            //현재 위치부터 단어의 길이만큼 일치하는 경우,
            //등장횟수 증가 및 다음 검색을 위해 i를 단어의 길이만큼 이동
            if (isMatch) {
                count++;
                i += word.length() - 1; // 외부 for 반복문에서 i++조건 때문에 단어 길이만큼 이동시키지 위해서는 -1을 적용
            }
        }
        System.out.println(count);
    }

 

 

indexOf() 사용

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String document = scan.nextLine();
        String word = scan.nextLine();

        int count = 0; // 등장 횟수를 저장할 변수
        int fromIndex = 0; // 검색을 시작할 인덱스

        // indexOf 메서드를 이용하여 문서에서 단어의 등장을 찾고,
        // 등장할 때마다 카운트를 증가시킴
        while ((fromIndex = document.indexOf(word, fromIndex)) != -1) {// 할당과 동시에 조건을 검사
            fromIndex += word.length(); // 다음 검색을 위해 fromIndex를 단어의 길이만큼 이동
            count++;
        }

        System.out.print(count);

    }
}

 

replace() 사용

import java.util.*;

public class Main{

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        String document = scan.nextLine();
        String word = scan.nextLine();

        String remainingAfterErasing = document.replace(word, "");
        int erasedLength = document.length() - remainingAfterErasing.length();
        int count = erasedLength / word.length();
        System.out.println(count);
    }

}

 

 

4. 처리 과정 추적 코드

 

이중 for문

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        System.out.print("문서를 입력하세요: ");
        String document = scan.nextLine();
        System.out.print("검색할 단어를 입력하세요: ");
        String word = scan.nextLine();
        int count = 0;

        for (int i = 0; i < document.length(); i++) {
            System.out.println("\n----------------------------------");
            System.out.println("현재 i: " + i);
            boolean isMatch = true;

            for (int j = 0; j < word.length(); j++) {
                System.out.println("\n처리 중인 j: " + j);
                int documentIndex = i + j;

                // 인덱스가 범위를 벗어나거나 문자가 일치하지 않는지 확인
                if (documentIndex >= document.length() || document.charAt(documentIndex) != word.charAt(j)) {
                    isMatch = false;
                    break;
                }

                System.out.println("현재 문서 문자: " + document.charAt(documentIndex));
                System.out.println("현재 단어 문자: " + word.charAt(j));
            }

            if (isMatch) {
                System.out.println("\n일치하는 문자열 발견!");
                count++;
                i += word.length() - 1; // 다음 가능한 시작 위치로 건너뛰기
            }
        }

        System.out.println("\n----------------------------------");
        System.out.println("단어의 총 출현 횟수: " + count);
    }
}

 

 

 

 

추가 정리

 

indexOf

문자열에서 지정된 부분 문자열이 처음으로 나타나는 위치(인덱스)를 반환합니다.

찾았을 경우 찾은 시작 위치(인덱스)를 반환 찾지 못한 경우 -1을 반환