백준 [자바 java] 20922 : 겹치는 건 싫어

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

주어진 배열에서 같은 수가 k개 이하인 배열의 최대 길이를 찾는 문제이다.

HashMap를 사용하여 각 숫자의 등장횟수를 저장하였다.

투포인터를 사용했고, start는 0부터 하나하나 올렸고, end는 최대로 올리고, start가 변화함에 따라 end를 올릴 수 있게 되면 또 최대한 올리는 방식을 사용했다.

 

while(start < n){
  while(end < n){
    if(hash.containsKey(arr[end])){
      if(hash.get(arr[end]) == k) break;
      hash.put(arr[end],hash.get(arr[end])+1);
      end++;
    }
    else{
      hash.put(arr[end],1);
      end++;
    }
  }
  if(ans < end - start -1){
    ans = end-start;
  }
  hash.put(arr[start],hash.get(arr[start])-1);
  start++;
}

 

핵심 부분은 여기다

end값을 탐색하고, 해당 값이 k값과 같다면 더 이상 늘어나면 안되므로, end값을 갱신하지 않고, break를 통해 해당 루프를 빠져나간다.

 

start가 하나 늘어나면, 원래 start 위치에 있던 노드는 현재 탐색중인 배열에 포함되지 않는다.

따라서 이전 노드에 해당하는 hashMap값은 해당 루프가 끝날 때 하나 줄인다.

 

처음엔 end를 start랑 같은 위치에서 시작하도록 하였는데 그렇게 하니까 시간초과가 났다.

end의 위치는 최대한 오른쪽에 있으면 좋으니까 start가 변화하더라도 같은 위치에서 시작하도록 하였다.

 

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 k = Integer.parseInt(st.nextToken());

    int[] arr = new int[n];

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

    for(int i = 0;i<n;i++){
      arr[i] = Integer.parseInt(st.nextToken());
    }

    int start = 0;
    int end = 1;

    int ans = 0;

    HashMap<Integer,Integer> hash = new HashMap<>();
    hash.put(arr[0],1);

    while(start < n){
      while(end < n){
        if(hash.containsKey(arr[end])){
          if(hash.get(arr[end]) == k) break;
          hash.put(arr[end],hash.get(arr[end])+1);
          end++;
        }
        else{
          hash.put(arr[end],1);
          end++;
        }
      }
      if(ans < end - start -1){
        ans = end-start;
      }
      hash.put(arr[start],hash.get(arr[start])-1);
      start++;
    }
    System.out.println(ans);
  }
}

 

전체 코드는 이러하다.