13144. List of Unique Numbers

슬라이딩 윈도우 vs 투포인터

13144: List of Unique Numbers(슬라이딩 윈도우)

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

• 문제 티어 : G4
• 풀이 여부 : Failed
• 소요 시간 : 21:05

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().rstrip().split()))
unique_elements = set()
ans = 0

left = 0
for right in range(N):
  while arr[right] in unique_elements: # 현재 요소에 중복된 요소가 있는 경우
    unique_elements.remove(arr[left]) # left 요소를 삭제하고
    left += 1 # left 한 칸 오른쪽으로 옮김

  unique_elements.add(arr[right]) # 중복된 요소가 없다면 right 포인터가 가리키는 요소를 추가
  ans += right - left + 1

print(ans)

접근 방식

중복요소가 없어야 하므로 중복요소가 있는 경우 left를 이동해 윈도우를 한 칸 오른쪽으로 옮기고,
arr 전체를 right가 순회하며 집합에 추가한다.

접근 시행착오(+ 코드)

백트래킹으로 접근했었지만.. 중복을 제거하지 못했고! 메모리가 아주 한정적이었고! 시간을 초과했고!
ex) 1 2 3 4 5 → [1, 2, 3, 4, 5, 12, 23, 34, 45, 123, 234, 345, 1234, 2345, 12345]
위와 같이 정답이 수열 기준으로 한칸씩 밀려가며 나오는 것을 보고 슬라이딩 윈도우라고 생각을 했지만
슬라이딩윈도우를 적용해 구현을 못하겠어서 GPT의 힘을 빌렸다 😂

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().rstrip().split()))
ans = 0

def backtrack(idx, curr, length):
  global ans
  if length == len(curr):
    ans += 1
  else:
    for i in range(idx, len(arr)):
      if arr[i] not in curr:
        curr.append(arr[i])
        backtrack(idx+1, curr, length)
        curr.pop()

for i in range(1, N+1):
  backtrack(0, [], i)

print(ans)

배운점 또는 느낀점

슬라이딩윈도우 유형의 문제를 많이 풀어야겠다.
백트래킹이라 생각하고 풀었다가는 중복 처리에서 까다로워지고, 시간과 메모리를 너무 잡아먹기에
투포인터와 슬라이딩윈도우를 잘 활용하는 능력을 길러야겠다!