우노

문제 링크 https://www.acmicpc.net/problem/3078 풀이 문제에 대한 설명이 길지만, 결국 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구 쌍이 얼마나 있는지를 찾는 문제입니다. 해당 문제는 슬라이딩 윈도우 알고리즘을 사용해 해결할 수 있습니다. 딕셔너리를 사용해, k 크기를 가지는 윈도우 내에 존재하는 학생들을 {이름 길이 : 인원} 형식으로 저장합니다. 윈도우를 오른쪽으로 한 칸씩 이동하며, 윈도우에서 빠지는 학생은 딕셔너리에서 제거하고, 윈도우에 추가되는 학생은 딕셔너리에 추가합니다. 이때, 추가되는 학생의 이름 길이와 동일한 길이가 딕셔너리에 존재한다면, 친구 쌍의 개수를 +1 해줍니다. 코드 import sys from collections import d..

문제 링크 https://www.acmicpc.net/problem/15961 풀이 슬라이딩 윈도우 알고리즘과 딕셔너리를 사용해서 해결할 수 있습니다. 윈도우의 크기를 k로 설정한 뒤, 윈도우를 오른쪽으로 한 칸씩 이동하며, 구간 내에 존재하는 접시의 종류별 개수를 파악하면 됩니다. 참고 회전 초밥 벨트는 원형으로 이루어져있기 때문에, 오른쪽 인덱스는 오른쪽 인덱스를 접시의 수로 나눈 나머지를 사용하면 됩니다. 구간 내에는 항상 쿠폰 번호가 포함되어 있다고 가정합니다. 코드 import sys from collections import defaultdict # n : 회전 초밥 벨트에 놓인 접시의 수 # d : 초밥의 가짓수 # k : 연속해서 먹는 접시의 수 # c : 쿠폰 번호 n, d, k, c =..

문제 링크 https://www.acmicpc.net/problem/2531 풀이 슬라이딩 윈도우 알고리즘과 딕셔너리를 사용해서 해결할 수 있습니다. 윈도우의 크기를 k로 설정한 뒤, 윈도우를 오른쪽으로 한 칸씩 이동하며, 구간 내에 존재하는 접시의 종류별 개수를 파악하면 됩니다. 참고 회전 초밥 벨트는 원형으로 이루어져있기 때문에, 오른쪽 인덱스는 오른쪽 인덱스를 접시의 수로 나눈 나머지를 사용하면 됩니다. 구간 내에는 항상 쿠폰 번호가 포함되어 있다고 가정합니다. 코드 import sys from collections import defaultdict # n : 회전 초밥 벨트에 놓인 접시의 수 # d : 초밥의 가짓수 # k : 연속해서 먹는 접시의 수 # c : 쿠폰 번호 n, d, k, c = ..

문제 링크 https://www.acmicpc.net/problem/10025 풀이 슬라이딩 윈도우 알고리즘을 활용하여 해결할 수 있습니다. 양동이의 좌표별 얼음 양은 1차원 배열에 저장합니다. 1차원 배열의 크기는 최대 크기인 1000001로 생성합니다. 윈도우의 범위는 (2 * k) + 1 로 설정합니다. 특정 위치에서 앞뒤로 k 만큼의 범위를 포함하기 때문입니다. 반복문을 돌며 윈도우 범위 내의 얼음의 양을 계산하고, 최댓값을 비교해나갑니다. 윈도우를 한 칸씩 이동하며, 윈도우의 맨 앞에 있었던 값은 윈도우의 합에서 빼고 윈도우의 맨 뒤에 추가되는 값은 윈도우의 합에 더해줍니다. 코드 import sys n, k = map(int, sys.stdin.readline().split(" ")) # 양동..