Problem : https://leetcode.com/problems/maximum-score-after-splitting-a-stringDifficulty : EasyStatus : SolvedTime : 00:04:33문제 설명 더보기0, 1로 구성된 문자열 s가 주어졌을 때, 이 문자열을 비어있지 않은 부분 문자열 둘로 나눴을 때 최대 스코어를 반환하라.문자열을 나눈 후의 스코어는 왼쪽 부분문자열의 0의 개수와 오른쪽 부분문자열의 1의 개수의 합이다. 풀이 약간의 창의력 문제.오른쪽의 1의 개수를 먼저 다 세 놓고, 모든 split case를 슬라이딩 윈도우(즉 포인터를 하나씩 옮겨가며) 방식으로 구해볼 수 있다.만약 나누는 부분이 1이면 이면 오른쪽 점수가 1 감소(오른쪽의 1이 하나 왼쪽으로 ..

1422. Maximum Score After Splitting a String

Problem : https://leetcode.com/problems/maximum-score-after-splitting-a-stringDifficulty : EasyStatus : SolvedTime : 00:04:33문제 설명 더보기0, 1로 구성된 문자열 s가 주어졌을 때, 이 문자열을 비어있지 않은 부분 문자열 둘로 나눴을 때 최대 스코어를 반환하라.문자열을 나눈 후의 스코어는 왼쪽 부분문자열의 0의 개수와 오른쪽 부분문자열의 1의 개수의 합이다. 풀이 약간의 창의력 문제.오른쪽의 1의 개수를 먼저 다 세 놓고, 모든 split case를 슬라이딩 윈도우(즉 포인터를 하나씩 옮겨가며) 방식으로 구해볼 수 있다.만약 나누는 부분이 1이면 이면 오른쪽 점수가 1 감소(오른쪽의 1이 하나 왼쪽으로 ..

2025.01.01

Problem : https://leetcode.com/problems/minimum-cost-for-tickets Difficulty : Medium Status : Solved Time : 00:17:48  문제 설명  더보기당신은 미리 일 년치 기차 여행을 계획하고 있습니다. 당신이 일 년간 기차를 탈 일자들이 정수 배열 'days'로 주어집니다. 각각의 day는 1 ~ 365사이의 정수입니다.기차표는 세 가지 다른 방법으로 판매됩니다. costs[0] 달러에 파는 1일 이용권costs[1] 달러에 파는 7일 이용권costs[2] 달러에 파는 30일 이용권 이 이용권들은 연속되는 수 일간의 여행동안 허용됩니다. 예를 들어, 우리가 2일차에 7일 이용권을 샀다면, 우리는 2, 3, 4, 5, 6, 7..

983. Minimum Cost For Tickets

Problem : https://leetcode.com/problems/minimum-cost-for-tickets Difficulty : Medium Status : Solved Time : 00:17:48  문제 설명  더보기당신은 미리 일 년치 기차 여행을 계획하고 있습니다. 당신이 일 년간 기차를 탈 일자들이 정수 배열 'days'로 주어집니다. 각각의 day는 1 ~ 365사이의 정수입니다.기차표는 세 가지 다른 방법으로 판매됩니다. costs[0] 달러에 파는 1일 이용권costs[1] 달러에 파는 7일 이용권costs[2] 달러에 파는 30일 이용권 이 이용권들은 연속되는 수 일간의 여행동안 허용됩니다. 예를 들어, 우리가 2일차에 7일 이용권을 샀다면, 우리는 2, 3, 4, 5, 6, 7..

2024.12.31

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/find-the-power-of-k-size-subarrays-i Difficulty : Medium Status : Solved Time : ??:??:?? 풀이 어떻게 문제를 분류해 볼 수 있을까.. 싶은 문제. 연속 숫자로 sort된 길이를 임시로 저장해가며, 그 길이가 k 이상이면 그 인덱스의 숫자를 (maximum 값이 현재 index임이 충족된다), 그렇지 않다면 -1을 담아 반환하기만 하면 된다. 기본적인 sort 개념을 어떻게 응용해 볼 수 있을까를 물어보는 문제라고 생각한다. 풀이 코드class Solution: def resultsArray(self, nums: List[int], k: int) -> List[int..

Problem : https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/ Difficulty : Medium Status : Solved Time : ??:??:?? 풀이 헤매고 헤매다가 힌트 하나를 보고 깨달은 문제. binary search의 응용 문제이다. 임의의 수 m에 대해서 모든 product를 m 이하가 되도록 나눌때, 이 product의 총 개수가 n이하인지를 검사하면 된다. 이를 기준으로 binary search를 수행해 최소가 되는 m(즉 lower bound)를 찾는 게 목표가 되겠다class Solution: def check(self, n, quantities, target): res..

Problem : https://leetcode.com/problems/count-the-number-of-fair-pairs Difficulty : Medium Status : Solved Time : ??:??:?? 풀이 모바일로 풀어 보는 경우를 생각해서 탬플릿을 단순화해야할까? 싶다. 각설하고, 처음 접근법은 binary search로 풀어보자고 생각했다. lower bound와 upper bound는 O(logN)시간복잡도로 구할 수 있고, 하나의 인자를 고정한 체로 다른 인자에 대해 lower bound와 upper bound를 구할 수 있기 때문이다. 이를테면, lower