섬의 개수
- 리트코드 200번 문제 : https://leetcode.com/problems/number-of-islands/
- 1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을때, 섬의 개수를 계산하라.
- 입력 :
- grid =
[
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
- grid =
- 출력 : 1
풀이 1) DFS로 그래프 탐색
- 실행 속도 : 152 ms
- 하나의 육지 기준으로하여 DFS를 하여 동서남북으로 연결된 육지를 제거하는 방법을 사용
- 그 작업이 끝나면, 그 육지를 포함하는 섬의 모든 육지를 제거한 것이다.
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(row, col) -> int:
if row < 0 or row >= len(grid) \ # 행 예외 처리
or col < 0 or col >= len(grid[0]) \ # 열 예외 처리
or grid[row][col] != "1": # 물 예외 처리
return 0
grid[row][col] = "0" # 육지 제거
dfs(row, col + 1) # 동쪽 탐색
dfs(row, col - 1) # 서쪽 탐색
dfs(row + 1, col) # 남쪽 탐색
dfs(row - 1, col) # 북쪽 탐색
return 1 # 탐색 끝
return sum(dfs(row, col) for row in range(len(grid)) for col in range(len(grid[0])) if grid[row][col] == "1")
# 육지에 대하여 dfs 결과 합 = 섬의 개수
전화 번호 문자 조합
- 리트코드 17번 문제 : https://leetcode.com/problems/letter-combinations-of-a-phone-number/
- 2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라.
- 입력 : digits = "23"
- 출력 : ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
- 그림 :
풀이 1) DFS로 그래프 탐색
- 실행 속도 :
풀이 2) itertools 사용
- 실행 속도 : 28ms
- itertools의 product 사용
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits: # 빈 문자열 예외처리
return []
diaglos = {
"1" : "",
"2" : "abc",
"3" : "def",
"4" : "ghi",
"5" : "jkl",
"6" : "mno",
"7" : "pqrs",
"8" : "tuv",
"9" : "wxyz"
} # 전화번호 패드
iterators = [ diaglos[digit] for digit in digits ] # 번호에 맞게 문자 목록 생성
return [ ''.join(comb) for comb in itertools.product(*iterators) ] # 카테시안 곱순열
- 리트코드 46번 문제 : https://leetcode.com/problems/permutations/
- 서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라.
- 입력 : nums = [1,2,3]
- 출력 :
- [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
- [
풀이 1) DFS로 순열 생성
- 실행 속도 :
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
풀이 2) itertools 사용
- 실행 속도 : 36 ms
- itertools의 permutations 사용
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return [ list(elem) for elem in itertools.permutations(nums)] 조합
- 리트코드 77번 문제 : https://leetcode.com/problems/combinations/
- 전체 수 n을 입력받아 k개의 조합을 리턴하라.
- 입력 : n = 4, k = 2
- 출력 :
- [
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
- [
풀이 1) DFS로 조합 생성
- 실행 속도 :
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
풀이 2) itertools 사용
- 실행 속도 : 74ms
- itertools의 combinations를 사용
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
return [ list(elem) for elem in itertools.combinations(range(1, n + 1), k) ]
조합의 합
- 리트코드 39번 문제 : https://leetcode.com/problems/combination-sum/
- 숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라, 각 원소는 중복으로 나열 가능하다.
- 입력 :
- candidates = [2, 3, 6, 7]
- target = 7
- 출력 :
- [
[7],
[2,2,3]
]
- [
풀이 1) DFS로 중복 조합 그래프 탐색
- 실행 속도 :
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
풀이 2) itertools 사용
- 실행 속도 : 288 ms
- itertools의 combinations_with_replacement 사용
- target이 되기위한 최대 중복 조합의 길이까지 조합을 구한 후, 조합의 합이 target이 되는 경우를 모두 확인하여 추가하는 방법
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
min_num = min(candidates)
max_num = max(candidates)
start = math.ceil(target / max_num)
end = math.ceil(target / min_num)
result = []
for index in range(start, end + 1):
for comb in itertools.combinations_with_replacement(candidates, index):
if sum(comb) == target:
result.append(list(comb))
return result
부분 집합
- 리트코드 78번 문제 : https://leetcode.com/problems/subsets/submissions/
- 모든 부분 집합을 리턴하라.
- 입력 : nums= [1, 2, 3]
- 출력 :
- [
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
- [
풀이 1) DFS로 탐색
- 실행 속도 :
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
풀이 2) 단순 반복
- 실행 속도 : 32 ms
- 손으로 부분 집합을 구하듯이 구하는 구조.
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
output = [[]]
for num in nums:
output += [curr + [num] for curr in output]
return output
풀이 3) itertools 사용
- 실행 속도 : 32 ms
- itertools의 chain, combinations 사용
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
return list(map(list, itertools.chain.from_iterable(itertools.combinations(nums, r) for r in range(len(nums) + 1))))
Java, Python, JavaScript Lover