[백준] 1543번 문서 검색

문제

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

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

입력

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

출력

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

 

더 간결하게 풀수 도 있었는데 아쉽다.ㅎㅎ

예를들어

ababababa 라는 str이 존재한다고 했을때,

aba가 중복없이 몇개 존재하는지 찾는 문제다.

 

 

그러니까 

 

aba bab aba

aba aba aba 이런식으로 같은 부분을 찾는 비교적 간단한 문제다.

 

문제는 

abababab 경우에는 어떻게 될까?

aba는 총 2개가 존재한다. 왜 그럴까?

 

바로 aba b aba b 이렇게 나누면 2개가 찾아진다.

그러면 여기서 의문이 드는게 위 식도 비슷하게 하면 더 나오지 않을까?

 

aba b aba ba 확인 결과 2개밖에 존재하지 않는걸로 확인되었다.

 

이렇게 총 갯수를 구하면 된다.

 

package _2020_07_01.B;

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

class Main {
	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 str = br.readLine();
		String find = br.readLine();

		long count = 0;

		try {
			for (int i = 0; i < str.length();) {

				String temp = "";
				for (int j = i; j < i + find.length(); j++) {
					temp += str.charAt(j);
				}

				if (find.equals(temp)) {
					count++;
					i += find.length();
				} else {
					i++;
				}
			}
		} catch (RuntimeException e) {
		}
		bw.write(count + "");

		bw.flush();

		bw.close();
	}
}

 

이 코드의 핵심 부분은

 

String temp = "";
 for (int j = i; j < i + find.length(); j++) {
    temp += str.charAt(j);
 }

바로 이부분이다.

이부분에서 temp를 만드는데 이게 바로 find 문자열과 똑같은것을 만드는곳이다.

 

그러면 초기값이 i일까?

그건 바로 0번째 시작할수도 있지만 그렇지 않을 수 도 있기 때문이다.

만약 무조건 0부터 시작이라고 작성해두면 중복값이 반드시 생기기 때문이다.

이를 방지하기 위해 i부터 시작하게 했다.

 

이와 마찬가지로 i+find.length()도 같은 맥락이다.

만약 find.length()만 존재하면 

find.length()가 3이라면 무조건 j의 길이는3이 될게 뻔하다.

이렇게 되면 j < find.legnth()라는 식은 거짓이기 때문에 동작하지 않을 수 있다.

그렇기 때문에 i를 추가해줘서 find.length()를 해주는것이다.

 

그리고 찾는 값이랑 비교했을때 같다. 그러면

i의 값을 find.length()만큼 증가 시켜주고

 

그렇지 않으면

i++만큼 증가 시켜준다.

이건 abababab 와 aba를 확인해보면 알 수 있다.

 

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String doc = sc.nextLine();
		String str = sc.nextLine();
		int cnt=0;
	
		while(doc.indexOf(str) > -1) {
			cnt++;
			doc = doc.substring(doc.indexOf(str)+str.length());
		}
		System.out.println(cnt);
	}
}

 

그렇게 어렵지도 않으면서도 간단한 코드인것 같다.

substring가 생각나지 않았다.ㅜㅜ

잘라내고, 또 잘라내고 -1보다 클때까지 아님 0보다 크거나 같은때까지 반복해주는 것 같다.