(JAVA) 백준 1543번 : 문서 검색

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

1543번: 문서 검색

 

간단한 문자열 문제!

 

String 을 사용하는 방법

StringBuilder를 사용하는 방법

 

이 있는데, 나는 StringBuilder를 사용했다.

 

 

String과 StringBuilder의 차이는 여러가지가 있지만

 

가장 큰 차이점은

 

String은 immutable(불변성) 의 성질을 갖고 있어

문자열 연산에는 효율적이지 않다고 한다.

 

그와는 다르게 문자열을 append, delete 하는 작업에 있어서는 

StringBuilder를 사용하는 것이 효율적이다.

 

*** 연산이 많지 않으면 차이가 크지 않다.

*** String과 StringBuilder에 대해 포스팅을 해보겠다.!

 

 

 

매커니즘은 단순하다.

String 클래스 함수 중 하나인

 

.indexOf(String str) : 파라미터로 받은 String(문자열)이 앞에서부터 탐색해서 처음 발견되는 인덱스를 리턴한다.

존재 : 인덱스,   존재 X : -1

 

을 사용했다.

 

 

이를 while문을 통해 -1이 나오면 while문을 벗어나고,

 

그 전까지는 delete를 통해 해당 문자를 제거한 다음

 

제거하고 남은 문자를 다시 탐색한다!

 

 

 

** 나도 이 예외를 생각하지 못하고 풀었었는데,

 

이 문제는 앞에서부터 순차적으로 문자를 읽어가며 단어가 포함되어있는지 찾는 것이다.

중간에 문자를 발견했다고 다시 처음으로 돌아가서 문자를 다시 찾지 않는다는 뜻이다.

 

 

** 그렇기 때문에

 

delete 시 해당 문자만 제거하는 것이 아니라

문자열의 맨 처음부터 해당 문자가 포함된 첫 인덱스 + 문자의 길이 만큼 제거해야 한다.

 

 

** 대표적인 반례 사례

aabb

ab

- 정답 : 1

- Worst : 2 (지우고 다시 처음부터 탐색하게 되면)

 

 

 

소스코드

---

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));
		
		StringBuilder sb = new StringBuilder();
		
		sb.append(br.readLine());
		String str = br.readLine();
		
		int count = 0;
		int startIndex = 0;
		int len = str.length();
		while((startIndex = sb.toString().indexOf(str)) != -1) {
			sb.delete(0, startIndex + len);
			count++;
		}
		
		System.out.println(count);
	}
}