BackJoon 겹치는 건 싫어 20922 (Java)

업데이트:
1 분 소요

BackJoon Algorithm - Java

alt

문제

alt

풀이

..

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

public class Back_20922 {
    public static void main(String[] args) throws IOException {
        // 입력을 받기 위한 BufferedReader 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 첫 번째 줄 입력: N은 배열의 길이, K는 숫자가 배열에서 나타날 수 있는 최대 빈도수
        StringTokenizer token = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(token.nextToken());  // 배열의 크기 N
        int K = Integer.parseInt(token.nextToken());  // 배열의 각 숫자가 등장할 수 있는 최대 횟수 K
        
        // 수열을 저장할 배열 선언
        int arr[] = new int[N];
        
        // 두 번째 줄 입력: N개의 숫자를 배열에 저장
        token = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(token.nextToken());
        }
        
        // 각 숫자의 등장 횟수를 저장할 배열 (숫자의 최대 범위는 1 ~ 100000)
        int[] count = new int[100001];
        
        // 최대 부분 수열의 길이를 저장할 변수와 두 포인터
        int max = 0;
        int st = 0;
        int en = 0;

        // 투 포인터 사용
        while (en < N) {
            // 현재 수의 등장 횟수가 K보다 작거나 같으면 끝 포인터를 확장
            if (count[arr[en]] < K) {
                count[arr[en]]++;  // 숫자 카운트 증가
                en++;  // 끝 포인터 확장
                max = Math.max(max, en - st);  // 최대 길이 업데이트
            } else {
                // 만약 arr[en]이 이미 K번 등장했다면, 시작 포인터를 오른쪽으로 이동시킴
                count[arr[st]]--;  // 시작 포인터가 가리키는 숫자의 카운트를 감소
                st++;  // 시작 포인터를 오른쪽으로 이동
            }
        }
        
        // 결과 출력: 조건을 만족하는 부분 수열의 최대 길이
        System.out.println(max);
    }
}



댓글남기기