백준 2195번 문자열 복사(C++)

2195번: 문자열 복사

문제 분석

원본 문자열 S와 이 문자열을 부분 복사한 집합인 새로운 문자열 P간의 관계에 대한 문제이다.

 

문제는 copy(s, p)라는 함수를 사용해서 복사하는데, 's번 문자부터 p개의 문자를 P에 복사해서 붙인다'라는 의미이다.

ex) S = "abc", P = "abcbcbb"라 할 때, copy(1, 3) / copy(2, 2) / copy(2, 1) / copy(2, 1) 를 수행하여 P를 만들 수 있다.

1단계 : "abc" -> 2단계 : "abcbc" -> 3단계 : "abcbcb" -> 4단계 : "abcbcbb"

 

이때 최소한으로 사용한 copy함수의 횟수를 구하는 문제이다. 

 

문제 자체는 생각보다 쉽다. 최적의 효율을 탐색하는 '그리디 알고리즘'을 사용하는 문제이기에 방법만 잘 강구한다면, 쉽게 풀 수 있다.

 

핵심은 2가지이다.

 

💡S문자열은 P문자열에서 시작점으로부터 최대한 많이 같은 경우의 수를 찾아한다. 💡

 

💡S문자열에서 같은 알파벳이 존재하는 경우를 고려해야한다. 💡

---

문제 풀이

1.  💡S문자열은 P문자열에서 시작점으로부터 최대한 많이 같은 문자가 찾아한다. 💡

 

당연히 S에서 복사한 문자열의 한 문자를 시작으로 최대한 많은 문자들이 같아야 최소한으로 copy함수를 사용할 수 있다.

 

ex) S = "123", P = "123"일 때, copy(1, 3)이면 최소한이지만, copy(1,1) copy(2,2) copy(3,3)은 3번의 copy함수를 사용한다.

 

2. 💡S문자열에서 같은 알파벳이 존재하는 경우를 고려해야한다. 💡

 

사실 2번이 문제에서 가장 중요한 핵심이라고 생각한다. 문제에서의 예를 들어서 설명해보겠다.

 

문제에서는 S="abaabba", P="aaabbbabbbaaa"라고 가정한다. 

 

이 때, P의 첫 시작 문자인 "a"와 같은 문자를 S에서 찾기 시작할 것이다.

-> P의 문자와 같은 위치 = 1, 3, 4, 7

 

동시에 4개의 "a"가 겹치는 모습을 알 수 있다. 그렇다면 이 중에서 겹친 "a"이후의 문자가 같은지 확인한다면 될 것이다!

-> 각 위치 1 3 4 7의 다음인 2 4 5 7을 확인한다! (7은 문자열의 끝이기에 더이상 확인하지 않음)

 

❎ S.copy(1, 2) = "ab"

✅ S.copy(1, 2) = "aa" 오직 3번 위치가 다음 문자인 "a"를 가지기에 2개가 겹치게 된다.

❎ S.copy(4, 2) = "ab"

❎ S.copy(7, 2) = "a" (뒤의 문자가 없음)

 

P의 시작점과 같은 S의 위치를 확인하고, S의 다음 위치와 P의 다음 위치가 같은지 확인하며
가장 많이 겹치는 위치가 copy함수를 최소한으로 사용할 수 있게 된다.

 

아래의 코드를 잠깐 리뷰하자면,

• temp : 다음 index를 가리키기 위한 장치이기에 1로 초기화하였다. 만약 S와 P의 다음 문자가 같다면, temp가 그 다음 위치를 가리키도록 한다.
• point : 다음 문자가 같은지 확인하는 stack용 장치이다. 다음 문자가 서로 같다면, point를 증가시켰다.

사실 temp와 point는 한번에 묶어서 사용하는 코드가 제일 최적화된 코드이지만, 필자가 햇갈리기에 직접 분리시켜서 사용하였다.

 

C++ 풀이

#include <iostream>
#include <string>

using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	string S, P;
	cin >> S >> P;

	int index = 0, copy = P.length(); 
    // index : P의 index, copy : P의 길이.
	while (index < P.length()) {
		int max = 0;

		for (int i = 0; i < S.length(); i++) {
			int point = 0; // 가장 많이 복사할 수 있는 양
			int temp = 1; // 다음 char을 가리키는 인덱스
			if (S[i] == P[index]) {
				while (i + temp < S.length() && index + temp < P.length() && S[i + temp] == P[index + temp]) {
					point++;
					temp++;
				}

				if (max < point) {
					max = point;
					i += temp;
				}
			}
		}

		copy -= max; // 복사할 수 있는 문자열만큼 수가 줄어듬.
		index += max; // 복사할 수 있는 문자들은 index를 확인할 필요 없기에 증가
		index++;
        
	}

	cout << copy;
    
	return 0;
}

코드 리뷰는 언제나 환영입니다!