22. UVa-11572 Unique Snowflakes

문제

<그림1: 문제설명>

별 잡다한 얘기를 다 붙여놨는데, 주어지는 integer sequence중에서 중복 원소를 포함하지 않는 longest subsequence의 최대 길이를 구하라는 문제다. (nlgn)안에 풀 수 있는 문제다. max_length를 갱신해가는 logic으로 풀었는데 일단 코드는 다음과 같다.

 

#include<iostream>
#include<map>
using namespace std;
/*Given a sequence of integers, find the length of the longest contiguous 
subsequence containing no repeated elements.
*/

int main() {
	int N;
	cin >> N;
	while (N--) {
		int test,max_length=0,length=0,startidx=1; //start idx: start point of subsequence
		int* input_arr;
		map<int, int> snow_flakes;	//first int is size of flake
		cin >> test;
		input_arr = new int[test+1]; //cause map[doesn't exist] returns 0, can't use 0 index.
		for (int i = 1; i <= test; i++) cin >> input_arr[i]; //input part

		for (int i = 1; i <= test; i++) {
			if (snow_flakes[input_arr[i]] == 0) { //if it is not contained in subsequence
				snow_flakes[input_arr[i]] = i; //write the position
				++length; //subsequnce's length++
				if (length > max_length) max_length = length;	//renew max length 
			}
			else {	//if it is contained in subsequence
				for(int j = snow_flakes[input_arr[i]]-1; j >= startidx; j--) { //remove at sequence from where it appear to start of sequence
					snow_flakes[input_arr[j]] = 0;
					--length;
				}
				startidx = snow_flakes[input_arr[i]] + 1; //start at final point of removal
				snow_flakes[input_arr[i]] = i; //now it appears at here
			}
		}

		cout << max_length <<endl;
	}
	return 0;
}

핵심은 다음 파트이다.

	for (int i = 1; i <= test; i++) {
			if (snow_flakes[input_arr[i]] == 0) { //if it is not contained in subsequence
				snow_flakes[input_arr[i]] = i; //write the position
				++length; //subsequnce's length++
				if (length > max_length) max_length = length;	//renew max length 
			}
			else {	//if it is contained in subsequence
				for(int j = snow_flakes[input_arr[i]]-1; j >= startidx; j--) { //remove at sequence from where it appear to start of sequence
					snow_flakes[input_arr[j]] = 0;
					--length;
				}
				startidx = snow_flakes[input_arr[i]] + 1; //start at final point of removal
				snow_flakes[input_arr[i]] = i; //now it appears at here
			}
		}

 

이 부분의 기본 logic은 아래 그림과 같다.

<그림2: 문제 풀이>

일단 i번째 input을 보면 다음을 생각한다.

지금 subsequence에 포함하고 있는 input인가?

->NO: 지금 subsequence에 포함하고 length++, maxlength갱신

->YES: 그 input이 옛날에 나온 시점부터 현재 subsequence의 시작원소까지를 전부 지우고 지운 만큼 length를 조정&그 원소가 나온 위치를 map에서 바꿔준다.

이 때 해당 input이 나온 위치를 저장하는 데에 자료구조 map을 이용하였다. map에는 input이 없는 경우 0을 반환하게 되어있으니까 (원소를 지우는 것)==(해당 map의 그 원소에 해당하는 Data에 0 대입) 이 된다.