백준 [자바 java] 2531 : 회전초밥

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

 

이 문제는 위와 같은 회전초밥집의 규칙이 있을 때 사용자가 먹을 수 있는 초밥의 최대 가짓수를 구하는 문제이다.

처음에는 해시셋을 사용했는데, 생각해보니 특정 숫자가 2개 이상인 경우, 셋에서 아예 빼버리면 반례가 발생하게된다.

따라서 해시맵을 통해 각 숫자별로, 등장 횟수를 저장하는 방식으로 구현했다.

 

풀이

HashMap<Integer,Integer> h = new HashMap<>();

for(int i = 0;i<k;i++){
  h.put(arr[i],h.getOrDefault(arr[i],0)+1);
}
h.put(c,h.getOrDefault(c,0)+1);

일단 0부터 K-1까지 해시맵에 넣었다(초기값)

그 다음 서비스로 주는 초밥 번호까지 맵에 넣은 후 

 

for(int i = 1;i<n;i++){
  if(h.get(arr[i-1]) == 1) h.remove(arr[i-1]);
  else h.put(arr[i-1],h.get(arr[i-1])-1);

  h.put(arr[(i+k-1)%n],h.getOrDefault(arr[(i+k-1)%n],0)+1);

  ans = Math.max(ans,h.size());
}

 

1부터 n-1까지 순회한다.

i-1(현재 집합에서 제외되는 부분)은 맵에서 제거하고, (i+k-1%n), (새로 집합에 들어가는 부분)은 해시맵에 추가하거나 기존 value에 1을 더했다.

이 때 %n을 사용한 이유는 회전초밥이 회전하는 형태라, n-1이 시작점인 집합의 구성요소는 n-1, n,n+1가 아니고, n-1, 0,1이기 때문이다.

 

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

public class Main {

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

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

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

    HashMap<Integer,Integer> h = new HashMap<>();

    for(int i = 0;i<k;i++){
      h.put(arr[i],h.getOrDefault(arr[i],0)+1);
    }
    h.put(c,h.getOrDefault(c,0)+1);

    int ans = h.size();

    for(int i = 1;i<n;i++){
      if(h.get(arr[i-1]) == 1) h.remove(arr[i-1]);
      else h.put(arr[i-1],h.get(arr[i-1])-1);

      h.put(arr[(i+k-1)%n],h.getOrDefault(arr[(i+k-1)%n],0)+1);

      ans = Math.max(ans,h.size());
    }

    System.out.println(ans);


  }
}

 

전체 코드는 이렇다.

해시맵 함수를 사용할 때 괄호가 많아서 헷갈리기 쉬운데 끝까지 괄호를 올바른 곳에 뒀는지 확인할 필요가 있다.