개발하는 개구리

🐸 문제 정보 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 🤖 알고리즘 슬라이딩 윈도우 ⏱️ 풀이 시간 47.30m 📝 풀이 슬라이딩 윈도우의 정석 같은 문제였다. 풀이 자체가 복잡하지 않은데도, 처음에 k개까지 초기 설정하는 부분에서 헛디뎌서 검색까지했다. 0부터 k-1번 접시까지 개수를 딕셔너리에 초기화한다. 이 때, 쿠폰 접시의 경우 기본적으로 1개를 추가해준다 이후 반복문을 돌면서 start가 n에 닿기 전까지 k개를 슬라이딩 윈도우하며 비교한다. 이 때,..

🐸 문제 정보 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 🤖 알고리즘 슬라이딩 윈도우 ⏱️ 풀이 시간 14.58m 📝 풀이 최근에 투포인터랑 슬라이딩 윈도우를 많이 풀어서 쉽게 풀 수 있었다. start = 0, end = k로 시작한다. (어차피 k개는 필수로 들어가야하기 때문) 이때 사이에 있는 1의 값은 미리 카운트하여 선언한다. end가 n이 될 때까지 아래 조건에 따라 인덱스를 움직이며 계산한다. 1의 개수가 k개와 같다면 현재 거리를 res와 비교하여 최솟값으로 저장한다 start 인덱스에..

🐸 문제 정보 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 🤖 알고리즘 슬라이딩 윈도우 ⏱️ 풀이 시간 36.01m 📝 풀이 문제집을 거의 다 풀어가니까 자꾸 푼 알고리즘이 겹쳐서 나오는 것 같다. 물론 이번 문제는 많이 어려웠다..! 역시 문제 이해를 잘못했기 때문이다. 특정 구간에 있는 모든 문자의 개수가 동일한 경우를 찾아야한다고 생각했다... 다시 한 번 문제를 제대로 이해해야겠다는 다짐을 했다. 문제를 제대로 이해하면 풀이 아이디어 자체는 크게 어렵지 않다. 입력된 문자열에서 각 문자가 등장하는..

🐸 문제 정보 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net 🤖 알고리즘 슬라이딩 윈도우 ⏱️ 풀이 시간 30m+ 📝 풀이 교환이라는 단어의 뜻이 명확하게 서술되어있지 않아서 한 번 이상하게 풀었다가 다시 풀었다. 이 문제에서 말하는 교환은, 단어 안에서 각 글자간 위치를 변경하는 경우를 말한다. (질문 게시판에 나와 같은 사람이 꽤 있었다...) 우선 문제는 슬라이딩 윈도우로 풀면 그렇게 어렵지 않다. 입력받은 문자열에서 a의 개수를 센다 문자열에서 a개씩 슬라이딩 윈도우하며, 해당 위치에 b의 개수의 최소값..

🐸 문제 정보 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 🤖 알고리즘 슬라이딩 윈도우 ⏱️ 풀이 시간 30m + (체크를 못했다...) 📝 풀이 조금 신기한..? 이상한..? 문제였다. 슬라이딩 윈도우로 푸는데, 조건문으로 검사하지 않고 모든 경우에서 적용할 수 있도록 코드를 작성하면 시간초과가 발생했다. 틀린 코드는 아래에서 볼 수 있다. 더보기 import sys input = sys.stdin.readline n, d, k, c = map(int, input(..