[JAVA] 13144 - List of Unique Numbers 💛4 : 투 포인터를 활용한 경우의 수 구하기

들어가며

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

주어진 수열에서 "연속된" 1개 이상의 수를 뽑았을 때 중복되지 않는 경우의 수를 정답으로 출력하면 되는 문제이다.

본론으로

중복만 체크해주면 되기에 중복 배열이나 Set 자료구조를 활용하여 완전탐색하면 정말 좋겠지만, 주어지는 수열의 길이는 최대 10만이다. O(N^2)으로는 절대 풀 수 없는 문제이다!!

투 포인터를 활용하면 시간복잡도를 O(N)으로 줄이며 경우의 수를 뽑아낼 수 있지 않을까? 라는 생각으로 좁혀진다. 하지만... 이 문제 구현이 어렵다 ㅜㅜ. 왼쪽에서부터 포인터 두개로 쭉쭉 진행되다가 중복된 것이 생기면 왼쪽 포인터를 하나 땡기는 생각은 이해가 되는데.. 특히 지금 상황의 경우의 수 구하는 식이 쉽게 안떠오른다.. 하다 보면 (r-l + 1) 로 정리가 된다.

아래는 해당 생각을 기반으로 구현한 정답 코드이다.

public class Main {

    static int N;
    static long ret;
    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 = new int[N]; // 수열 담기용
        cnt = new int[N + 1]; // 중복 체크용
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        ret = 0;
        int l = 0;
        for (int r = 0; r < N; r++) {
            cnt[arr[r]]++;

            while (cnt[arr[r]] > 1) {
                cnt[arr[l]]--;
                l++;
            }

            ret += (r - l + 1);
        }

        System.out.println(ret);

    }
}

마무리하며

투포인터를 활용해서 왼쪽에서부터 오른쪽으로 라인스위핑 하는 방식의 문제는 정말 많은 것 같다. 근데 경우의 수 관련된 문제만 나오면 왜이렇게 머리가 막막해지는지... 고등학생때 미적분 말고 확통좀 들을걸!!!

문제에서 요구하는 식을 만드는 연습을 필사적으로 더 해야겠다. 아자자 🧑‍💻