[백준] 13144번 -List of Unique Numbers (JAVA)

 1 2 3 1 2에서 1개 이상의 수를 뽑았을때 나올 수 있는 경우의 수는 12가지이다.  여기서 포인트는 연속한 1개이상의 수를 뽑아야 한다는 것이다..! 이 문제는 두포인터 알고리즘을 이용해서 풀 수 있다. 한개의 포인터는 차례대로 늘리고 다른 하나의 포인터는 점점 늘리는 식으로 활용하는 것이다. 

---

| 투 포인터(Two Pointers)란? 

 

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 정렬되어있는 두 리스트의 합집합에도 사용됨. 

---

| 접근 방식

1. l 을 차례대로 늘리고 , r은 점점 늘리는 식으로 두 포인터를 활용한다. 

 : 두 포인터는 안봐도 될 부분을 안 보기 위한 알고리즘이다. 

 

ex) 1 2 3 1 2 수열이 있을때 

  l = 1, r = 1 에서 r = 2, r =3 까지 하면 안전한 범위이다. 이를 r - l + 1 즉, l과 r사이의 거리로 하는 이유는 

 l이 1이기 때문에 1을 포함해서 연속된 수열을 만들 수 있는 경우의 수가 1, 1 2, 1 2 3 이렇게 3개이기 때문이다. 

 l = 2일때도 마찬가지이다. 2 , 2 3 , 2 3 1 이렇게 3가지를 만들 수 있고, l = 3일때는 3 , 3 1 , 3 1 2 이렇게 3가지, 

 l = 4일때는 1, 1 2 이렇게 2가지, l = 5 일때는 2 한가지이다. 

 

2. l은 차례대로 증가시키지만 r은 두가지 조건에 맞춰서, 한칸씩 늘려나간다. 

 

  1) 처음쓰는 숫자인지, 즉 num 배열에서 0 인지

  2) arr 배열의 길이를 넘지 않는지 

 

조건을 반복해서 검사해야되기 때문에 미리 늘어난 r 범위가 조건에 맞는지 확인한 후, r을 늘리는 게 안전하기 때문이다.

 

3. 수가 중복되는지 확인하기 위해 확인용 배열을 만든다. 단,수열의 길이는 100,000이하라고 했으므로 100,001 크기로 만들어준다. 

 

| 입,출력

BufferedReader 이용하여 입력하고 println 으로 출력하였다. 

 

---

import java.io.*;
import java.util.*;
public class Unique_13144 {
    static int N;
    static int [] arr, cnt;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        //arr,cnt 배열만들고 값 담아주기 
        arr = new int[N+1];
        cnt = new int[100000 + 1];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        toPoint();
    }
    static void toPoint(){
    	
        long ans = 0;
        
        int l = 1; 
        int r = 0;
        //현재 위치(l)에서 시작해서 조건 만족할때까지 r을 늘려나간다. 
        while(l <= N){
        	//처음쓰는 숫자인지, 범위를 안넘는지 체크 
            while(r + 1 <= N && cnt[arr[r + 1]] == 0){
                r++; //while 조건에서 이미 확인을 했으므로 안심하고 증가.
                cnt[arr[r]]++; //해당 수 썼으니 썼다고 표시 
            }
            
            ans += r - l + 1;
          //l을 한칸씩 밀면서 볼것이기 때문에 계산이 끝나고 나면 l을 한 칸 밀어준다. 
          //이전 위치의 cnt는 다음번 계산에서 제외하기 위해 cnt[arr[l]]--;
            cnt[arr[l++]]--; 
        }
        System.out.println(ans);
    }
}

 

참고: https://coder-in-war.tistory.com/entry/BOJ-JAVA13144-List-of-Unique-Numbers