[PYTHON] 프로그래머스 고득점 kit
정렬
k 번째 큰 수
https://school.programmers.co.kr/learn/courses/30/lessons/42748
쉬운문제
기억할 포인트
- 파이썬에서는 substring 사용할때 슬라이싱 array[i:j]
-> i 인덱스부터 j-1까지
문제에서는 인덱스+1 되어 있어서 i-1 : j
def solution(array, commands):
answer = []
for i, j, k in commands:
substring = array[i-1:j]
substring.sort()
answer.append(substring[k-1])
return answer
가장 큰 수
https://school.programmers.co.kr/learn/courses/30/lessons/42746
쉬운 정렬 문제
기억할 포인트
sort에서 key를 사용할때 자바처럼 매개변수 2개가 안들어간다
사용하려면
- from functools import cmp_to_key
from functools import cmp_to_key
def solution(numbers):
def comparator(x, y):
if x + y > y + x:
return -1
elif x + y < y + x:
return 1
else:
return 0
numbers = list(map(str, numbers))
numbers.sort(key = cmp_to_key(comparator))
answer = ''.join(numbers)
return '0' if answer[0] == '0' else answer
마지막에 0000 인 경우를 위해 예외처리해야하는 함정이 있었다
H-index
https://school.programmers.co.kr/learn/courses/30/lessons/42747
생각해내기가 어렵다.,, 시험시간에 이런 생각을 할 수 있을까?
def solution(citations):
citations.sort(reverse=True)
h = 0
for i, citation in enumerate(citations):
if citation >= i+1:
h = i+1
else:
break
return h
DFS / BFS
타겟 넘버
https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3
기억할 포인트
from functools import lru_cache
메모이제이션 캐싱 풀이
dfs 풀이
def solution(numbers, target):
answer = 0
def dfs(index, current_sum):
nonlocal answer
if len(numbers) == index:
if current_sum == target:
answer += 1
return
dfs(index+1, current_sum + numbers[index])
dfs(index+1, current_sum - numbers[index])
dfs(0,0)
return answer
count를 반환하는 dfs 풀이
def solution(numbers, target):
def dfs(index, currnet_sum):
if index == len(numbers):
if currnet_sum == target:
return 1
return 0
count = 0
count += dfs(index+1, currnet_sum + numbers[index])
count += dfs(index+1, currnet_sum - numbers[index])
return count
return dfs(0, 0)
bfs 풀이
from collections import deque
def solution(numbers, target):
answer = 0
q = deque([(0,0)])
while q:
index, current_sum = q.popleft()
if index == len(numbers):
if current_sum == target:
answer += 1
continue
q.append((index + 1, current_sum + numbers[index]))
q.append((index + 1, current_sum - numbers[index]))
return answer
lru cache 적용 풀이
대신 캐싱을 적용하기 때문에 중간 로직에 answer+=1 하는 로직은 사용하면 안되고
dfs return 값으로 계산하는 방식을 사용해야한다
from functools import lru_cache
def solution(numbers, target):
@lru_cache(maxsize = None)
def dfs(index, current_sum):
if len(numbers) == index:
if target == current_sum:
return 1
return 0
count = 0
count += dfs(index + 1, current_sum + numbers[index])
count += dfs(index + 1, current_sum - numbers[index])
return count
return dfs(0, 0)
네트워크
https://school.programmers.co.kr/learn/courses/30/lessons/43162
기본적인 섬찾기 문제
visited를 배열로 많이 하는데 여기서는 set으로 해봤다
from collections import defaultdict
def solution(n, computers):
answer = 0
dict = defaultdict(list)
for i, computer in enumerate(computers):
for j, c in enumerate(computer):
if i != j and c == 1:
dict[i].append(j)
visited = set()
def dfs(index):
nonlocal answer
visited.add(index)
for next in dict[index]:
if next not in visited:
dfs(next)
for i in range(n):
if i not in visited:
answer += 1
dfs(i)
return answer
게임맵 최단거리
https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=python3
오랜만에 파이썬으로 하니 굉장히 쉽다
기본적인 BFS
from collections import deque
def solution(maps):
answer = 0
n, m = len(maps), len(maps[0])
q = deque([(0, 0, 1)])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
visited = [[False]*m for _ in range (n)]
visited[0][0] = True
while q:
x, y, move = q.popleft()
if x == n-1 and y == m-1:
return move
for dx, dy in directions:
xx, yy = x + dx, y + dy
if 0 <= xx < n and 0 <= yy < m and maps[xx][yy] == 1 and visited[xx][yy] == False:
visited[xx][yy] = True
q.append((xx, yy, move+1))
return -1
단어 변환
BFS
기억할 포인트
- zip
처음 풀이 - 오답
can transform 메서드가 틀렸다
(위치를 생각하지 않아서)
from collections import deque
def solution(begin, target, words):
# a에서 b로
def can_transform(a, b):
return len(set(a) - set(b)) == 1
if target not in words:
return 0
q = deque([(begin, 0)])
visited = set([begin])
while q:
current, count = q.popleft()
if current == target:
return count
for word in words:
if word not in visited and can_transform(current, word):
visited.add(word)
q.append((word, count + 1))
return 0
수정
zip을 사용했는데 그냥 index로 계산해도 된다
from collections import deque
def solution(begin, target, words):
# a에서 b로
def can_transform(a, b):
diff_count = 0
for c1, c2 in zip(a, b):
if c1 != c2:
diff_count += 1
return diff_count == 1
if target not in words:
return 0
q = deque([(begin, 0)])
visited = set([begin])
while q:
current, count = q.popleft()
if current == target:
return count
for word in words:
if word not in visited and can_transform(current, word):
visited.add(word)
q.append((word, count + 1))
return 0
zip을 살펴보면 리스트 두개 OR 문자열 두개를 나란히 묶어주는 메서드
둘의 길이가 다르면 짧은 쪽에 맞춰진다
응용해서 파이썬식 좀더 간결하게
def can_transform(a, b):
return sum(c1 != c2 for c1, c2 in zip(a, b)) == 1
이렇게 사용할 수 있다.
시험시간에 기억 안나면 그냥 인덱스로 빨리 풀자
여행경로
어렵다
핵심 아이디어는 막다른 길까지 도달해야한다는 점이다
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]
ticket일때
icn -> jfk
재귀
current jfk
jfk -> hnd
재귀
current hnd
hnd -> iad
재귀
current iad
여기서 딕셔너리가 비어있기 때문에 while문으로 들어가지 않는다
그러면 current인 aid를 answer에 append
탈출
hnd를 append
jfk append
icn append
리스트를 뒤집으면 경로가 나온다
import heapq
from collections import defaultdict
def solution(tickets):
dict = defaultdict(list)
for f, t in tickets:
heapq.heappush(dict[f], t)
answer = []
def dfs(current):
while dict[current]:
next = heapq.heappop(dict[current])
dfs(next)
answer.append(current)
dfs("ICN")
return answer[::-1]