백준 16472 : 고냥이

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

16472번: 고냥이

 

투포인터로 해결할 수 있는 문제다.

 

나는 DP라고 생각하면서 DP로 풀었는데, 원리는 투포인터와 비슷하다. 다만 dp배열을 선언하고 값을 저장하는데 메모리를 사용하므로 투포인터보다 공간복잡도가 더 크다.

 

#include <iostream>
#include <algorithm>
#include <bitset>

using namespace std;

int n;
string s;
int dp[100'000];
int last_idx[26];

void solution() {
	int cur, seq_cnt;
	int min_idx, cur_front;
	char target;
	bitset<26> bs;

	cin >> n >> s;

	for (int i = 0; i < 26; i++)
		last_idx[i] = 1e6;

	seq_cnt = 0, cur_front = 0;
	for (int i = 0; i < s.size(); i++) {
		cur = s[i] - 'a';
		// 현재 cur이 범위 안에 있는지 확인
		if (!bs[cur]) {
			// 범위 안에 있고 범위 안의 문자의 종류가 N개보다 작으면 단순히 문자 추가
			if (bs.count() < n)
				bs[cur] = 1;
			// N개가 가득차있으면 각 문자별로 가장 마지막 인덱스를 확인해서
			// 제일 앞에 있는 문자를 제거하고 새로운 문자 삽입
			else {
				// 가장 앞에있는 문자 찾기
				min_idx = *min_element(last_idx, last_idx + 26);
				target = s[min_idx] - 'a';

				// 범위 축소
				seq_cnt -= min_idx - cur_front + 1;
				cur_front = min_idx + 1;

				last_idx[target] = 1e6;
				bs[target] = 0;
				bs[cur] = 1;
			}
		}
		// 각 문자별로 가장 마지막에 발견된 idx 저장
		last_idx[cur] = i;
		// 현재까지 범위의 크기 저장
		dp[i] = ++seq_cnt;
	}
	cout << *max_element(dp, dp + s.size());
}

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

	return 0;
}

메모리: 2784 kb

시간: 4 ms