[C++] UVa-11572 Unique Snowflake

 

구현 코드 )

 

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

#define maxn (int)(le9)+1

int t, n, x, ans, cnt, block;

map<int, int> lastseen; 

int main() {
	cin >> t; // 테스트 케이스 개수 입력

	while (t--) {
		cin >> n; // 정수 리스트의 길이 입력

		lastseen.clear(); 
        //테스트 케이스가 1개 이상 입력 될 경우 map을 초기화 하여 입력을 받아온다.
		
		ans = 0, cnt = 0, block = 0;
		for (int i = 1; i <= n; i++) {
        	cin >> x; 		
	        

            int lx = lastseen[x];

			if (lx != 0) {
				block = max(block, lx); 
				cnt = i - block - 1;
                
			}
			cnt++;
			lastseen[x] = i;  
			ans = max(ans, cnt);
		}
		cout << ans << '\n';
        
        // 끗!
	}
}

 

코드 설명 )

 

1. 변수 설명

 

int t : 테스트 케이스 입력 개수 저장

int n : 리스트의 길이 입력 저장

int x : 사용자가 입력한 정수

int ans : 중복 없이 측정 가능한 최대 길이

int cnt : 현재 중복 없이 측정하고 있는 길이

int block : 가장 최근 마주한 중복 element

 

2. 코드 진행

 

• 사용자가 입력한 길이 만큼의 반복문을 진행한다.
• x를 가장 최근에 본 위치를 저장하는 map인 lastseen에서 index x의 값을 lx에 저장한다. 
      => 본 적이 없을 경우 0의 값을 반환한다.
• x를 본 위치가 있을 경우 중복값이 감지된 것 이므로 block 위치를 업데이트 하여 중복 지점을 체크 한다.
• lx와 현재 block 값을 비교하여 큰 값을 저장하는 이유는 앞서 지정해 두었던 block 값 보다 앞의 index로 block을 설정 할 경우 중복이 발생할 수 있기 때문에 더 큰 index 값을 block으로 지정하여 중복을 막는다.
• block index 바로 뒤 index 부터 현재 i의 위치까지의 길이를 cnt에 저장한다.
• 가장 최근에 본 입력값 x의 위치는 현재 i의 위치로 last seen을 업데이트 한다.
• 지금까지 측정 된 중복 없이 연속된 길이 (ans) 와 현재 측정 중인 연속된 길이(cnt)를 비교하여 더 긴 값을 ans에 저장한다.