[백준/Baekjoon] 13144 List of Unique Numbers C++ :: Two pointer

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

13144번: List of Unique Numbers

---

1. Logic

이 문제는 투포인터를 사용하여 풀 수 있다.

 

문제를 푸는 로직은

1. start, end를 0으로 초기화 한다.

2. input 받은 값을 순회하며 중복이 없을 때 까지 map에 입력한다.

3. 중복이 있는 문자가 나오면 멈추고 수열의 갯수인 end-start-1개를 더해준다.

4. 과정을 반복하며 입력받은 수의 끝까지 반복해준다.

 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
vector<int> input;
map<int, int> m; //수열에 등장하는 숫자가 중복인지 확인

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

    cin >> n;
    int start = 0;
    int end = 0;
    long long ans = 0;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        input.push_back(a);
    }    

    m[input[start]] = 1;

    while(true) {
        //input[end+1]이 선택한 수열에 없을경우 추가
        while(end < n - 1 && m[input[end + 1]] == 0) {
            end++;
            m[input[end]]++;
        }
        if(start >= n || end >= n) break;

        ans += end - start + 1;
        m[input[start]]--;
        start++;
    }

    cout << ans;
}

 

 

---

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐