list(map(lambda x:x+10, [1,2,3]))
[n*2 for n in range(1, 10+1) if n % 2==1]
a=[]
for n in range(1, 10+1):
if n % 2 == 1:
a.append(n*2)
a
a={key:value for key, value in original.items()}
str1 ="ajdASD"
import re
[
str1[i:i+2].lower() for i in range(len(str1)-1)
if re.findall('[a-z]{2}', str1[i:i+2].lower())
]
결과: ['aj', 'jd', 'da', 'as', 'sd']
try:
print(a[9])
except IndexError:
print('존재하지 않는 인덱스')
---
a=dict()
a={'k1':'v1', 'k2':'v2'}
a['k3']='v3' # 별도로 값을 선언해서 넣어줌
a
>>> {'k1':'v1', 'k2':'v2', 'k3':'v3'}
팰린드롬: 앞뒤가 똑같은 단어나 문장, 뒤짚어도 같은 말이 되는 단어 또는 문장
def isPalindrom(s):
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 # 모두다 통과한 경우 True를 반환
s="race a car"
isPalindrom(s)
>>> False
def isPalindrome(s):
# 자료형 데크로 선언
strs : Deque = collections.deque()
for char in s:
if char.isalnum():
strs.append(char.lower())
while len(strs)>1:
if strs.popleft() != strs.pop(): # .popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제
return False
return True
def isPalindrome(s):
s=s.lower()
# 정규식으로 불필요한 문자 필터링
s=re.sub('[^a-z0-9]','',s)
return s==s[::-1]
문자열 슬라이싱
- s='안녕하세요'
- s[-1] == 요
- s[:-3] == 안녕(뒤에서 3개 글자 앞까지)
- s[-3:] == 하세요(뒤에서 3번째 문자부터 마지막까지)
- s[::1] == 안녕하세요(기본값)
- s[::-1] == 요세하녕안(뒤짚어줌)
- s[::2] == 안하요(2칸씩 앞으로 이동)
def reverseString(s):
left, right = 0, len(s)-1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -=1
return s
s=['h','e','l']
reverseString(s)
>>> ['l', 'e', 'h']
def reverseString(s):
s.reverse()
return s
def reverseString(s):
s[:] = s[::-1]
return s
def reorderLogFiles(logs):
letters, digits = [], []
for log in logs:
if log.split()[1].isdigit():
digits.append(log)
else:
letters.append(log)
# 2개의 키를 람다 표현식으로 정렬
letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))
digits.sort(key=lambda x: (x.split()[1:], x.split()[0]))
return letters + digits
logs = ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]
reorderedLogs = reorderLogFiles(logs)
print(reorderedLogs)
>>>['let1 art can', 'let3 art zero', 'let2 own kit dig', 'dig2 3 6', 'dig1 8 1 5 1']
2개의 키를 람다 표현식으로 정렬하는 방법
- sorted(s) 사용시 ['1A', '1B', '2A', '4C']
s= ['2A', '1B', '4C', '1A'] s.sort(key=lambda x:(x.split()[1], x.split()[0])) s >> ['1A', '2A', '1B', '4C']
sorted()의 key 옵션
- 예시 1
c=['ccc', 'aaaa', 'd', 'bb'] sorted(c, key=len) >> ['d', 'bb', 'ccc', 'aaaa']
- 예시 2
a= ['cde', 'cfc', 'abc'] def fn(s): return s[0], s[-1] # 첫 문자열과 마지막 문자열 순으로 정렬 print(sorted(a, key=fn)) >> ['abc', 'cfc', 'cde']
- 예시2-1 람다로
sorted(a, key=lambda s: (s[0], s[-1]))
import re
from collections import Counter
def mostCommonWord(para, banned):
words= [word for word in re.sub(r'[^\w]', ' ', para)
.lower().split()
if word not in banned]
counts = collections.Counter(words)
return counts.most_common(1)[0][0]
mostCommonWord("bob hit a ball, the hit BALL flew far after it was hit", ['hit'])
>>> 'ball'
from collections import Counter
def groupAnagrams(strs):
anagrams = collections.defaultdict(list)
for word in strs:
anagrams[''.join(sorted(word))].append(word)
return anagrams.values()
groupAnagrams(['eat','tea','tan','ate','nat','bat'])
>>> dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])
팰린드롬: 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열
def longestPalindrome(s):
# 팰린드롬 판별 및 투 포인터 확장
def expand(left:int, right:int):
while left >= 0 and right <= len(s) and s[left] == s[right-1]:
left -= 1
right += 1
return s[left +1:right-1]
# 해당 사항이 없을 때 빠르게 리턴
if len(s) < 2 or s == s[::-1]: # 길이가 2보다 짧거나, 뒤짚었을때 원래 같은 경우
return s
result = ''
# 슬라이딩 윈도우 우측으로 이동
for i in range(len(s)-1):
result = max(result,
expand(i, i+1),
expand(i, i+2),
key=len)
return result
longestPalindrome('babad')
>>> 'bab'
배열: 값 또는 변수 엘리먼트의 집합으로 구성된 구조, 하나 이상의 인덱스 또는 키로 식별
추상자료형(ADT)의 실제 구현 대부분은 배열, 연결 리스트를 기반
예) 스택 -> 연결 리스트로 구현, 큐 -> 배열로 구현 (반대도 가능)
배열: 고정된 크기만큼의 연속된 메모리 할당
덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스 리턴하기
def twoSum(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i]+nums[j] == target:
return [i, j]
twoSum([2,7,11,15],9)
>>> [0,1]
def twoSum(nums, target):
for i, n in enumerate(nums):
complement = target -n
if complement in nums[i+1:]:
return nums.index(n), nums[i+1:].index(complement)+(i+1)
twoSum([2,7,11,15],9)
>>> (0,1)
def twoSum(nums, target):
nums_map = {}
# 키와 값을 바꿔서 딕셔너리로 저장
for i, num in enumerate(nums):
nums_map[num] = i
# 타겟에서 첫 번째 수를 뺸 결과를 키로 조회
for i, num in enumerate(nums):
if target - num in nums_map and i != nums_map[target-num]:
return nums.index(num), nums_map[target-num]
def twoSum(nums, target):
nums_map ={}
# 하나의 for문으로 통합
for i, num in enumerate(nums):
if target - num in nums_map:
return [nums_map[target-num], i]
nums_map[num] = i
def twoSum(nums, target):
left, right = 0, len(nums)-1
while not left == right:
# 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로
if nums[left] + nums[right] < target:
left +=1
# 합이 타겟보다 작으면 왼쪽 포인터를 오른쪽으로
elif nums[left] + nums[right] > target:
right -= 1
else:
return left, right
높이를 입력 받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하기
def trap(height):
if not height:
return 0
volume = 0
left, right = 0, len(height)-1
left_max, right_max = height[left], height[right]
while left < right:
left_max, right_max = max(height[left], left_max),max(height[right], right_max)
# 더 높은 쪽을 향해 투 포인터 이동
if left_max <= right_max:
volume += left_max - height[left]
left += 1 # 오른쪽이 크다면, 왼쪽으로 이동
else:
volume += right_max - height[right]
right -= 1 # 오른쪽이 이동
return volume
trap([0,1,0,2,1,0,1,3,2,1,2,1])
>>> 5
def trap(height):
stack = []
volume = 0
for i in range(len(height)):
# 변곡점을 만나는 경우
while stack and height[i] > height[stack[-1]]:
# 스택에서 꺼낸다
top = stack.pop()
if not len(stack):
break
# 이전과의 차이만큼 물 높이 처리
distance = i - stack[-1] -1
waters = min(height[i], height[stack[-1]])-height[top]
volume += distance * waters
stack.append(i)
return volume
배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트 출력하기
def threeSum(nums):
results = []
nums.sort()
# 브루트 포스 n^3 반복
for i in range(len(nums)-2):
# 중복된 값 건너뛰기
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, len(nums)-1):
if j>i+1 and nums[j] == nums[j-1]:
continue
for k in range(j+1, len(nums)):
if k>j+1 and nums[k] == nums[k-1]:
continue
if nums[i] + nums[j] + nums[k] == 0:
results.append((nums[i], nums[j], nums[k]))
return results
threeSum([-1,0,1,2,-1,-4])
def threeSum(nums):
results = []
nums.sort()
for i in range(len(nums)-2):
# 중복된 값 건너뛰기
if i > 0 and nums[i] == nums[i-1]:
continue
# 간격을 좁혀가며 합 sum 계산
left, right = i+1, len(nums)-1
while left < right:
sum=nums[i]+nums[left]+nums[right]
if sum < 0:
left += 1
elif sum > 0:
right -= 1
else:
# sum=0인 경우이므로 정답 및 스킵 처리
results.append((nums[i], nums[left], nums[right]))
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
return results
n개의 페어를 이용한 min(a,b)의 합을 만들 수 있는 가장 큰 수를 출력하라
def arrayPairSum(nums):
sum = 0
pair =[]
nums.sort()
for n in nums:
# 앞에서부터 오름차순으로 페어를 만들어서 합 계산
pair.append(n)
if len(pair) == 2:
sum += min(pair)
pair= []
return sum
def arrayPairSum(nums):
sum=0
nums.sort()
for i, n in enumerate(nums):
# 짝수번째 값의 합 계산
if i % 2 == 0:
sum += n
return sum
def arrayPairSum(nums):
return sum(sorted(nums)[::2])
배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라(나눗셈을 하지 말고 풀이하라)
def productExceptSelf(nums):
out=[]
p=1
# 왼쪽 곱셈
for i in range(0, len(nums)):
out.append(p)
p=p*nums[i]
p=1
# 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
for i in range(len(nums)-1,0-1, -1):
out[i]=out[i]*p
p=p*nums[i]
return out
한 번의 거래로 낼 수 있는 최대 이익 산출하기
def maxProfit(prices):
max_price = 0
for i, price in enumerate(prices):
for j in range(i, len(prices)):
max_price=max(prices[j]-price, max_price)
return max_price
maxProfit([7,1,5,3,6,4])
import sys
def maxProfit(prices):
profit = 0
min_price = sys.maxsize
# 최소값과 최대값을 계속 갱신
for price in prices:
min_price = min(min_price, price)
profit = max(profit, price-min_price)
return profit
파이썬 최대 최소 지정하기
mx=-sys.maxsize mn=sys.maxsize # 무한대 지정 mx = float('-inf') mn = float('inf
파이썬 리스트 노드
- 방법 1 리스트 변환
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): # 연결리스트에 요소 추가하면서 가장 마지막 값을 next로 지정, 포인터인 last는 가장 마지막으로 이동
self.last = Node(item, self.last)
def pop(self): # 가장 마지막 아이템 꺼내고, last 포인터를 한 칸 앞으로 전진(이전에 추가된 값을 가리키게)
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)
for _ in range(5):
print(stack.pop())
괄호로 된 입력값이 올바른지 판별하기
(, [, {는 스택에 push하고 스택에서 pop한 결과가 ),},]를 만났을 때 일치하는지 확인하기
매핑 테이블을 만들고 테이블에 존재하지 않으면 푸시하고 팝했을 때 결과가 일치하지 않으면 False를 리턴하도록 구현
pop은 가장 최근에 삽입된 요소를 제거함
def isValid(s)-> bool:
stack = []
table= {
')':'(',
'}':'{',
']':'[',
}
# 스택 이용 예외 처리 및 일치 여부 판별
for char in s:
if char not in table:
stack.append(char)
elif not stack or table[char] != stack.pop():
return False
return len(stack) == 0
isValid('(}')
>>> False
중복된 문자를 제외하고 사전식 순서로 나열하기
사전식 순서: 사전에서 가장 먼저 찾을 수 있는 순서
def removeDuplicateLetters(s):
#집합으로 정렬
for char in sorted(set(s)):
suffix = s[s.index(char):]
# 전체 집합과 접미사 집합이 일치할 때 분리 진행
if set(s) == set(suffix):
return char + removeDuplicateLetters(suffix.replace(char,''))
return ''
removeDuplicateLetters('cbacdcbc')
>>> 'acdb'
def removeDuplicateLetters(s):
counter, seen, stack = Counter(s), set(), []
for char in s:
counter[char] -= 1
if char in seen:
continue
# 뒤에 붙일 문자가 남아 있다면 스택에서 제거
while stack and char < stack[-1] and counter[stack[-1]]>0:
seen.remove(stack.pop())
stack.append(char)
seen.add(char)
return ''.join(stack)
from collections import Counter
removeDuplicateLetters('cbacdcbc')
매일의 화씨 온도 리스트를 입력 받아서 더 따뜻한 날씨를 위해서 며칠을 기다려야 하는지 출력하기
def dailyTemperatures(T):
answer = [0]*len(T)
stack = []
for i, cur in enumerate(T):
# 현재 온도가 스택 값보다 높다면 정답 처리
while stack and cur > T[stack[-1]]:
last = stack.pop()
answer[last]=i-last
stack.append(i)
return answer
dailyTemperatures([73,74,75,71,69,72,76,73])
>>> [1, 1, 4, 2, 1, 1, 0, 0]
class MyStack:
def __init__(self):
self.q = collections.deque()
def push(self, x):
self.q.append(x)
# 요소 삽입 후 맨 앞에 두는 상태로 재정렬
for _ in range(len(self.q)-1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return len(self.q) == 0
class MyQueue:
def __init__(self):
self.input = []
self.output = []
def push(self, x):
self.input.append(x)
def pop(self):
self.peek()
return self.output.pop()
def peek(self):
# output이 없으면 모두 재입력
if not self.output:
while self.input:
self.output.append(self.input.pop())
return self.output[-1]
def empty(self):
return self.input == [] and self.output == []
원형 큐: INFO구조
class MyCircularQueue:
def __init__(self, k: int):
self.q = [None] * k
self.maxlen = k
self.p1 = 0
self.p2 = 0
# enQueue(): 리어 포인트 이동
def enQueue(self, value: int) -> bool:
if self.q[self.p2] is None:
self.q[self.p2] = value
self.p2 = (self.p2 +1) % self.maxlen
return True
else
return False
# deQueue(): 프론트 포인터 이동
def deQueue(self) -> bool:
if self.q[self.p1] is None:
return False #이미 내보낼것이 없는 상태 ->False
else:
self.q[self.p1] = None #삭제
self.p1 = (self.p1+1) % self.maxlen
return True
def Front(self) -> int:
return -1 if self.q[self.p1] is None else self.q[self.p1]
def Rear(self) -> int:
return -1 if self.q[self.p2 -1] is None else self.q[self.p2 -1]
def isEmpty(self) -> bool:
return self.p1 == self.p2 and self.q[self.p1] is None
def isFull(self) -> bool:
return self.p1 == self.p2 and self.q[self.p1] is not None
데크: 더블 엔디드 큐, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)
- 양쪽에서 삭제, 삽입 모두 가능
- 스택, 큐의 특징 모두 가짐
- 이중 연결 리스트로 구현시 좋은 성과 발휘