중복 문자 제거 문제 중복된 문자를 제외하고 사전식 순서로 나열하라. 예제1 입력 "bcabc", 출력 "abc" 예제2 입력 "cbacdcbc", 출력 "acdb" 코드 정답 # 재귀 class Solution: def removeDuplicateLetters(self, s: str) -> str: # 집합으로 정렬 for char in sorted(set(s)): suffix = s[s.index(char):] # 전체 집합과 접미사 집합이 일치할때 분리 진행 if set(s) == set(suffix): return char + self.removeDuplicateLetters(suffix.replace(char, '')) return '' # 스택 import collections class So..
연결 리스트를 이용한 스택 ADT 구현 코드 class Node: def __init__(self, item, next): self.item = item self.next = next class Stack: def __init__(self): self.last = None def push(self, item): self.last = Node(item, self.last) def pop(self): item = self.last.item self.last = self.last.next return item stack = Stack() stack.push(1) stack.push(2) stack.push(3) stack.push(4) stack.push(5) 헷갈린 부분 처음에 Stack 클래스가 만들어지면..
역순 연결 리스트 Ⅱ 문제 인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다. 입력 1→2→3→4→5→NULL, m = 2, n = 4 출력 1→4→3→2→5→NULL 코드 class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode: if not head or m == n: return head root = start = ListNode(None) root.next = head for _ in range(m - 1): start = start.next end = star..
페어의 노드 스왑 문제 문제링크 연결 리스트를 입력받아 페어(pair) 단위로 스왑하라 입력 1→2→3→4 출력 2→1→4→3 코드 class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def swapPairs(self, head: ListNode) -> ListNode: root = prev = ListNode(None) prev.next = head while head and head.next: #fixme b가 head를 가리키도록 할당 b = head.next head.next = b.next b.next = head #fixme prev가 b를 가리키도록 할당 prev.next = b #fixme ..
숫자형 리스트를 단일 값으로 병합하기 a = [1, 2, 3, 4, 5]처럼 숫자형으로 이루어진 리스트가 있을 때 이를 하나로 합치는 좀 더 우아한 코드를 만들어 보자. >>> ''.join(str(e) for e in a) '12345' 이 방식의 코드는 아무래도 가독성이 떨어지고 영 보기가 좋지 않다. 좀 더 깔끔한 방법은 없을까? >>> ''.join(map(str, a)) '12345' 이 경우 임시 변수 e를 사용하지 않아 깔끔하며, map(str,로 이어지는 부분이 문자열로 변환을 암시하는 듯하여 가독성도 좋다. 코드 크기가 줄어듦은 물론이다. >>> functools.reduce(lambda x, y: 10 * x + y, a, 0) 12345 이런 식으로 처리할 수 있을 것 같다. func..
리트코드 Group Anagrams from typing import List import collections class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: anagrams = collections.defaultdict(list) for word in strs: anagrams[''.join(sorted(word))].append(word) print(anagrams) return anagrams.values() if __name__ == '__main__': s = Solution() print(s.groupAnagrams(["eat","tea","tan","ate","nat","bat"])) sorted()는..
re 모듈 sub 함수 정규식과 매치되는 부분을 다른 문자로 바꾸어준다. sub 메서드의 첫 번째 매개변수는 바꿀 문자열이 되고, 두 번째 매개 변수는 대상 문자열이 된다. 그런데 딱 한 번만 바꾸고 싶은 경우도 있다. 이렇게 바꾸기 횟수를 제어하려면 다음과 같이 세 번째 매개변수로 count값을 넘기면 된다. import re s = "A man, a plan, a canal: Panama" s = re.sub('[^0-9a-z]', '', s) # 영어 소문자, 숫자 빼고 나머지 다 없앰. print(s) # s = "manaplanacanalanama" s = "A man, a plan, a canal: Panama" s = re.sub('[^0-9a-z]', '', s, count=1) print..
isalnum 함수 isalnum()는 영문자, 숫자 여부를 판별하는 함수 lower 함수 모두 소문자로 변환한다. class Solution: def isPalindrome(self, s: str) -> bool: strs: Deque = collections.deque() for char in s: if char.isalnum(): #영문자, 숫자 여부를 판별 strs.append(char.lower()) # 모두 소문자 변환 while len(strs) > 1: if strs.popleft() != strs.pop(): return False return True 출처 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]
typing 모듈 타입 어노테이션을 사용하다 보면 리스트, 사전, 터플, 세트와 같은 파이썬 내장 자료 구조에 대한 타입을 명시해야 할 때가 있습니다. 이럴 때는 typing 모듈에서 제공하는 List, Dict, Tuple, Set를 사용하여 타입 어노테이션을 추가한다. from typing import Deque class Solution: def isPalindrome(self, s: str) -> bool: strs: Deque = collections.deque() for char in s: if char.isalnum(): strs.append(char.lower()) while len(strs) > 1: if strs.popleft() != strs.pop(): return False ret..
제너레이터 제너레이터는 루프의 반복 동작을 제어할 수 있는 루틴 형태를 말한다. 예를 들어 임의의 조건으로 숫자 1억 개를 만들어내 계산하는 프로그램을 작성한다고 가정해보자. 이 경우 제너레이터가 없다면 메모리 어딘가에 만들어낸 숫자 1억 개를 보관하고 있어야 하낟. 그러나 제너레이터를 이용하면, 단순히 제너레이터만 생성해두고 필요할 때 언제든 숫자를 만들어낼 수 있다. 이때 yield 구문을 사용하면 제너레이터를 리턴할 수 있다. 기조느이 함수는 return 구문을 맞닥뜨리면 값을 리턴하고 모든 함수의 동작을 종료한다. 그러나 yield는 제너레이터가 여기까지 실행 중이던 값을 내보낸다는 의미로, 중간 값을 리턴한 다음 함수는 종료되지 않고 계속해서 맨 끝에 도달할 때까지 실행된다. yield의 값을 ..
locals locals()는 로컬 심볼 테이블 딕셔너리를 가져오는 메소드로 업데이트 또한 가능하다. 여기서는 딕셔너리를 가져오는 부분에 집중해 살펴보자면, 로컬에 선언된 모든 변수를 조회할 수 있는 강력한 명령이므로 디버깅에 도움이 된다. 변수명을 일일이 찾아낼 필요 없이 로컬 스코프에 정의된 모든 변수를 출력하기 떄문에 편리하다. import pprint pprint.pprint(locals()) """ {'__annotations__': {}, '__builtins__': , '__cached__': None, '__doc__': None, '__file__': '3.py', '__loader__': , '__name__': '__main__', '__package__': None, '__spec_..
sort + ramda 람다 표현식이란 식별자 없이 실행 가능한 함수를 말하며, 함수 선언 없이도 하나의 식으로 함수를 단순하게 표현할 수 있다. letters = ['let1 art can', 'let2 own kit dig', 'let3 art zero'] letters.sort(key=lambda x : (x.split()[1:], x.split()[0])) # 출력 : ['let1 art can', 'let3 art zero', 'let2 own kit dig'] 식별자를 제외한 문자열 [1:]을 키로 하여 정렬하며, 동일한 경우 후순위로 식별자 [0]를 지정해 정렬되도록, 람다 표현식을 이용해 정렬할 수 있다. 출처 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]
print 리스트를 출력할 떄는 join()으로 묶어서 처리한다. a = ['A', 'B'] print(' '.join(a)) # A B 다음과 같이 idx와 fruit이 정의되 있을 때 가장 선호되는 print() 방법은 f-string이다. 변수를 뒤에 별도로 부여할 필요 없이 마치 템플릿을 사용하듯 인라인으로 삽입할 수 있어 편리하게 사용할 수 있다. idx = 1 fruit = "Apple" print(f'{idx +1}: {fruit}') # 2: Apple 출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호)
타입 힌트 오류 확인 mypy를 사용하면 타입 힌트에 오류가 없는지 자동으로 확인 할 수 있으므로 이를 통해 수정 할 수 있다. 타입 힌트가 잘못 지정된 코드는 다음과 같이 InCompatible return value type 오류가 발생하므로 확인 후 직접 코드를 수정할 수 있다. $ mypy solution.py 출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호)
카멜 케이스와 스네이크 케이스 카멜 케이스 단어를 대소문자로 구분하여 섞어서 작명하는 방식으로, 자바의 대표적인 표기 방식이기도 하다. 스네이크 케이스 각 단어를 언더스코어로 구분한다. 일반적으로 모두 소문자로 표기하지만 경우에 따라 시작 문자는 대문자로 표기하기도 한다. 연구 결과에 따르면 스네이크 케이스가 카멜 케이스보다 훨씬 더 인지하기 쉽다고 한다. 파이썬은 PEP8을 통해 스네이크 케이스 방식의 네이밍 컨벤션을 권장한다. camelCase: int = 1 snake_case: int = 1 네이밍 컨벤션 파이썬의 변수명 네이밍 컨벤션은 자바와 달리 각 단어를 밑줄(_)로 구분하여 표기하는 스네이크 케이스를 따른다. 이는 함수명도 마찬가지다. 특히 파이썬은 파이썬다운 방식에 굉장한 자부심이 있어서..
구조체 파이썬에는 구조체가 없을 뿐더러 클래스 또한 데이터 타입을 지정할 수 없어, 구조체와 같은 형태를 정의하려면 네임드 튜플을 사용해야 했다. from collections import namedtuple MyStruct = namedtuple("MyStruct", "field1 field2 field3") m = MyStruct("foo", "bar", "baz") 위처럼 정의해 사용하는 방법밖에 없었는데, 파이썬 3.7부터 dataclass를 지원하며, @dataclass 데코레이션으로 타입 힌트와 함께 활용함으로써 다음과 같이 class를 이용해 구조체 형태로 정의할 수 있다. from dataclasses import dataclass @dataclass class Product: weight..