BOJ - 1543 문서 검색

Problem

---

Solve

주어진 문서에서 찾고자 하는 단어의 개수를 구하는 문제.

주어진 문서와 비교하려는 단어를 각 문자씩 비교한다면 (2500*50)*2500으로 시간초과가 발생할것이다.

문자열에서 startWith()메서드를 이용하면 쉽게 구할 수 있다.

startWith()는 시작 문자열에서 비교하려는 문자열(regex)와 비교해서 regex문자열과 동일하다면 true를 아니라면 false를 반환한다.

주어진 문서를 돌면서 startWith()으로 regex를 비교하고 동일하다면 주어진 문서를 비교 시작한 문자열부터 regex의 길이만큼 잘라서 다시 비교한다.

---

Code

public class 문서검색 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String line = br.readLine();
		String pattern = br.readLine();

		int count=0;
        //문서의 길이가 0이 될때까지 비교
		while(line.length() > 0){
        	//해당 문자열이 regex와 동일하다면 문서를 regex길이만큼 잘라준다.
			if(line.startsWith(pattern)){
				count++;
				line = line.substring(pattern.length());
			}
           	//동일하지 않다면 문서의 맨 앞부분만 제거한다.
            else{
				line = line.substring(1);
			}
		}

		bw.write(String.valueOf(count));
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference