algorithm/SlidingWindow 4

[백준1522/실버1] 문자열 교환 - JavaScript

https://www.acmicpc.net/problem/1522 문제 조건은1. 모든 a를 한곳에 모아야한다2. 문자열은 원형 구조라 처음과 끝이 이어져있다. 따라서 문제 풀이는1. 최종 완성되어야할 연결된 a의 수 구하기2. 문자열은 원형구조이므로 두배로 이어 붙이기3. 문자열 i부터 i+a 까지 슬라이싱해서 그 안에 있는 b의 수의 최솟값 구하기 # 성공 코드const str = require("fs").readFileSync("/dev/stdin").toString().trim();const aCnt = [...str].filter((c) => c === "a").length;const strDouble = str + str;let result = Number(Infinity);for (let ..

[프로그래머스/Lv2] 보석쇼핑 - Python

https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제를 보고 백준 과일 탕후루 문제랑 비슷하다고 생각났지만(투포인터, 슬라이딩 윈도우) 왠지 그냥 비효율적으로 풀어보고싶어서 냅다 풀어봤는데 당연히 시간초과 나고 정확도 검사도 틀렸다. # 실패 코드 1def solution(gems): answer = [] gems_set = set(gems) gems_dict = {g: 0 for g in gems_set} for idx, gem in enumerate(g..

[백준13144/골드4] List of Unique Numbers - Python

https://www.acmicpc.net/problem/13144 부분수열을 만들떄, 부분 수열의 끝 점을 정한 후 그 점 까지 중복된 수가 안나오는 제일 긴 시작점을 구했다. (for end in range(N))그리고 그 부분수열에서 시작점을 변경하며 나올 수 있는 부분수열의 수를 더해줬다. (end - start + 1) # 성공 코드N = int(input())numbers = list(map(int, input().split()))select = set() # 선택된 수 (슬라이딩 윈도우 안의 수)start = 0 # 시작점result = 0for end in range(N): # 끝점 0번 인덱스부터 끝까지 순회 # 숫자가 중복되면 시작점 제거 후 다음 시작점 탐색 while n..

[백준2531/실1] 회전초밥 - Python

https://www.acmicpc.net/problem/2531   처음엔 그냥 비교할 대상을 덱에 넣고 뺴면서 검사만 해주면 된다고 생각했는데 시간이 너무 오래걸렸다.  첫번째 코드 (python 35316KB, 3496ms | pypy 178300KB, 2200ms)1. deque에 k개의 초밥 올리기2. 최댓값인지 비교3. deque에 popleft 후 append 하면서 다음 비교 준비# python 35316KB, 3496ms# pypy 178300KB, 2200msfrom collections import deque# 연속해서 초밥 k개 먹으면 쿠폰번호 초밥 하나 공짜# result = 초밥 가짓수의 최댓값# 접시 수, 초밥 가짓수, 연속해서 먹는 접시 수, 쿠폰 번호N, d, k, c = ..