Life Engineering
[JUNGOL 2577] 회전 초밥(고) 본문
http://jungol.co.kr/bbs/board.php?bo_table=pbank&code=2577&sca=99
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main_JO_2577 {
static int N, d, k, c;
static int[] arr;
static int answer=0;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer 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+k-1];
for (int i=0; i<N; i++) {
arr[i]=Integer.parseInt(br.readLine());
}
for (int i=N; i<N+k-1; i++) {
arr[i]=arr[i-N];
}
window_sliding(k, c);
System.out.println(answer);
}
private static void window_sliding(int window, int coupon) {
Map<Integer, Integer> map=new HashMap<>();
map.put(coupon, 1);
for (int i=0; i<window; i++) {
int cnt=map.containsKey(arr[i])?map.get(arr[i]):0;
map.put(arr[i], cnt+1);
answer=Math.max(answer, map.keySet().size());
}
for (int i=window; i<N+k-1; i++) {
map.put(arr[i-window], map.get(arr[i-window])-1);
if (map.get(arr[i-window])==0) map.remove(arr[i-window]);
int cnt=map.containsKey(arr[i])?map.get(arr[i]):0;
map.put(arr[i], cnt+1);
answer=Math.max(answer, map.keySet().size());
}
}
}
슬라이딩 윈도우 문제다! 라고 직감하고 map을 이용해서 풀었다..
key를 빼고 value값이 0이면 아예 key를 제외하는 처리를 해줬다.
key의 사이즈를 새는 식으로 먹을 수 있는 초밥의 가짓수를 세줬는데, 이렇게 하면 시간이 많이 걸린다.
map을 이용하는 대신 배열의 인덱스를 이용해서 푼다면 시간을 반으로 줄일 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
static int N, d, k, c;
static int[] arr;
static int[] check;
static int answer=0, cnt=0;
static int num;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer 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+k];
check=new int[d+1]; //인덱스=초밥 넘버
boolean isCoupon=false;
for (int i=0; i<N; i++) {
arr[i]=Integer.parseInt(br.readLine());
}
for (int i=N; i<N+k; i++) {
arr[i]=arr[i-N];
}
for (int i=0; i<N+k; i++) {
if (i>=k) { //줄이기
num=arr[i-k];
check[num]-=1;
if (check[num]==0) {
cnt--;
if (num==c) isCoupon=false;
}
}
num=arr[i];
check[num]+=1;
if (check[num]==1) cnt++;
if (num==c) isCoupon=true;
if (i>=k) {
answer=Math.max(answer, isCoupon?cnt:cnt+1);
}
}
System.out.println(answer);
}
}
슬라이딩 윈도우를 진행시켜 가면서 인덱스가 k 이상이면 앞에꺼를 계속 빼주고,
빼줬는데 해당 초밥 넘버 인덱스의 배열 값이 0이면 count-- 해줘서 가짓수가 줄어들었음을 나타낸다.
추가해주는 것은 check[num]+=1 로 하는데, 이때 값이 1이면 처음 추가된 것이므로 count++ 해줘서 가짓수를 높인다.
여기서 포인트는 coupon이 있는지 없는지 flag 값으로 표시해서, 해당 영역에 쿠폰이 포함되어 있으면 count를 answer과 비교하고 포함되어 있지 않으면 count+1을 answer과 비교하는 식으로 진행한다.
'Problem Solving' 카테고리의 다른 글
[BOJ 2239] 스도쿠 (Java) (0) | 2022.04.06 |
---|---|
[BOJ 10159] 저울 (Java) (0) | 2022.04.05 |
[SWEA 5656] 벽돌 깨기 (Java) (0) | 2022.04.05 |
[BOJ 1644] 소수의 연속합 (Java) (0) | 2022.04.04 |
[SWEA 1767] 프로세서 연결하기 (Java) (0) | 2022.04.04 |