[실버 1] 회전 초밥

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

2531번: 회전 초밥

풀기 전:

뭐가 이렇게 복잡해

 

1. 범위 k개로 해서 한 바퀴 돌면서 hashMap에 담자

이런 다음에 hashMap 돌면서 hashMap.size max 찾고

max개인 것들 안에서 쿠폰넘버 뒤져서 없으면 답은 max+1개인 거다

 

풀어보자

 

메모리초과 너무 다 저장하려고 했나

 

주어진 힌트를 전부 사용하려고 해 보자

 

 

int [] check = new int [초밥의 가짓수];

check [쿠폰번호] = 1;

number =1;

max =0;

쿠폰을 무조건 쓴다고 생각하고 처음부터 넣고 시작

check [초밥번호] = 0 이 되면 종류에서 빠진 거기 때문에 number--;

check [초밥번호] = 1 이 되면 종류에서 새로 추가된 거 기 때문에 number++;

 

left가 N이 되면 종료하고 매번 max 갱신해 주기

 

정답은 max

 

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N;
        int d;
        int k;
        int c;
        int[] arr;

        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        arr = new int[N];
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(br.readLine());

        /////////////////////////////////////////////////////////////////////////////

무난하게 입력받기

        int[] check = new int[d + 1];
        check[c] = 1;
        int count = 1;
        int max;

        int left = 0;
        int right = 0;
        for (; right < k; right++) {
            check[arr[right]] = check[arr[right]] + 1;
            if (check[arr[right]] == 1)
                count++;
        }

        max = count;

        while (left < N) {
            check[arr[left]] = check[arr[left]] - 1;
            if (check[arr[left]] == 0)
                count--;
            left++;

            check[arr[right]] = check[arr[right]] + 1;
            if (check[arr[right]] == 1)
                count++;
            right = (right+1)%N;

            if (max < count)
                max = count;
        }

        sb.append(max+"");
        System.out.println(sb);

    }
}