코딩테스트/Python

🔗 Problem Linkhttps://leetcode.com/problems/find-the-highest-altitude/description/❔Thinking현재의 높이 0에서 주어지는 높이와의 차이를 순차적으로 계산하고(= net gain altitude) 업데이트한다.모든 net gain altitude 가운데에 가장 큰 값을 반환한다.💻Solutiondef largestAltitude(self, gain: List[int]) -> int: net_gain = [0] for h in gain: net_gain.append(net_gain[-1] + h) return max(net_gain)🗝️keypoint리스트 선언의 필요 없이, 두개의 변수를 통해 max 값..

🔗 Problem Linkhttps://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/description/❔Thinking0과 1로 숫자 배열 nums가 주어질 때, 0 한 개를 제거하여 만들 수 있는 가장 긴 1 부분수열의 길이를 반환한다.[1,1,0,1] 이라면 111이므로 3 반환💻Solutiondef longestSubarray(self, nums: List[int]) -> int: delete_cnt = 1 left = 0 longest_len = 0 for right in range(len(nums)): if nums[right] == 0: delete_..

🔗 Problem Linkhttps://leetcode.com/problems/max-consecutive-ones-iii/description/❔Thinking0과 1로 이루어진 숫자 배열이 주어질 때, k개의 0을 1로 바꾸어 만들 수 있는 1 부분 수열의 최대 길이를 반환한다.ex - 0 0 1 1 1 0 1, k=1 이라면 111 0 1에서 0을 1로 바꾸어 11111을 만들 수 있으므로 5 반환💻Solution1. left, right Two-Pointer를 활용한 풀이left와 right로 0을 1로 바꾼 횟수가 k를 넘지 않도록 window 구성만약 현재 0을 1로 바꾼 횟수가 k를 넘은 경우, left를 이동하여 cur_zero_cnt를 k보다 작게 유지한다.right-left+1로 w..

🔗 Problem Linkhttps://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/❔Thinking문자열 s와 정수 k가 주어질 때, k개의 문자를 가지는 s의 부분 문자열 가운데에서 모음(a,e,i,o,u)이 최대 몇 개인지 반환한다.s = 'abciiidef', k = 3 인 경우 output은 3이다. (부분 문자열 'iii')s = 'aeiou', k = 2 인 경우 output은 2이다 (어떤 부분 문자열이라도 2) 💻Solution1. two-pointer를 활용한 풀이def maxVowels(self, s: str, k: int) -> int: left = 0 ..

🔗 Problem Linkhttps://www.acmicpc.net/problem/1013❔Thinking주어진 패턴 "(100+1+ | 01)+"과 일치하는 문자열인 경우 "YES", 아니라면 "NO"를 반환한다.💻Solutionimport reimport sysinput = sys.stdin.readlineT = int(input().rstrip())r = re.compile("(100+1+|01)+")for _ in range(T): pattern = input().rstrip() if r.fullmatch(pattern): print('YES') else: print('NO')🗝️keypointre로 compile하면, r을 해당 패턴을 검색하는데 활..

🔗 Problem Linkhttps://leetcode.com/problems/maximum-average-subarray-i/description/❔Thinking숫자 배열 nums와 k가 주어질 때, k개의 연속된 부분 수열 중 가장 큰 평균을 반환한다.💻Solution1. 평균으로 비교하기def findMaxAverage(self, nums: List[int], k: int) -> float: max_avg = -(10**4 * 10**5 + 1) left, right = 0, 0 window_sum = 0 while right 0 else -(-window_sum / k)) window_sum -= nums[left] left = ..