알고리즘/코딩 테스트

올바른 괄호 / 균형잡힌 괄호 2가지를 체크하는 함수를 각각 구현한 뒤 문제에서 설명하는 변환 과정 1 ~ 4를 구현 하면 됩니다. 이때 재귀 부분만 신경쓰면 큰 어려움은 없을 듯 합니다. def isbalanced(s): flag = 0 for c in s: if c == '(': flag += 1 elif c == ')': flag -= 1 if flag == 0: return True else: return False def iscorrect(s): stack = [] for c in s: if len(stack) == 0: stack.append(c) else: if c == '(': stack.append(c) elif c == ')': if len(stack) == 0 or stack.pop(..
그냥 무식하게 1개 단위 ~ n-1개 단위 압축 경우의 수를 모두 계산하고 그 중 가장 작은 값은 반환하는 방법으로 해결했습니다. 좀 더 깔끔하게 해결한 코드가 있으면 정리해서 업데이트 하겠습니다.. import math def solution(s): if len(s) == 1: return 1 elif len(set([c for c in s])) == 1: count = len(s) return len(str(count)) + 1 else: answer = len(s) for i in range(1, len(s)): idx = i length = 0 prev = s[:i] count = 1 for j in range(math.ceil(len(s) / i) - 1): curr = s[idx:idx+i] ..
Problem) Solution 1) 2중 for문을 사용해서 인덱스 i + j 값을 활용하여 리스트의 대각선 성분들끼리 묶을 수 있습니다. 예제의 경우 각 위치의 i + j 값은, [[1, 2, 3], [[0, 1, 2], [4, 5, 6], ----> [1, 2, 3], [7, 8, 9]] [2, 3, 4]] 이와 같이 표현할 수 있기 때문에 O(n)의 복잡도로 모든 원소들을 대각선 묶음으로 저장해서 얻은 딕셔너리를 각 키 값의 성분들을 역순으로 출력하면 원하는 값을 얻을 수 있습니다. d = {"0": [0], "1": [2, 4], "2": [3, 5, 7], "3": [6, 8], "4": [9]} 각 리스트들의 역순 reversed_d = {"0": [0], "1": [4, 2], "2": [..
Problem) Solution) class Solution: def arrayPairSum(self, nums: List[int]) -> int: return sum(sorted(nums)[::2])
Problem) Solution) 쉬워 보이지만 제대로된 풀이법을 생각해 내는데 꾀 오랜 시간이 걸렸다.. 계속해서 무식한 방법을 사용하다 보니까 시간 초과가 나서... leetcode 사이트에 discussion에 좋은 설명이 있어서 참조하여 설명글을 정리하겠습니다. 기본 아이디어는 입력받은 리스트 값을 하나씩 단계별로 더해서 sum값을 구할 때, 이 sum값이 k만큼 증가하는 순간에 합이 k값인 subarray를 구할 수 있습니다. 무슨 의미인지 풀어서 설명하겠습니다. 리스트 [1, 2, 1, 3]과 k = 3이 주어진다면, 단계별 sum값들은 [1, 3, 4, 7]이 됩니다. 이때, 1 -> 4인 순간과 4 -> 7인 순간을 통해서 우리는 합이 3인 subarray가 2개 있다는 것을 알 수 있습니..
Problem) Solution) 이전에 풀었던 "Container With Most Water"와 거의 유사한 문제입니다. 길이 n의 배열이 주어지고 배열의 각 값은 위 그림에 보이는 것 같이 'bar'의 길이를 나타냅니다. 이때, 비가 와서 물이 가득 찼을 때의 물의 양을 구하면 됩니다. 풀이법은 n 길이의 배열을 for loop으로 돌리면서 각 단계마다 중심 기둥이 되는 위치의 좌측에서 가장 높은 기둥을 "left", 그리고 우측에서 가장 높은 기둥 "right"라고 정의 합니다. 이때, left와 right중 작은 기둥의 높이 만큼 빗물이 찰 수 있게 되고 따라서 얻은 작은 기둥의 높이에서 중심 기중의 높이의 차이가 실제로 해당 공간에 빗물이 찰 수 있는 공간이 됩니다. 설명이 조금 복잡해 보이는..
Problem) Solution) 먼저 제 첫번째 솔루션 입니다. class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for idx, value in enumerate(nums): if (target - value) in nums: if nums.index(target - value) != idx: return [idx, nums.index(target - value)] 그보다 x20 빠른 솔루션 입니다. class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: d = {} for i, n in enumerate(nums): m = targ..
Problem) 정말 간단한 문자열 뒤집기 문제 입니다. 문제의 핵심은 in-place로 추가 메모리를 사용하지 않고 해결하라는 조건입니다. Solution) class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ left, right = 0, len(s) - 1 while left < right: s[left], s[right] = s[right], s[left] left += 1 right -= 1 left와 right로 처음과 끝의 인덱스를 설정하고 서로 맞바꾸는 방법으로 문자열을 뒤집을 수 있습니다. * 추가적으로 python에서 제공하..
sssssein
'알고리즘/코딩 테스트' 카테고리의 글 목록