unique element로 구성된 nums 배열이 주어졌을 때,가능한 모든 subsets(부분집합)을 리턴하는 문제다. 접근 - 백트래킹모든 부분 집합을 구하는 문제 -> 완전 탐색반복문 vs 재귀 -> 반복문으로 모든 경우를 탐색하기 어려우므로 재귀(DFS)를 이용한 탐색,nums의 각 원소를 포함할지 안 할지 선택 필요 -> 백트래킹백트래킹은 모든 가능한 경우를 탐색하면서, 불가능한 경로는 빠르게 되돌아가(백트랙) 탐색을 줄이는 기법이다.일반적으로 재귀(Recursion)을 이용한다. 부분집합 문제에서는 nums[i]를 선택할지 안 할지 결정하는 2가지 선택이 계속해서 분기되기에 백트래킹에 적합하다. 풀이: 백트래킹class Solution: def subsets(self, nums: L..
⚙️ Problem Solving/Algorithm - Python
문제 요약스톤의 무게가 담긴 stones[i] 배열이 있을 때1. 가장 무거운 두 개의 스톤을 선택,2. 같으면 둘다 제거, 다르면 큰 돌이 (큰 값 - 작은 값)으로 변함3. 최대 한 개의 돌이 남아있을 때까지 반복4. 남은 돌의 무게 반환 (없으면 0) 최적 풀이 : max heap 이용max heap을 이용하면 항상 가장 큰 무게의 두 돌이 항상 배열의 맨 앞에 있는 구조를 유지할 수 있다.class Solution: def lastStoneWeight(self, stones: List[int]) -> int: stones = [-s for s in stones] heapq.heapify(stones) while len(stones) > 1:..
정수 k와 초기 스트림 nums가 주어질 때,새로운 값이 추가될 때마다 K번째로 큰 값을 반환하는 클래스를 구현하는 문제다.constructor는 클래스를 처음 생성할 때 실행되는 함수.Python에서는 __init__()이 constructor(생성자) 역할을 한다. 풀이1: Min-Heap 이용이 문제의 가장 효율적인 풀이는 Min-Heap을 이용하는 것이다. import heapqclass KthLargest: def __init__(self, k: int, nums: List[int]): self.minHeap, self.k = nums, k heapq.heapify(self.minHeap) while len(self.minHeap) > k: ..
BST의 root와 k가 주어졌을 때,트리에서 k번째로 작은 값을 리턴하는 문제이다.(1-indexed: 1부터 시작하는 인덱스 기준) 풀이 1: 브루트포스(DFS) - O(n log n)가장 간단한 풀이로는 dfs를 통해 완전 탐색을 하고, 정렬하여 k번째로 작은 값을 리턴할 수 있다. # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def kthSmallest(self, root: Opt..
링크드리스트에 사이클이 있는지 없는지 판단하는 문제이다.set을 이용하여 간단히 풀 수도 있지만, 플로이드의 순환 찾기 알고리즘, 플로이드의 토끼와 거북이 알고리즘으로도 풀 수 있는 재밌는 문제였다! 풀이1. set 이용# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: seen = set() cur = head while cur: ..
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.Kok..
You are given an m x n integer matrix matrix with the following two properties:Each row is sorted in non-decreasing order.The first integer of each row is greater than the last integer of the previous row.Given an integer target, return true if target is in matrix or false otherwise.You must write a solution in O(log(m * n)) time complexity.1. 각 행은 오름차순으로 정렬되어 있음2. 한 행의 첫 번째 값은 이전 행의 마지막 값보다 큼O(..
You are given the heads of two sorted linked lists list1 and list2.Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.Return the head of the merged linked list.두 개의 링크드리스트를 하나의 sorted linked list로 만들기! 풀이1: Recursion (재귀)# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# se..
Given a string s, find the length of the longest substring without repeating characters.반복되는 문자 없이 가장 긴 substring의 길이를 찾는 문제!substring은 시작과 끝이 정의된 유동적인 범위이므로,상황에 따라 범위(윈도우)를 늘리거나 줄이는 슬라이딩 윈도우 풀이를 떠올릴 수 있다. 풀이 : Sliding Windowclass Solution: def lengthOfLongestSubstring(self, s: str) -> int: charSet = set() l = 0 res = 0 for r in range(len(s)): while s[..
Given head, the head of a linked list, determine if the linked list has a cycle in it.There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.Return true if there is a cycle i..
