[백준]겹치는 건 싫어, [백준]회전초밥

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

20922번: 겹치는 건 싫어

투포인터

1) lo, hi =0, 0, cnt = {}

2) 종료조건 : hi 포인터가 끝까지 가면 종료

3) 해당 정수 dict에 count가 k개 미만 or Not 분기 설정

import sys
from collections import defaultdict

def solution(n,k,arr):
    lo,hi = 0,0
    ans = 0
    cnt = defaultdict(int)
    while hi < n:
        if cnt[arr[hi]] < k:
            cnt[arr[hi]] +=1
            hi +=1
        else:
            cnt[arr[lo]] -=1
            lo +=1
        ans = max(ans, hi-lo)
    return ans

N, K = map(int, sys.stdin.readline().split())
arr = [*map(int, sys.stdin.readline().split())]

print(solution(N,K,arr))

c++ 풀이

#include<iostream>
#include<algorithm>
using namespace std;
int arr[200000];
int cnt[100000];
int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    int n,k;
    cin >> n >> k;
    int ans = 0;
    int lo = 0, hi = 0;
    for(int i=0; i<n;i++) {
        cin>>arr[i];
    }

    while(hi < n) {
        if(cnt[arr[hi]]<k){
            cnt[arr[hi]] ++;
            hi++;
        } else {
            cnt[arr[lo]] --;
            lo++;
        }
        ans = max(ans, hi-lo);
    }
    cout << ans;
    return 0;  
}

 

 

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

15961번: 회전 초밥

투포인터

1) while 문 사용 (break 조건 --> lo 포인터가 n 보다 작은경우, 초밥 종류가 K 보다 큰 경우)

2) defaultdict 사용,  lo, hi +1, dictionary hi -> +1 lo -> -1  (dictionary low value 가 0 인경우 key,value 삭제)

3) dictionary 길이로 리턴

 

import sys
from collections import defaultdict

def solution(arr,n,d,k,c):
    lo,hi = 0,0
    dic = defaultdict(int)
    ans = 0
    dic[c] +=1  ## 쿠폰번호
    
    while hi < k:
        dic[arr[hi]] +=1
        hi+=1
        
    while lo < n:
        ans = max(ans, len(dic))
        dic[arr[lo]] -=1
        if dic[arr[lo]] == 0:
            del dic[arr[lo]]
        dic[arr[hi%n]] +=1
        lo +=1
        hi+=1
        
        if ans > k:
            return ans
    return ans
    

# 접시수,초밥가짓수,연속접시수,쿠폰번호
n,d,k,c = map(int, sys.stdin.readline().split())  
arr = [*map(int,sys.stdin.readlines())]
print(solution(arr,n,d,k,c))