백준] 11008 - 복붙의 달인(ACM-ICPC Regionals)

시간 제한 : 2초

메모리 제한 : 256MB

 

문제
한신이는 대학교에서 "복붙의 달인"으로 유명하다. 한신이는 타이핑 속도가 느리기 때문에 대학에서 가능한 모든 일을 복붙으로 해결한다. 그는 n개의 문자를 입력하는데 있어서 n초의 시간이 걸리지만 뛰어난 "붙여넣기" 스킬을 이용하면 어떠한 개수의 문자도 단 1초만에 타이핑 할 수 있다. 만약 한신이가 "bana"를 복사한 상태에서 "banana"를 타이핑한다면, "bana" 붙여넣기 1초, 'n' 입력, 'a' 입력으로 총 3초가 걸린다. 한신이가 클립보드에 저장한 p를 알고 있을 때 s를 입력하는데 걸리는 최소 시간을 계산해보자!

입력
첫 번째 줄에는 테스트케이스의 개수 T(T ≤ 25)가 입력된다. 각 테스트케이스는 한 줄에 2개의 문자열 s와 p가 공백으로 구분되어 입력되며 한신이는 p를 복사하여 s를 만들어 내는 것을 목표로 한다. s의 최대 길이는 10,000이고, p의 최대 길이는 100이다.

출력
각 테스트 케이스에 맞는 한신이가 p를 이용하여 s를 타이핑할 때 걸리는 최소 시간(초 단위)을 출력하라!

 

 

소스코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(void)
{
	int T;
	cin >> T;
	while (T--)
	{
		int ans = 0, sLen, pLen;;
		string s, p;
		cin >> s >> p;

		sLen = s.length();
		pLen = p.length();
		if (pLen == 1)
		{
			ans = sLen;
		}
		else
		{
			string tmp = "";
			while (1)
			{
				int subLen = s.length();
				int idx = s.find(p);
				if (idx == string::npos)
				{
					tmp += s;
					break;
				}

				ans++;
				tmp += s.substr(0, idx);
				s=s.substr(idx+pLen, subLen - pLen);
			}
			ans += tmp.length();
		}
		cout << ans << '\n';
	}
}

 

 

 

Tip

문자열 s에서 p 패턴을 찾아서 최대한 횟수를 줄여나가는 방법으로 접근했다.

p의 길이가 1이면 패턴 찾는 것이 무의미해서 s의 길이가 정답이다.

 

패턴 p를 s에서 찾아내면 문자열의 처음부터 해당 문자열까지 싹 지워버리는 식으로 접근했다.

대신 그 과정에서 아래와 같은 경우가 발생할 수 있는데, 

 

s="asakusa"

p="sa"

 

첫번째 "sa"를 찾아서 삭제 작업을 하면 s="kusa"가 되는데, a라는 문자까지 같이 사라졌다. 그래서 패턴을 지우는 과정에서 사라지는 문자열들을 tmp 문자열에 계속 붙여나가면서 '복사 붙여넣기'로 입력할 수 없는 문자열들을 모아두는 작업을 했다.