중복 없는 구간

문제

n개의 숫자가 주어지고, 이 중에서 r개의 연속된 숫자를 선택했을 때, 이 연속 부분 내에는 숫자가 중복되지 않기를 원한다. 예를 들어, 다음과 같이 10개의 숫자에서 3개의 연속된 숫자를 선택할 수 있다.

이렇게 선택을 하면, 선택된 숫자들 사이에서는 중복이 존재하지 않는다. r의 최댓값을 구하는 프로그램을 작성하시오. 위의 경우, (4, 2, 1, 3)을 선택하면 되므로 r의 최댓값은 4이다. r이 5 이상이 될 경우, 중복 없이 연속 부분을 선택하는 것이 불가능하다.

 

입력

첫째 줄에는 숫자의 개수 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 둘째 줄에 n개의 숫자가 주어진다. 각 숫자는 항상 1보다 크거나 같고, n보다 작거나 같다.  

출력

r의 최댓값을 출력한다.

 

예제 입력

10 1 3 1 2 4 2 1 3 2 1

예제 출력

4

 

예제 입력

7 7 1 4 2 5 3 6

예제 출력

7

 

#코드 : 시간복잡도에 어긋나는 것을 알았지만 그냥 잘못된 설계위에 풀었다.

# 구간합은 맨앞자리 숫자를 빼주고 맨뒷자리 숫자를 빼주면 되는데...

# 중복 숫자를 어떻게 솎아낼지 .... 몰겠다 ㅋ

import sys 
 
if __name__ == "__main__":
  input = sys.stdin.readline
  n   = int(input())
  arr = list(map(int, input().split()))
  
  start    = 1
  end      = n+1
  max_val  = 0
  interval = 1
  
  while start+1 < end:
    mid  = (start+end)//2  
    cnt = 0
    # 이중 for문 시간복잡도를 어떻게 줄일 수 있을까? 
    # 나는 모른다....
    for i in range(n-mid):
      temp    = {}
      origin  = list()
      sum_val = 0
      for j in range(i, i+mid): 
        sum_val += arr[j]
        origin.append(arr[j])
        try:
          temp[arr[j]] = 1
        except:
          temp[arr[j]] = 1  
      # 중복되었다면 cnt를 +1 
      if len(temp) != len(origin):
        cnt += 1
      # 중복되지 않았다면.
      else: 
        if max_val < sum_val:
          max_val  = sum_val
          interval = mid 
    if cnt == n-mid: # 구간모두 중복 즉 왼쪽으로 이동
      end = mid
      
    else:
      start = mid
  print(interval)   

 

#코드2 : 시간복잡도를 개선하였다...85점나온다..

import sys 
 
def isDuplicate(x): 
  global arr, cnt_arr, cnt, n
  # x구간에 중복 값을 확인한다.
  flag    = False
  max_val = 0 # 구간별 합 중 max값 단, cnt가 0인 경우에만...
  sum_val = 0 # 구간별 합의 값
  # 1.처음부터 ~ x까지 직접 값을 할당해준다.
  for i in range(x): 
    sum_val += arr[i]
    cnt_arr[arr[i]] += 1
    if cnt_arr[arr[i]] >= 2:  
      cnt += 1 
  if cnt == 0:
    flag = True
    if max_val < sum_val:
      max_val = sum_val 
  # 2.처음부터 ~ n-x까지 구간을 체크한다. 앞의 요소와 뒤의 요소를 이용
  #   앞의 요소의 cnt를 -1해주고 뒤의 요소의 cnt를 +1해준다.
  for i in range(n-x):  
    sum_val = sum_val - arr[i] + arr[i+x]
    # 앞의 요소 값을 빼줬을 경우 개수에 따라 cnt를 처리해준다.
    if cnt_arr[arr[i]] >= 2 and cnt_arr[arr[i]] - 1 < 2:
      cnt -= 1
    cnt_arr[arr[i]]   -= 1
    if cnt_arr[arr[i]] >= 2:  
      cnt += 1  
    # 새로 들어오는 뒤의 요소의 개수에 따라 cnt를 처리해준다.
    cnt_arr[arr[i+x]] += 1
    if cnt_arr[arr[i+x]] >= 2:  
      cnt += 1
    if cnt == 0:
      flag = True
      if max_val < sum_val:
        max_val = sum_val 
    
  return (flag, max_val) 
  
 
if __name__ == "__main__":
  input   = sys.stdin.readline
  n       = int(input())
  arr     = list(map(int, input().split()))
  # 구간별 개별 숫자의 빈도수를 카운팅하는 배열 변수
  max_val = max(arr)
  cnt_arr = [0]*(max_val+1)
  # 개별 숫자의 빈도수가 2이상인 요소들을 관리하는 변수
  cnt     = 0
  # 구간의 시작점과 끝점
  start   = 1
  end     = n+1 
  
  res_interval, res_max = 1, 0 
  while start+1 < end:
    mid  = (start+end)//2   
    # mid=구간 
    getFlag, getMax = isDuplicate(mid) 
     
    # getFlag값이 True이면, 오른쪽 탐색 : start = mid
    if getFlag:
      start = mid
      if getMax > res_max:
        res_max      = getMax
        res_interval = mid
    # getFlag값이 False이면, 왼쪽 탐색 : end = mid    
    else:
      end = mid
    cnt_arr = [0]*(max_val+1)
    cnt     = 0 
  print(res_interval)  

 

# 코드3 : 드디어 정답

# cnt를 중복된 숫자 갯수만큼 카운팅해버리는게 실수 였었다. 예를들어 1 : 2, 2 : 2 면 cnt = 4가 되어 버리는 것이 문제

# cnt는 중복된 숫자의 개수만 카운팅하면된다. 1:2, 2:2, 3:1 이면 cnt=2가 들어있으면 된다. 중복된 숫자는 1, 2이기 때문...

import sys 
 
def isDuplicate(x): 
  global arr, cnt_arr, n
  # x구간에 중복 값을 확인한다.
  flag = False 
  cnt  = 0 # 중복된 숫자의 개수를 카운팅한다.
  # 1.처음부터 ~ x까지 직접 값을 할당해준다.
  for i in range(x):  
    cnt_arr[arr[i]] += 1
    if cnt_arr[arr[i]] == 2:  
      cnt += 1 
  if cnt == 0:
    flag = True 
  # 2.처음부터 ~ n-x까지 구간을 체크한다. 앞의 요소와 뒤의 요소를 이용
  #   앞의 요소의 cnt를 -1해주고 뒤의 요소의 cnt를 +1해준다.
  for i in range(n-x):
    if cnt_arr[arr[i]] >= 2 and cnt_arr[arr[i]] - 1 == 1:
      cnt -= 1 
    cnt_arr[arr[i]]   -=1
    cnt_arr[arr[i+x]] +=1
    
    
    if cnt_arr[arr[i+x]] == 2:
      cnt += 1 
    if cnt == 0:
      flag = True
    
  return flag 
  
 
if __name__ == "__main__":
  input   = sys.stdin.readline
  n       = int(input())
  arr     = list(map(int, input().split()))
  # 구간별 개별 숫자의 빈도수를 카운팅하는 배열 변수
  max_val = max(arr)
  cnt_arr = [0]*(max_val+1)
  # 개별 숫자의 빈도수가 2이상인 요소들을 관리하는 변수
  
  # 구간의 시작점과 끝점
  start   = 1
  end     = n+1 
  
  res_interval, res_max = 1, 0 
  while start+1 < end:
    mid  = (start+end)//2   
    # mid=구간 
    getFlag = isDuplicate(mid) 
 
    # getFlag값이 True이면, 오른쪽 탐색 : start = mid
    if getFlag:
      start = mid 
      res_interval = mid
    # getFlag값이 False이면, 왼쪽 탐색 : end = mid    
    else:
      end = mid
    cnt_arr = [0]*(max_val+1)
     
  print(res_interval)