(JAVA) [BOJ]백준 20922번, 겹치는 건 싫어

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

20922번: 겹치는 건 싫어

 

 

20922, 겹치는 건 싫어

📌 난이도 : Silver 1

📌 알고리즘 : 투포인터

 

이번 문제는 투포인터 문제이다. 루프 안에서의 범위 설정에 주의해야 한다.

 

🧩 프로세스

📚 초기화 및 선언

: 정수 N 과, 중복의 수 K를 입력받고 N개만큼의 int[] 를 생성해서 값을 넣어준다.

또한 수의 중복값을 확인하기 위해 int[] arr 을 생성해준다. N 의 범위 때문에 new int[100,001] 로 생성해준다.

(수의 범위 0 ~ 100,000)

public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static int N,K;
public static int[] A;
public static int[] nums = new int[100001];

public static void main(String[] args) throws IOException {
    input();
    process();
}

public static void input() throws IOException {
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());

    A = new int[N+1];

    st = new StringTokenizer(br.readLine(), " ");
    for(int i=1; i<=N; i++) A[i] = Integer.parseInt(st.nextToken());
}

 

📚 투포인터

: 투포인터를 사용하겠다. A 의 1 ~ N번까지의 원소가 존재한다. 왼쪽 포인터 L은 1부터, 오른쪽 포인터는 0부터 탐색을 진행한다.

 

왼쪽 포인터가 +1 될때마다 현재 인덱스 -1 의 인덱스 값을 제거해준다. while 문을 통해 R+1 이 N 보다 작거나 같고, A[R+1] 의 값이 K 보다 작을 경우에 오른쪽 포인터를 옮겨주고 사용된 값의 중복 수를 올려준다.

탐색이 끝나면 R-L+1 을 통해 부분 수열의 길이의 최댓값을 갱신해주면 되는 문제이다.

public static void process() {
    int R=0, cnt = 0;

    for(int L=1; L<=N; L++) {
        // 왼쪽 포인터가 오른쪽으로 이동할 때마다 
        // 빠지는 수열의 카운트를 빼준다
        nums[A[L-1]]--;

        while(R+1<=N && nums[A[R+1]] < K) {
            nums[A[++R]]++;
        }

        cnt = Math.max(cnt, R-L+1);
    }

    System.out.println(cnt);
}

 

✅ 전체 코드

: 투포인터에서 오른쪽 포인터 설정에 주의하자!

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

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static int N,K;
    public static int[] A;
    public static int[] nums = new int[100001];

    public static void main(String[] args) throws IOException {
        input();
        process();
    }

    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        A = new int[N+1];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1; i<=N; i++) A[i] = Integer.parseInt(st.nextToken());
    }

    public static void process() {
        int R=0, cnt = 0;
        
        for(int L=1; L<=N; L++) {
            // 왼쪽 포인터가 오른쪽으로 이동할 때마다 
            // 빠지는 수열의 카운트를 빼준다
            nums[A[L-1]]--;

            while(R+1<=N && nums[A[R+1]] < K) {
                nums[A[++R]]++;
            }

            cnt = Math.max(cnt, R-L+1);
        }

        System.out.println(cnt);
    }
}