Coding Test103 [LeetCode] 22. Generate Parentheses [JAVA(자바)] 문제 👉 https://leetcode.com/problems/generate-parentheses/ 1. 문제 (괄호 생성) n 쌍의 괄호의 모든 조합을 생성한다. Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] 2. 풀이 백트래킹을 이용한 풀이 backtracking == recursion + termination check termination check : ( 와 ) 의 개수가 n 일 때 종료 recurse : ( 의 개수가 n 보다 작을 때 ( 추가 ) 의 개수가 ( 의 개수 보다 작을 때 ) 추가 3. 코드 백트래킹을 이용한 풀이 class Solution { // numClosed > numOpen -> invalid .. 2021. 11. 23. [LeetCode] 771. Jewels and Stones [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (보석과 돌) 돌에 보석이 몇개 있는지 구해라. (대소문자 구분) 2. 풀이 해시를 이용한 풀이 Counter를 이용한 풀이 파이썬 스타일을 이용한 풀이 3. 코드 해시를 이용한 풀이 from collections import defaultdict class Solution: def numJewelsInStones(self, jewels: str, stones: str) -> int: ret, dic = 0, defaultdict(int) for s in stones: dic[s] += 1 for j in jewels: ret += dic[j] return ret Counter를 이용한 풀이 from collecti.. 2021. 11. 23. [LeetCode] 739 Daily Temperatures [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (일일 온도) 매일의 화씨 온도 리스트 T를 입력받아, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야하는지를 출력하라. 2. 풀이 스택을 이용한 풀이 스택에 인덱스를 넣기 전에 해당 인덱스의 온도 값이 추가되는 온도와 비교한다 3. 코드 스택을 이용한 풀이 class Solution: def dailyTemperatures(self, T: List[int]) -> List[int]: st, ret = [], [0] * len(T) for idx, val in enumerate(T): while st and T[st[-1]] < val: last = st.pop() ret[last] = idx - last st.app.. 2021. 11. 23. [LeetCode] 347. Top K Frequent Elements [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (상위 K 빈도 요소) k번 이상 등장하는 요소를 추출하라. 2. 풀이 해시와 Counter를 이용한 풀이 zip()와 Counter를 이용한 풀이 3. 코드 해시와 Counter를 이용한 풀이 from collections import Counter class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: ret = [] cnt = Counter(nums).most_common(k) for i in range(k): ret.append(cnt[i][0]) return ret zip()와 Counter를 이용한 풀이 from colle.. 2021. 11. 23. [LeetCode] 316. Remove Duplicate Letters [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (중복 문자 제거) 중복된 문자를 제외하고 사전식 순서 중 가장 작게 만들어라. Example 1: Input: s = "bcabc" Output: "abc" Example 2: Input: s = "cbacdcbc" Output: "acdb" 2. 풀이 스택의 개념을 이용한 풀이 (list를 stack처럼 활용하는 문제) 사전에서 가장 앞에 나오게 중복된 문자를 제거하는 문제이다. 문자열의 문자를 미리 카운팅한 후 스택에 다음과 같은 조건에 맞춰 문자를 추가한다. 추가하는 문자가 스택에 존재하지 않을 경우 스택의 마지막 문자가 추가하는 문자 보다 사전 순위가 크고 카운팅 수가 0 보다 클 때 스택의 문자를 계속해서.. 2021. 11. 23. [LeetCode] 20. Valid Parentheses [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (유효한 괄호) 괄호로 된 입력값이 올바른지 판별하라. 2. 풀이 스택을 이용한 풀이 3. 코드 (Python) 스택을 이용한 풀이 class Solution: def isValid(self, s: str) -> bool: dic = { ')' : '(', '}' : '{', ']' : '[' } stack = [] for c in s: if c not in dic: stack.append(c) elif not stack or stack.pop() != dic[c]: return False return not stack 결과 : 방.. 2021. 11. 23. [LeetCode] 3. Longest Substring Without Repeating Characters [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (중복 문자 없는 가장 긴 부분 문자열) 중복 문자가 없는 가장 긴 부분 문자열의 길이를 출력하라. 2. 풀이 해시와 투 포인터를 이용한 풀이 부분 문자열의 처음과 끝에 포인터를 위치 중복이 없으면 끝을 오른쪽으로 이동 중복이 있을 경우 처음을 오른쪽으로 이동 3. 코드 해시와 투 포인터를 이용한 풀이 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: ret, start = 0, 0 used = {} for idx, char in enumerate(s): if char in used and start 2021. 11. 23. [LeetCode] 328. Odd Even Linked List [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (홀짝 연결리스트) 연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성해라. 공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이하라. 2. 풀이 반복문을 이용한 풀이 3. 코드 반복문을 이용한 풀이 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def oddEvenList(self, head: ListNode) -> ListNode: #종료 조건 if not head: return None odd.. 2021. 11. 23. [LeetCode] 234. Palindrome Linked List [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (팰린드롬 연결리스트) 연결리스트가 팰린드롬인지 확인하라. 2. 풀이 deque를 이용한 풀이 런너 기법을 이용한 풀이 3. 코드 deque를 이용한 풀이 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next from collections import deque class Solution: def isPalindrome(self, head: ListNode) -> bool: # 종료 조건 if not head: return True que.. 2021. 11. 23. 이전 1 ··· 4 5 6 7 8 9 10 ··· 12 다음
