[SWEA] 3143. 가장 빠른 문자열 타이핑

문제

어떤 문자열 A를 타이핑하려고 한다.

그냥 한 글자씩 타이핑 한다면 A의 길이만큼 키를 눌러야 할 것이다.

여기에 속도를 조금 더 높이기 위해 어떤 문자열 B가 저장되어 있어서 키를 한번 누른 것으로 B전체를 타이핑 할 수 있다.

이미 타이핑 한 문자를 지우는 것은 불가능하다.

예를 들어 A=”asakusa”, B=”sa”일 때, 다음 그림과 같이 B를 두 번 사용하면 5번 만에 A를 타이핑 할 수 있다.
 

A와 B가 주어질 때 A 전체를 타이핑 하기 위해 키를 눌러야 하는 횟수의 최솟값을 구하여라.

 

풀이방법

n길이의 문자열 A와 m길이의 문자열 B가 주어진다.

 

n길이의 A문자열을 0번째 인덱스부터 탐색을 할 때, 

 

현재 탐색하고 있는 인덱스 i부터 i+m인덱스까지 문자가 B와 같다면 

 

다음 탐색할 인덱스는 i+m+1.

 

같지않다면 i+1를 탐색한다.

 

탐색한 횟수가 타이핑 최솟값이 된다.

 

소스코드

package samsung;

import java.util.*;

public class s_3143 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			String a = sc.next();
			String b = sc.next();
			int cnt = 0;
			int i = 0;
			while(i < a.length()) {
				if(i < a.length() - b.length() + 1) {
					String tmp = a.substring(i, i+b.length());
					if(tmp.equals(b)) i += b.length();
					else i++;
				}
				else i++;
				cnt++;
			}
			
			System.out.println("#" + t + " " + cnt);
		}
	}
}