BOJ 13144 : List of Unique Numbers

문제링크

풀이 요약

투 포인터

풀이 상세

1. 등차 수열을 이용한 문제이다. 예를 들어 1,2,3,1,2 를 예로 들어 본다면,

   • 1 을 시작으로 나올 수 있는 수열의 경우의 수는 1, 1,2, 1,2,3 이 되며
   • 다음 2를 시작으로 나올 수 있는 수열의 경우의 수는 2, 2,3, 2,3,1 이 된다.
   • 3 이후는 중복되는 것이 없으므로 모두 반영 될 수 있다.

2. st, ed 와 방문처리를 할 수 있는 배열과 함께, 나올 수 있는 모든 경우의 수를 탐색한다. 만약 중복되는 것이 나오는 경우는 st 값을 늘리고 이전 시작값의 방문처리를 다시 false 로 만드는 과정을 반복한다. 중복되는 값이 나왔을 때의 모든 경우의 수는 ed-st 이다.

3. 만약 임의의 st 를 시작으로 ed 값이 N 의 범위를 초과하게 되는 경우는 더이상 중복되는 값이 존재하지 않는다는 뜻이다, 현재 st~ed 범위의 등차수열을 구하는 공식은 $m*(m+1)/2$ 이다.

4. ed 값이 +1 초과되어 나오지만 ed 는 정확히 index 값이므로, 이론상 ed-st 를 했을 때 어차피 숫자 갯수가 하나 모자르니 문제 없었다.

배운점

• 방문처리용 배열을 쓰는 것 보다, 맵을 쓰는게 더 용량도 적고 빠르게 풀 수 있을 줄 알았더니 그게 아니더라. 추측하건데 맵의 경우 할당되는 값마다 버킷을 동적할당하는데 필요한 메모리도 존재하기 때문에 그러는 듯하다. 혹시나 해서, erase() 를 써봤지만 사용하는 메모리나 시간을 똑같더라. 여튼 오늘의 배운점은 $4bytes * 10만$ 이면 400kb 이니 팍팍 쓰자!

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int N, st, ed;
vector<int> v;

void input() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N;
    int num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        v.push_back(num);
    }
}

void solve() {
    unordered_map<int, int> m;
    long long ans = 0;
    while (ed < N) {
        if (!m[v[ed]]) {
            m[v[ed++]]++;
        } else {
            ans += ed - st;
						m[v[st++]]--;
        };
    }
    ans += (long long) (ed - st) * (ed - st + 1) / 2;
    cout << ans;
}

int main() {
    input();
    solve();
}