13144 List of Unique Numbers

문제

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

입력

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

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

출력

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

====

문제 풀이

우선 N이 최대 10만이므로 O(N^2)인 로직은 배제해야한다.

한번의 순회를 통해서 정답을 출력한다는 생각으로 로직을 작성.

' 열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램 ' 이라는 것은

모든 연속된 수 조합 갯수에서 여러번 등장할 수 있는 조합의 갯수를 빼는 것과 같은 결과이다. 

1 2 3 1 2 이 있을 때

1 2 3 에서 1을 추가하는 순간 1이 여러번 등장하게 되어 그 뒤에 무슨 수가 오든 이것은 같은 수가 여러번 등장하게 되는 경우가 된다. 

이것의 갯수는 1이 등장한 인덱스인 3부터 가능한 것이므로 전체 갯수인 5에서 3을 빼준 2가지 경우가 같은 수가 여러번 등장하게 되는 것이다. ==> 1231, 12312  --> 2가지

인덱스 1부터 본다면 2 3 1 2 인 1가지  

사이즈가 n인 배열에서 연속된 수들의 총 수는 1+2+3+...+n-1+n 이다. ==> 총 갯수는 n*(n+1)/2  

총 갯수 5*(5+1)/2 - 3  = 12가지가 나오게 된다.

탐색을 진행하면서 지금까지 가진 수중 만났던 적이 있는지 측정하게 위해 큐를 하나 선언해준다.

const n = +input[0];
const arr = input[1].split(' ').map(Number);

let answer = (n * (n + 1)) / 2;
const q = [arr[0]];

이제 인덱스 1부터 arr을 탐색하면서 큐에 해당 엘리먼트가 담겨 있는지 확인해주고, 

있다면 그 값을 만날 때까지 pop을 해준다. 이때 큐에 3 4 5 1이 담겨있을 때 엘리먼트가 4가 온다면 큐는 두번 값을 꺼내줘야한다.

이 때도 같은 수가 여러 번 등장하는 것은 3 4 5 1 4, 4 5 1 4 로 같은 수를 만날 때까지 pop하면서 같은 수를 여러 번 만나는 연속 수를 더해줘야 한다는 것이다. 이때 shift 연산을 한번씩 해주면 시간 초과가 발생해서 큐에서 엘리먼트의 idx를 찾은 뒤 그 idx까지 splice 해주었고 연속되는 수를 idx+1 만큼 곱해주어 전체 경우의 수에서 빼줬다.

for (let i = 1; i < n; i++) {
    const value = arr[i];
    const idx = q.findIndex((v) => v === value);
    if (idx !== -1) {
        q.splice(0, idx + 1);
        answer = answer - (n - i) * (idx + 1);
    }
    q.push(value);
}

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input[1].split(' ').map(Number);

let answer = (n * (n + 1)) / 2;
const q = [arr[0]];

for (let i = 1; i < n; i++) {
    const value = arr[i];
    const idx = q.findIndex((v) => v === value);
    if (idx !== -1) {
        q.splice(0, idx + 1);
        answer = answer - (n - i) * (idx + 1);
    }
    q.push(value);
}

console.log(answer);