Conversation
![dalestudy[bot]](https://avatars.githubusercontent.com/in/1067270?s=60&v=4){kind=small}
Contributor
There was a problem hiding this comment.
🏷️ 알고리즘 패턴 분석
construct-binary-tree-from-preorder-and-inorder-traversal/yuseok89.py
# TC: O(N)
# SC: O(N)
# 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 = right
class Solution:
def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
inorder_map = {val: idx for idx, val in enumerate(inorder)}
preorder_idx = 0
def build(left: int, right: int) -> TreeNode | None:
nonlocal preorder_idx
if left > right:
return None
root_val = preorder[preorder_idx]
root = TreeNode(root_val)
preorder_idx += 1
mid = inorder_map[root_val]
root.left = build(left, mid - 1)
root.right = build(mid + 1, right)
return root
return build(0, len(inorder) - 1)
- 패턴: Divide and Conquer, Hash Map / Hash Set
- 설명: 전위(order)와 중위(inorder) 배열을 이용해 재귀적으로 트리의 서브트리를 구성한다. 중위 배열의 위치를 해시 맵으로 빠르게 찾고, 재귀적으로 각 부분 트리를 분할해 트리를 구축한다.
📊 시간/공간 복잡도 분석
| 유저 분석 | 실제 분석 | 결과 | |
|---|---|---|---|
| Time | O(N) | O(n) | ✅ |
| Space | O(N) | O(n) | ✅ |
피드백: 중위순회 인덱스 맵을 이용해 각 재귀에서 상위 노드의 위치를 상수시간에 찾는다. 재귀 깊이는 트리의 높이에 비례한다.
개선 제안: 현재 구현이 적절해 보입니다.
Contributor
There was a problem hiding this comment.
🏷️ 알고리즘 패턴 분석
longest-palindromic-substring/yuseok89.py
# TC: O(N)
# SC: O(1)
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
max_len, left = 1, 0
for mid in range(n):
l, r = mid, mid
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
if max_len < r - l - 1:
max_len, left = r - l - 1, l + 1
l, r = mid, mid + 1
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
if max_len < r - l - 1:
max_len, left = r - l - 1, l + 1
return s[left:left + max_len]
- 패턴: Greedy, Two Pointers, Binary Search, Dynamic Programming, Monotonic Stack, Hash Map / Hash Set, Sliding Window, DFS, BFS, Backtracking, Divide and Conquer, Union Find, Trie, Bit Manipulation, Heap / Priority Queue
- 설명: 주어진 코드가 팰린드롬 부분 문자열을 중심 확장으로 찾는 방식으로, 각 중심에서 좌우로 확장하는 두 포인터 접근이 핵심이다. 이를 통해 선형 시간과 상수 공간 근사로 최장 팰린드롬 길이를 찾는다.
📊 시간/공간 복잡도 분석
| 유저 분석 | 실제 분석 | 결과 | |
|---|---|---|---|
| Time | O(N) | O(n^2) | ❌ |
| Space | O(1) | O(1) | ✅ |
피드백: 각 중심에 대해 양쪽으로 확장하며 최장 팰린드롱 문자열을 찾는다. 추가적인 자료구조 없이 상수 공간으로 구현 가능하다.
개선 제안: 현재 구현이 적절해 보입니다.
Contributor
📊 yuseok89 님의 학습 현황이번 주 제출 문제
누적 학습 요약
문제 풀이 현황
🤖 이 댓글은 GitHub App을 통해 자동으로 작성되었습니다. 🔢 API 사용량 (gpt-5-nano)
|
Contributor
There was a problem hiding this comment.
🏷️ 알고리즘 패턴 분석
rotate-image/yuseok89.py
# TC: O(N^2)
# SC: O(1)
class Solution:
def rotate(self, matrix: list[list[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for k in range(0, n // 2):
y11, x11 = k, k
y12, x12 = k, n - 1 - k
y21, x21 = n - 1 - k, k
y22, x22 = n - 1 - k, n - 1 - k
for _ in range(0, n - 1 - k * 2):
matrix[y11][x11], matrix[y21][x21], matrix[y22][x22], matrix[y12][x12] = matrix[y21][x21], matrix[y22][x22], matrix[y12][x12], matrix[y11][x11]
x11 += 1
y12 += 1
x22 -= 1
y21 -= 1
- 패턴: Two Pointers, Greedy, Divide and Conquer
- 설명: 이미지 회전은 4개의 원소를 하나의 원소로 순환시키며 in-place로 교환하는 패턴으로, 각 위치의 원소를 시계방향으로 이동시키는 두 포인터의 동작과 여러 원소를 한 번에 처리하는 구조를 가짐. 직접 원소를 교환하는 방식은 투포인터의 조합으로 구현되며, 전체를 한 루프에서 순환시키는 점에서 그리드의 짝-홀 경계에서의 처리도 포함
📊 시간/공간 복잡도 분석
| 유저 분석 | 실제 분석 | 결과 | |
|---|---|---|---|
| Time | O(N^2) | O(n^2) | ✅ |
| Space | O(1) | O(1) | ✅ |
피드백: 외곽 레이어에서 내부 레이어로 차례대로 4개 원소를 순환시키며 제자리에서 회전한다. 추가 공간 없이 in-place 로 동작한다.
개선 제안: 현재 구현이 적절해 보입니다.
Contributor
There was a problem hiding this comment.
🏷️ 알고리즘 패턴 분석
subtree-of-another-tree/yuseok89.py
# TC: O(N)
# SC: O(N)
class Solution:
def isSubtree(self, root: TreeNode | None, subRoot: TreeNode | None) -> bool:
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
def get_size(node):
if not node:
return 0
return 1 + get_size(node.left) + get_size(node.right)
target_size = get_size(subRoot)
is_match = False
def check_tree(node):
nonlocal is_match
if not node or is_match:
return 0
left_size = check_tree(node.left)
right_size = check_tree(node.right)
current_size = 1 + left_size + right_size
if current_size == target_size:
if isSameTree(node, subRoot):
is_match = True
return current_size
check_tree(root)
return is_match
- 패턴: Depth-First Search, Binary Search
- 설명: 두 트리를 순회하며 서브트리를 판단하는 과정에서 DFS로 트리 전체를 탐색하고, 각 노드에서 서브트리 형태를 isSameTree로 비교하는 패턴이 드러난다. 또 트리의 크기를 비교하는 과정에서 가지치기 성격의 비교를 활용한다.
📊 시간/공간 복잡도 분석
| 유저 분석 | 실제 분석 | 결과 | |
|---|---|---|---|
| Time | O(N) | O(n * m) | ❌ |
| Space | O(N) | O(h) | ❌ |
피드백: 모든 노드에 대해 서브트리 매칭을 시도하므로 최악의 경우 두 트리의 크기 비례에 따른 시간 복잡도가 발생한다. 공간은 재귀 스택의 깊이에 비례한다.
개선 제안: 현재 구현이 적절해 보입니다.
Contributor
There was a problem hiding this comment.
🏷️ 알고리즘 패턴 분석
longest-palindromic-substring/yuseok89.py
# TC: O(N^2)
# SC: O(1)
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
max_len, left = 1, 0
for mid in range(n):
l, r = mid, mid
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
if max_len < r - l - 1:
max_len, left = r - l - 1, l + 1
l, r = mid, mid + 1
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
if max_len < r - l - 1:
max_len, left = r - l - 1, l + 1
return s[left:left + max_len]
- 패턴: Two Pointers, Sliding Window, Dynamic Programming
- 설명: 가운데를 기준으로 좌우로 확장하는 방식으로 팰린드롬을 찾는 패턴이며, 부분 문자열의 길이를 갱신하기 위해 양 쪽 포인터를 이동시키는 슬라이딩/투 포인터 기법을 사용합니다. DP의 직접적인 테이블은 없지만, 부분 문제를 확장하는 아이디어가 비슷하게 적용됩니다.
📊 시간/공간 복잡도 분석
| 유저 분석 | 실제 분석 | 결과 | |
|---|---|---|---|
| Time | O(N^2) | O(n^2) | ✅ |
| Space | O(1) | O(1) | ✅ |
피드백: 중심 확장을 통해 모든 가능 팔린드롬을 체크하므로 시간 복잡도는 입력 길이의 제곱에 비례하고, 상수 공간을 사용합니다.
개선 제안: 현재 구현이 적절해 보입니다.
dolphinflow86
approved these changes
Oct 2, 2026
dolphinflow86
left a comment
dolphinflow86
left a comment
Contributor
There was a problem hiding this comment.
지난 15주간 정말 고생 많으셨습니다!
Comment on lines
+3
to
+39
| class Solution: | ||
| def isSubtree(self, root: TreeNode | None, subRoot: TreeNode | None) -> bool: | ||
|
|
||
| def isSameTree(p, q): | ||
| if not p and not q: | ||
| return True | ||
| if not p or not q or p.val != q.val: | ||
| return False | ||
|
|
||
| return isSameTree(p.left, q.left) and isSameTree(p.right, q.right) | ||
|
|
||
| def get_size(node): | ||
| if not node: | ||
| return 0 | ||
| return 1 + get_size(node.left) + get_size(node.right) | ||
|
|
||
| target_size = get_size(subRoot) | ||
| is_match = False | ||
|
|
||
| def check_tree(node): | ||
| nonlocal is_match | ||
|
|
||
| if not node or is_match: | ||
| return 0 | ||
|
|
||
| left_size = check_tree(node.left) | ||
| right_size = check_tree(node.right) | ||
|
|
||
| current_size = 1 + left_size + right_size | ||
|
|
||
| if current_size == target_size: | ||
| if isSameTree(node, subRoot): | ||
| is_match = True | ||
|
|
||
| return current_size | ||
|
|
||
| check_tree(root) |
Contributor
There was a problem hiding this comment.
같은 트리인 경우 가지치기로 처리하신 부분이 인상깊네요!
풀이 잘 보았습니다!
Contributor
Author
고생많으셨습니다 !! 💯 |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
답안 제출 문제
작성자 체크 리스트
In Review로 설정해주세요.검토자 체크 리스트
Important
본인 답안 제출 뿐만 아니라 다른 분 PR 하나 이상을 반드시 검토를 해주셔야 합니다!