백준 13144번 <List of Unique Numbers>

백준 알고리즘 13144번

https://www.acmicpc.net/problem/13144

13144번: List of Unique Numbers

---

13144번

 

---

문제 해결

two pointer를 사용하여 문제를 풀이했다.

작은 테스트케이스를 손으로 확인하며 찾은 규칙을 보니 two pointer를 사용하면 될 것 같았다.

하나씩 모두 구해보니 end를 기준으로 end-1까지의 숫자로 만든 수열에 end를 추가하면 된다는 것을 알 수 있었다. 

이때, 중간에 같은 숫자가 있는 경우에는 start를 update 시켜주어야 하는데 다음 그림을 보면 쉽게 이해할 수 있다.

2가 중복으로 나오기 때문에 중간에 start를 2로 update 한 것을 확인할 수 있다. 이렇게 하면 [3, 2, 1] 을 수열로 생각할 수 있게 된다.

 

사용하는 변수는 다음과 같다.

• use[i] : 숫자 i를 사용했으면 true 사용하지 않았으면 false
• start : 고려하는 수열의 시작 인덱스
• end : 고려하는 수열의 끝 인덱스
• acc  : 같은 수가 등장하지 않는 경우의 수

N이 100,000개이고, 수열의 숫자가 모두 다르다면 ( 100,000 * (100,000 + 1) ) / 2 = 5,000,050,000 로 최대 50억이 될 수 있기 때문에 long 타입을 사용하였다.

 

프로세스는 다음과 같다. 

• 방금 추가한 숫자 (수열의 end 인덱스 숫자)를 사용했다면 사용하지 않게 만든다.
• 방금 추가한 숫자를 사용하지 않을 때까지 start를 증가시켜가며 숫자를 사용하지 않는다. 
• 방금 추가한 숫자를 사용한다. end - start + 1 개의 경우의 수를 구할 수 있다. 
  • 이전에 구성된 경우들에 방금 추가한 숫자를 이어붙이는 경우와 방금 추가한 숫자 혼자 있는 경우
• end를 1 증가시킨다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_13144 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] number = new int[N];
        String[] inArr = br.readLine().split(" ");
        int max = 0;
        for (int i = 0; i < N; i++) {
            number[i] = Integer.parseInt(inArr[i]);
            max = Integer.max(max, number[i]);
        }
        boolean[] use = new boolean[max + 1];
        int start = 0;
        int end = 0;
        long acc = 0;
        while (end < N) {
            // 방금 추가한 숫자가 이미 사용 중이라면
            if (use[number[end]]) {
                // 해당 숫자 사용 안하기
                while (start <= end) {
                    if (number[end] == number[start]) {
                        start++;
                        break;
                    }
                    use[number[start]] = false;
                    start++;
                }
            }
            // 방금 추가한 숫자 사용
            use[number[end]] = true;
            acc += (end - start) + 1;
            end++;
        }
        System.out.println(acc);
    }
}

---

결과

 

---