[BOJ] 백준 1543번 문서 검색 (Java)

#1543 문서 검색

난이도 : 실버 4

유형 : 그리디

1543번: 문서 검색

▸ 문제

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

▸ 출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

 

문제 풀이  

문서에 있는 검색하려는 문자열(pattern) 개수를 세어주면 되는 문제이다. 간단하면서 풀이법은 다양하다. 그리디는 현재의 선택에 가장 이득이 되는 경우만을 선택해야 한다. 그리디쪽의 사고를 확장시키기 위해 다음의 내용을 정리해봤다.

 

• 첫 번째, 무조건 문서 맨 앞의 인덱스부터 조회를 해야한다. 탐색의 수가 많으면 많을수록 검색되는 문자의 개수는 같거나 늘어나기 때문이다.  
• 두 번째, 현재 인덱스와 일치하지 않으면 1개의 문자열씩 삭제해가며 다음 인덱스를 탐색한다. 만약 2개, 3개씩 건너뛰면 첫 번째 조건에 위반되어 최적해를 구할 확률이 줄어들게 된다.

 

결론적으로 맨 앞의 인덱스부터 1칸씩 건너뛰며 문자열을 대조시켜야 그리디하게 최적해를 구할 수 있는 조건에 성립하게 된다.

 

풀이 코드 

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		String pattern = br.readLine();
		
		int cnt =0;
		while(line.length()>0) {
			if(line.startsWith(pattern)) {
				cnt++;
				line =line.substring(pattern.length());
			}else {
				line = line.substring(1);
			}
		}
		System.out.println(cnt);
	}
}