알고리즘 13

[카카오] 2020 신입 개발자 블라인드 채용 1차 코딩 - 괄호 변환

올바른 괄호 / 균형잡힌 괄호 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(..

[카카오] 2020 신입 개발자 블라인드 채용 1차 코딩 - 문자열 압축

그냥 무식하게 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] ..

[Leetcode] Diagonal Traverse

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": [..

알고리즘 2020.08.30

[Leetcode] Subarray Sum Equals K

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개 있다는 것을 알 수 있습니..

알고리즘 2020.08.25

[ Leetcode ] Trapping Rain Water

Problem) Solution) 이전에 풀었던 "Container With Most Water"와 거의 유사한 문제입니다. 길이 n의 배열이 주어지고 배열의 각 값은 위 그림에 보이는 것 같이 'bar'의 길이를 나타냅니다. 이때, 비가 와서 물이 가득 찼을 때의 물의 양을 구하면 됩니다. 풀이법은 n 길이의 배열을 for loop으로 돌리면서 각 단계마다 중심 기둥이 되는 위치의 좌측에서 가장 높은 기둥을 "left", 그리고 우측에서 가장 높은 기둥 "right"라고 정의 합니다. 이때, left와 right중 작은 기둥의 높이 만큼 빗물이 찰 수 있게 되고 따라서 얻은 작은 기둥의 높이에서 중심 기중의 높이의 차이가 실제로 해당 공간에 빗물이 찰 수 있는 공간이 됩니다. 설명이 조금 복잡해 보이는..

알고리즘 2020.08.24

[Leetcode] Reverse String

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에서 제공하..

알고리즘 2020.08.19

[Leetcode] Valid Palindrome

Problem) 간단한 문자열 문제입니다. 코딩 문제로 문자열과 정규식 관련 문제를 은근히 자주 마주칠 수 있는데요. 이번 문제를 통해서 다시 한번 문자열 관련 다양한 처리 방법들에 대해서 정리해보면 좋을 것 같네요. Solution) # 문자열 활용 솔류션 class Solution: def isPalindrome(self, s: str) -> bool: strs = [] for char in s: if char.isalnum(): strs.append(char.lower()) while len(strs) > 1: if strs.pop(0) != strs.pop(): return False return True # 정규식 활용 솔류션 import re class Solution: def isPalind..

알고리즘 2020.08.18

[Leetcode] Container With Most Water

solution for Container With Most Water Problem) Solution) 2개의 포인터를 활용해서 시간 복잡도 O(n)에 끝낼 수 있다. max_water 변수에는 각 단계별 최대 물의 양을 저장한다. x, y 포인터 초기화하고 각각 x는 시작점, y는 끝점에 위치하고 하나씩 옮기며 최대 물의 양을 계산하고 max_water의 값과 비교하여 최종 최대 물의 양 값을 얻는다. 이때 포인터를 옮기는 과정에서 x, y 포인터가 가르키는 막대의 길이를 비교하여 길이가 짧은 막대의 포인터를 x는 +1, y는 -1로 한칸씩 옮겨야 한다. Example의 예를 들면 최초 x는 0 (height[0] = 1)을 가르키고 y는 8 (height[8] = 7)을 가르킨다. 여기서 물의 양을 ..

알고리즘 2020.06.04