[Java] 백준 1543번 [문서 검색] 자바

: ) YOUNG·2022년 4월 20일
2

알고리즘

목록 보기
107/417
post-thumbnail

백준 1543번
https://www.acmicpc.net/problem/1543


문제

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

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


입력

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


출력

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


예제 입력

ababababa
aba

예제 출력

2

생각하기

문자열에서 내가 원하는 문자열을 찾는 방식입니다.
근데, 중복은 되지 않으니까 찾은 문자는 문자열에서 지우면서 나아가면 됩니다.

여기서 String 연산을 할 때
즉, append, delete는 일반 String보다는 StringBuilder가 좋다는 말을 듣고 입력부터
StringBuilder를 사용해서 입력을 받았습니다.

String은 immutable(불변성)의 성질을 가지고 잇어서 문자열 연산에는 효율적이지 않고

StringBuilder의 append, delete를 사용한다면 훨씬 효율적인 작업을 할 수 있습니다.

동작

		int count = 0;
		int startIndex = 0;
		int find_len = find.length();
				
		// find와 똑같은 문자열을 StringBuilder에서 찾아서 해당 index값을 가져옴
		// 이후에 StringBuilder에서 delete작업을 하면됨.
		// 그리고 count값 증가를 하면 답을 구할 수 있음
		while((startIndex = sb.toString().indexOf(find)) != -1) {
			sb.delete(0, startIndex + find_len);
			count++;
		}
		
		System.out.println(count);

search() 메소드를 통해서 전체 문자열인 sb에서
find가 포함되어 있는지 찾습니다.

찾는 방법은 indexOf(find)를 사용해서 sb와 같은 문자가 있으면 index값을 반환받아 해당 시작 인덱스 startIndex에서 find의 문자열 길이 만큼 delete작업을 하면 됩니다.




코드

import java.io.*;

public class Main {
	static 	StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb.append(br.readLine());
		String find = br.readLine();

		search(find);

	} // End of main

	static void search(String find) {

		int count = 0;
		int startIndex = 0;
		int find_len = find.length();

		while((startIndex = sb.toString().indexOf(find)) != -1) {
			sb.delete(0, startIndex + find_len);
			count++;
		}

		System.out.println(count);
	}
} // End of class

0개의 댓글