[그리디] 백준 1543번 문서 검색(Java)

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

1543번: 문서 검색

📚 문제

예를 들어, 문서가 ababababa이고 찾으려는 단어가 ababa라면 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다.

ababababa

그러나 동시에 셀 수는 없다. 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

 

📝 문제 해결

- 방법 1 : StringBuilder

"(동시에 셀 수 없으므로) 입력값에서 패턴값을 지워가며 카운트를 세주면 되겠다." 라고 생각해서 replaceFirst() 메소드를 사용하여 치환해주었으나 처음부터 차례대로 패턴값을 찾은 뒤 그 다음 인덱스부터 다시 찾아줘야하는데 이 경우 남은 문자열에서 다시 패턴값을 찾아 카운트가 다르게 나왔다. 

bbabaa  ba의 경우, bbabaa 로 카운트 값이 3이 출력 됨

 

그래서 StringBuilder의 delete 메소드를 사용하여 문자열을 아예 삭제해줬다.

public StringBuilder delete(int start, int end)

start~end 이전까지의 문자열을 삭제해준다.

import java.io.*;

public class BOJ1543{
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        sb.append(br.readLine());
        String regex = br.readLine();
        
        int idx, cnt = 0;
        
        while((idx = sb.toString().indexOf(regex)) != -1){
            sb.delete(0, idx+regex.length());
            cnt++;
        }
        
        System.out.println(cnt);
    }
}

 

- 방법 2 : Pattern 클래스의 matcher()  메서드 사용

import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.io.*;

public class BOJ1543{
    public static void main(String[]a) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        String regex = br.readLine();
        Pattern pattern = Pattern.compile(regex);
        Matcher matcher = pattern.matcher(input);
        int cnt = 0;

        while(matcher.find()) {
          cnt++;
        }
        System.out.println(cnt);
    }
}

[출처 : https://aorica.tistory.com/m/194 ]

•  Pattern

문자열로 정의한 정규 표현식을 Pattern 객체로 만들기 위해 Pattern 클래스의 compile() 메소드를 사용합니다. 컴파일된 패턴은 Matcher 객체를 만드는 데 사용되며, Matcher객체는 임의의 입력 문자열이 패턴에 부합되는지 여부를 판가름하는 기능을 가지고 있습니다.

static Pattern compile(String regex)	주어진 정규표현식으로부터 패턴을 만들어낸다(이를 ‘컴파일 한다’고 표현한다).
static Matcher matcher (CharSequence input)	입력 캐릭터 시퀀스에서 패턴을 찾는 Matcher 객체를 만든다.

 

• Matcher

Matcher 객체는 특정한 문자열이 주어진 패턴과 일치하는가를 알아보는데 이용됩니다.

boolean matches()

주어진 문자열 전체가 특정 패턴과 일치하는가를 판단한다.

1) 주어진 문자열 전체가 특정 패턴과 일치하는 가를 판단(matches).
2) 주어진 문자열이 특정 패턴으로 시작하는가를 판단(lookingAt).
3) 주어진 문자열에서 특정 패턴을 찾아낸다(find).
5) 특정 문자열을 찾아 새로운 문자열로 교체하는 기능도 제공된다.

[출처 : https://ktko.tistory.com/m/entry/JAVA-%EC%9E%90%EB%B0%94%EC%9D%98-%EC%A0%95%EA%B7%9C%ED%91%9C%ED%98%84%EC%8B%9D-Pattern-Matcher ]

 

- 방법 3 : replace

replace 메소드를 사용하여 입력값에서 패턴값을 지워준 뒤,

처음 입력값의 길이에서 남은 입력값의 길이를 빼주고

패턴값의 길이로 나눠주면 총 몇번의 패턴값이 지워졌는지 알 수있다.

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

public class BOJ1543 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		String regex = br.readLine();
        
		int size = input.length();
		
		input = input.replace(regex, "");
		System.out.println((size - input.length()) / regex.length());
	}
}

[출처 : https://comain.tistory.com/m/313 ]