[Java/투포인터] 코드트리. 겹치는 숫자가 없는 최대 구간

🤔 Intuition

투포인터를 아직도 제대로 못 하는 것 같아서 트레이닝을 위해 개념 문제를 풀었다.

투포인터 문제인지 알고 접근했다.

🔎 Algorithm & Complexity

* @algorithm two pointer
* @time O(N) : 선형탐색
* @memory O(N + R) : 주어지는 숫자 개수 N + 주어지는 숫자 범위 R

👨🏻‍💻 Logic

1. 입력되는 숫자 배열을 운영함과 동시에, 숫자들의 등장 횟수를 저장하는 count array를 운영하면 투포인터를 진행하는 과정에서 숫자의 중복 여부 또는 숫자의 등장 횟수를 O(1)로 관리할 수 있다.
2. 이를 이용하여 투포인터를 운영하면 된다.

public class Main {
    private static int N;
    private static int[] arr;
    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];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] counting = new int[100001];

        int right = 0; // right pointer init
        int ans = 0;
        for (int left = 0; left < N; left++) { // left pointer
            while (right < N) {
                int num = arr[right];
                if (counting[num] == 1) {
                    break;
                }
                counting[num]++;
                right++;
            }
            ans = Math.max(ans, right - left);
            int pop = arr[left];
            counting[pop]--;
        }

        System.out.println(ans);
    }
}

 

위 로직을 투포인터 템플릿에 맞게 맞춰서 좀 더 명료하고 깔끔하게 바꾸면 아래와 같이 될 수 있다.

 

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

public class Main {
    private static int N;
    private static int[] arr;
    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];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] counting = new int[100001];

        int right = -1; // right pointer init (right + 1이 0번 인덱스부터 바라봐야 하므로 -1로 초기화)
        int ans = 0;
        for (int left = 0; left < N; left++) { // left pointer
            while (right + 1 < N && counting[arr[right+1]] != 1) {
                counting[arr[right + 1]]++;
                right++;
            }
            ans = Math.max(ans, right - left + 1);
            counting[arr[left]]--;
        }

        System.out.println(ans);
    }
}