[백준] 1543번: 문서 검색(그리디, 완전탐색)

https://www.acmicpc.net/problem/1543

1543번: 문서 검색

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String str = scan.nextLine();	// 문서
		String word = scan.nextLine();	// 검색하고 싶은 단어
		int count = 0;	// 단어가 중복되지않고 등장하는 횟수
		int index = 0;	// 문서에서 검색할 단어를 찾을 때 시작할 인덱스의 값
         
		for(int i=index; i<=str.length() - word.length(); i++) {
			boolean flag = true;	// 중복된 단어 등장하는지 판별
			for(int j=0; j<word.length(); j++) {
				
				// 문서와 검색하려는 단어가 다를경우
				if(str.charAt(i+j) != word.charAt(j)) {
					flag = false;
					break;
				}
			}
			
			/*
			 * 문서와 검색하는 단어가 같을 경우
			 *  - 등장 횟수 +1
			 *  - 다음 등장하는 횟수를 찾기위해 인덱스를 문서의 길이만큼 더한다.
			 */
			if(flag) {
				count ++;	
				index += word.length();
				i = index-1;
			}
			// 문서와 검색하는 단어가 다를 경우
			// 바로 다음 알파벳부터 탐색하면 되므로 인덱스를 +1 한다.
			else {
				index ++;
			}
		}
		System.out.println(count);
		scan.close();
	}

}

풀이

주어진 문서(문자열)에서 어떤 단어가 총 몇번 등장하는지 중복을 제외하고 세아리면 된다.

문서 : ababababa

단어 : aba

라고 가정했을 때, 문서의 길이는 9, 단어의 길이는 3이다. 

밖 for문을 문서의 길이 - 단어의 길이 만큼 반복하는 이유는, 위의 예시에서 ababababa <- 빨간색 만큼만 반복하면서 판단하면 되기 때문이다.

 

1. 문서와 단어가 다른경우

문서: b

단어: a

flag 변수를 false로 저장한 후 바로 안쪽 for문을 빠져나간다.

 

 

2. 안쪽 for문(문서와 단어가 동일한지 아닌지 판단)이 끝났을 경우,

만약 문서와 단어가 동일해서 flag가 true일 경우

중복을 뛰어넘기 위해 index 값을 문서의 길이만큼 더한다.

ababababa

aba 

위에서 앞에 3개는 동일하므로, 다음꺼(bababa)부터 판단하면 되므로 3을 더한다.

i에 index - 1 을 더한 이유는 밖 for문에서 +1을 해주기 때문에 -1을 더해준다.

 

만약 문서와 단어가 달라서 flag가 false인 경우

이때는 문서의 바로 다음 문자부터 탐색하기위해 index를 ++해준다.

 

* 문제에서 조심할 점은 문서와 단어는 알파벳 소문자와 공백으로 이루어져있다고 나와있다.

* 따라서 공백을 주의해 문서와 단어를 입력받을때 next() 가 아닌 nextLine() 로 입력받아야 한다.