백준 13144 List of Unique Numbers(투 포인터)

 

문제

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

입력

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

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

출력

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

예제 입력 1 복사

5
1 2 3 4 5

예제 출력 1 복사

15

예제 입력 2 복사

5
1 2 3 1 2

예제 출력 2 복사

12

예제 입력 3 복사

5
1 1 1 1 1

예제 출력 3 복사

5

 

풀이

 

체크 배열을 두고 투포인터로 푼다 

1 2 3 1 2 가 있을때 

rt를 더 진행 불가능 할때 까지 증가시키면 1,2,3을 체크하고 이미 방문한 1을 만나서 멈춘다

-> {1}, {1,2}, {1,2,3} 이 답에 들어감, 1,2,3 체크됨

r이 멈추면 가능한 수열 갯수에  r - 1 +1을 더하고

l을 하나 증가시킨다 -> 1체크 해제됨

다시 rt가 방문 가능해진 1 까지 증가하고.. 이런 과정을 반복하게 된다

 

처음에 lt, rt 모두 1로 두고 시작하는걸로 생각하다가 r이 1부터 시작하면 arr[1]이 비교되지 않는걸 알고 r 범위를 0부터 시작하는 걸로 바꿨다

 

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        int[] check = new int[100001]; // 수열에 들어올 수 있는 수는 1~10만

        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);

        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(st.nextToken());

        long ans = 0;

        int l = 1;
        int r = 0; // r이 1부터 시작하면 arr[1]은 비교에 들어가지 않는다

        while (l <= n){
            while (r < n && check[arr[r+1]] == 0){ // 옮긴 위치에 있는 숫자가 l~r 사이에 있으면 안됨
                r++;
                check[arr[r]] = 1;
            }

            ans += r - l +1;
            check[arr[l]] = 0;
            l++;
        }

        System.out.println(ans);
    }
}