Algorithem/백준 PS with code

백준 #2531 - [S1] 회전 초밥 : 두포인터

2023. 7. 6. 11:07
목차
  1. 두포인터 혹은 슬라이딩 윈도우
  2. 코드

(python3)

 

2531번: 회전 초밥

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤

www.acmicpc.net

 

두포인터 혹은 슬라이딩 윈도우

윈도우 길이를 k로 유지하고 옆으로 한칸씩 이동시키면서 먹을 수 있는 가짓수를 확인합니다.

이 문제의 파이썬 풀이 10등이네요~ 와~

디테일한건 코드 주석으로 남기겠습니다.

 

코드

import sys
def solution(input) :
    N,d,k,c = list(map(int,input().split()))
    sushi = [int(input().strip()) for _ in range(N)]
    ans = 0
    CNT = [0]*(d+1) # 초밥종류마다 몇개씩 나왔는지
    cnt = 0 # 초밥종류 몇개인지

    for t in sushi[-1:-k-1:-1] : # 초기값 설정 (뒤쪽 k개)
        if CNT[t] == 0 :
            CNT[t]+=1
            cnt+=1
        else :
            CNT[t]+=1

    for i in range(N) : # i가 윈도우의 마지막 인덱스

        if CNT[sushi[i]] == 0 : # 윈도우 마지막 원소 추가
            cnt+=1
        CNT[sushi[i]]+=1

        if CNT[sushi[i-k]] == 1 : # 윈도우 첫 원소 제거
            cnt-=1
        CNT[sushi[i-k]]-=1

        if CNT[c] == 0 : # 쿠폰 포함 가짓수로 최대값 구하기
            ans = max(ans,cnt+1)
        else :
            ans = max(ans,cnt)
    
    print(ans)

input = sys.stdin.readline
solution(input)

 

my solved.ac :

 

solved.ac

알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다.

solved.ac

'Algorithem > 백준 PS with code' 카테고리의 다른 글

백준 #12919 - [G5] A와 B 2 : 거꾸로 해결하기/예외처리  (0) 2023.07.08
백준 #1522 - [S1] 문자열 교환 : 투포인터  (0) 2023.07.07
백준 #17615 - [S1] 공 모으기 : 그리디  (0) 2023.07.05
백준 #1446 - [S1] 지름길 : DP  (0) 2023.07.04
백준 #15989 - [S1] 1,2,3 더하기 4 : DP  (0) 2023.07.03
  1. 두포인터 혹은 슬라이딩 윈도우
  2. 코드
'Algorithem/백준 PS with code' 카테고리의 다른 글
  • 백준 #12919 - [G5] A와 B 2 : 거꾸로 해결하기/예외처리
  • 백준 #1522 - [S1] 문자열 교환 : 투포인터
  • 백준 #17615 - [S1] 공 모으기 : 그리디
  • 백준 #1446 - [S1] 지름길 : DP
jamong5
jamong5
데이터 엔지니어를 희망하는 개발자 지망생
jamong5
JAMONG5
jamong5
전체
오늘
어제
  • 분류 전체보기 (171)
    • Algorithem (92)
      • 백준 PS with code (64)
      • 프로그래머스 PS with code (9)
      • 알고리즘 이론 (3)
    • Languages (19)
      • Python (10)
      • Java (2)
      • C & C++ (7)
    • SQL (42)
      • 프로그래머스 MySQL with code (41)
      • MySQL (1)
    • CS (2)
    • DevOps (4)
      • Docker (1)
      • Git, GitHub (3)
    • 코드 고민 (1)
    • 도움을 받은 정보 (2)
    • 책 (4)
    • 보드 게임 일기 (1)
    • 컴퓨터 일기 (2)
    • R&D 휴지통 (0)

블로그 메뉴

  • 소개
  • 홈
  • 태그

공지사항

인기 글

태그

  • 투포인터
  • 최소힙
  • 파이썬
  • 백준
  • 스택
  • backtracking
  • heapq
  • Python
  • SQL
  • LCS
  • 프로그래머스
  • 구현
  • Git
  • MySQL
  • 그래프탐색
  • 백트래킹
  • 시간초과
  • 똥이
  • join
  • 알고리즘

최근 댓글

최근 글

hELLO · Designed By 정상우.
jamong5
백준 #2531 - [S1] 회전 초밥 : 두포인터
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.