[틀림] 백준 13144 List Of Unique Numbers c++ // 투포인터, 배열활용

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

13144번: List of Unique Numbers

1. 배열활용 아이디어

vis[해당숫자] 방문여부표시 => 중복숫자인지 검사

 

2.전체코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, m,ret,temp;
vector<ll> v;
int vis[1000000 + 1];	//해당숫자 방문했는지 여부

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> temp;
		v.push_back(temp);
	}
	//v.push_back(0);

	if (n == 1) {
		cout << 1;
		return 0;
	}

	ll e = 0, ret = 0;
	for (int s = 0; s < n; ++s) {
		while (e < n) {
			if (vis[v[e]]) break;	//중복숫자인경우
			vis[v[e]] = 1;	//중복숫자가아닌경우 방문표시
			e++;
		}
		ret += (e - s);	//1,2,3,4,5인경우 : e==5, s==0
		vis[v[s]] = 0; //다음반복문위해 시작지점숫자 미방문표시
	}
	cout << ret;
}

 

* 25.1.30. 2회독

• 행동영역
  • 투포는 라인을 그리고 시각화 하라! 그러고 공식 도출(e-s)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,ret; // 경우의수는 ll 박고 시작
ll arr[100000+4], vis[100000+4];

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   cin>>n;

   for(int i=0;i<n;++i) {
      cin>>arr[i];
   }

   //각 s 에 대해
   int e=0;
   for(int s=0;s<n;++s) {
      while(e<n) {
         if(vis[arr[e]]) {
            //ret+=(e-s); // 여기두면 e==n이 될때 계산이 누락됨!
            break;
         }
         vis[arr[e]]=1;
         e++;
      }
      ret+=(e-s); // 올바른위치
      vis[arr[s]]=0;
   }
   
   cout<<ret;
   
   return 0;
}

 

* 큰돌

• 특징
  • while(e<n) 한번만돌림
  • for loop 없음

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstdio>
using namespace std;
long long s, e, cnt[100001], n, a[100001];
long long ret;
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%lld", a + i);
    }
    while(e < n){
        if(!cnt[a[e]]){
            cnt[a[e]]++;
            e++;
        }else{
            ret += (e - s);
            cnt[a[s]]--;
            s++;
        }
    }
    ret += (long long)(e - s) * (e - s + 1) / 2;
    printf("%lld\n", ret);
    return 0;
}

• e탈출시, 마지막 구간은 항상 유효한가? ㅇㅇ

1. 코드는 중복된 숫자를 만났을 때만 구간을 끊습니다.
2. e가 n에 도달했다는 것은 중복된 숫자를 만나지 않고 끝까지 갔다는 의미입니다.

예시로 보면:
```
1 2 3 1 2의 경우:
- 1 2 3까지 가다가 두 번째 1을 만나면 첫 구간 처리
- 2 3 1까지 가다가 두 번째 2를 만나면 두 번째 구간 처리
- 마지막 구간 3 1 2는 중복이 없는 상태로 끝남

1 2 3 4 5의 경우:
- 끝까지 중복을 만나지 않음
- 마지막 구간은 1 2 3 4 5 전체가 됨
```

따라서 e가 n에 도달했을 때의 마지막 구간은 s부터 e-1까지 모든 숫자가 중복 없이 있는 상태입니다. 이런 상태에서 등차수열의 합 공식을 적용하면 그 구간에서 가능한 모든 연속 부분 수열의 개수를 정확히 계산할 수 있습니다.