[BOJ/C++] 백준 13144번: List of Unique Numbers

 

🔗 문제 링크 : https://www.acmicpc.net/problem/13144

 

 

☁ 어떻게 해야 투포인터를 더 효율적으로 움직일 수 있을지.. 수많은 고민을 하며 풀었던 문제

 

아직 투포인터 구현이 미숙했기에 첫 접근 방식부터가 잘못됐었다.

투포인터를 구현하면서 중복 확인 부분을 unordered_set을 이용하는 방법을 택했는데, 갈수록 복잡해지는 코드에 잘못된 길(?)을 걷고 있음을 깨달았다. 투포인터조차 제 기능을 못 하는 상황까지.. 🥊

 

투포인터인'척' 하는 내 코드에게..

 

결과적으로, 배열을 이용하여 현재 숫자의 빈도를 카운트를 하고, 중복이 발생하면 투포인터의 움직임으로 구간의 중복을 제거하며, 중복이 없는 구간에서 가능한 경우의 수를 누적해 나가도록 구현한 코드가 최종 정답이 되었다.

 

 

 

역시 다양한 유형의 문제를 풀고 경험치 쌓는 게 최고다. 🎣

 

 

---

 

문제

길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.

 

 

 

 

 

입출력 예시

입력

첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다. 수열에 나타나는 수는 모두 1 이상 100,000 이하이다.

 

 

출력

조건을 만족하는 경우의 수를 출력한다.

 

 

 

입출력 예시

 

 

 

---

 

풀이 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    int N;
    cin >> N;
    vector<int> nums(N);
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }
 
    int left = 0;
    long long count = 0;
    vector<int> freq(100001, 0); // 숫자의 빈도를 저장할 배열

    /* 투 포인터 알고리즘 */
    for (int right = 0; right < N; right++) {
        freq[nums[right]]++;  // 현재 숫자의 빈도 증가

        /* 중복이 발생하면 left를 증가시켜 중복이 없도록 조정한다. */
        while (freq[nums[right]] > 1) {
            freq[nums[left]]--;
            left++;
        }

        /* 중복이 없는 구간의 경우의 수를 더해준다. */
        count += (right - left + 1);
    }

    cout << count;
    return 0;
}

 

 

vector<int> freq(100001, 0);

• freq 배열을 사용하여 각 숫자의 빈도를 관리한다.
• 각 숫자가 몇 번 등장했는지 확인한다.
• freq[n]에 담긴 값이 2 이상이라면 현재 구간 nums[left] ~ nums[right] 에서 숫자 n이 두 번 등장했다는 뜻이다.

 

 

/* 중복이 없는 구간의 경우의 수를 더해준다. */
count += (right - left + 1);

구간의 길이에 따른 부분 수열을 생각해 보자.

중복이 없는 구간의 길이가 L일 때, 그 구간 내에서 가능한 부분 수열의 수는 아래와 같은 특징이 있다.

• 길이 1의 부분 수열: L개
• 길이 2의 부분 수열: L−1개
• 길이 3의 부분 수열: L−2개
  ...
• 길이 L의 부분 수열: 1개

---