Problem : https://leetcode.com/problems/maximum-sum-of-distinct-subarrays-with-length-k/description/ Difficulty : Medium Status : Solved Time : 00:00:00 풀이 간단하긴 한데, 어떻게 더 최적화할지를 생각해보게 되는 문제. 기본적으로는 딕셔너리를 사용하여 distinct한 숫자를 관리하면 된다. k개의 fix된 길이니 슬라이딩 윈도우를 수행하며 조건에 맞을 때마다 정답을 갱신하면 되겠다. 워낙 많이 보이는 타입의 문제다 보니, 최적화가 역시 관건이 될 것 같다. 풀이코드class Solution: def maximumSubarraySum(self, nums: List[int], k: in..

Problem : https://leetcode.com/problems/defuse-the-bomb Difficulty : Easy Status : Solved Time : 00:06:22  문제 설명  풀이 슬라이딩 윈도우 문제. k가 주어진 세 가지 경우일 때를 각각 구현하면 쉽게 풀린다. 시간복잡도는 O(N). 풀이 코드class Solution: def decrypt(self, code: List[int], k: int) -> List[int]: n = len(code) result = [0]*n if k == 0 : return result if k > 0 : result[0] = sum..

Problem : https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists Difficulty : Hard Status : Solved Time : 00:18:12  문제 설명 더보기k개의 단조증가하는 순서(감소하지 않는 순서)로 정렬된 리스트를 가지고 있다. k개의 리스트 각각의 적어도 하나의 수를 포함하는 가장 작은 범위를 구하여라. 우리는 다음 상황 ( b-a  풀이 쪼오금 마음에 안드는 풀이긴 하지만, 이렇게 풀 수 있다! 를 보려주려고 한다. 슬라이딩 윈도우를 생각해 보자. 이 슬라이딩 윈도우는 가급적 k개 집합의 모든 수를 최소한으로 보유하는 게 목적이다. 즉 다음 기능이 필요하다.숫자와 인덱스 정보를 저장할 큐덱에..

Problem : https://www.acmicpc.net/problem/25553 25553번: 단짠단짠 피자 $N$개의 조각으로 이루어진 원형의 피자가 있다. 각 조각은 시계방향으로 $1$번부터 $N$번까지의 번호를 가지고 있으며, 피자가 원형이기 때문에 $N$번 조각 다음에는 $1$번 조각이 있다. 각 조각은 www.acmicpc.net Difficulty : Gold 1 Status : Solved Time : 00:09:28 문제 설명 더보기 N개의 조각으로 이루어진 원형의 피자가 있다. 각 조각은 시계방향으로 1번부터 N번까지의 번호를 가지고 있으며, 피자가 원형이기 때문에 N번 조각 다음에는 1번 조각이 있다. 각 조각은 번호별로 종류가 다른데, 홀수 번호에 해당하는 조각은 파인애플 피자,..

Problem : https://www.acmicpc.net/problem/1306 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net Difficulty : Platinum 5 Status : Solved Time : 00:12:59 문제 설명 더보기 홍준이는 러너이다. 그런데 어쩌다 보니 아무리 뛰어도 뛰어도 속도가 변하지 않는다. 1초에 딱 1칸을 움직인다. 그런데 홍준이가 뛰는 코스는 광고판으로 가득하다. 광고판은 빛의 세기가 다른데, 홍준이는 자신이 볼 수 있는 광고판들 중에서 가..

Problem : https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net Difficulty : Gold 5 Status : Solved Time : 00:34:42 문제 설명 더보기 작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다. 1. 알파벳 소문자로 이루어진 문자열 W가 주어진다. 2. 양의 정수 K가 주어진다. 3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다. 4. 어떤 문자를 정확히..