99클럽 코테 스터디
오늘은 스터디에 늦게 들어와서 챌린저 문제만 풀어 보았는데, 발표자가 빠르게 꽉 차서 처음으로 발표하지 않은 날이었다. 문제 자체는 쉬운 편이었다. 미들러 문제가 어려웠다고 하니 풀어봐야겠다.
-> 수정 : 발표 시간 동안 비기너, 미들러도 풀고 추가했다.
-> 미들러 문제를 자바로도 풀어보았다.
비기너 문제 Maximum Depth of Binary Tree : https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
미들러 문제 Reverse Odd Levels of Binary Tree : https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/
챌린저 문제 네트워크 : https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=python3
출처 : 프로그래머스, leetcode
비기너 문제 : Maximum Depth of Binary Tree
풀이 접근
정석적인 dfs 문제이다. 방문하는 노드의 depth가 지금까지 방문한 노드 중 최대이면 그걸로 갱신하는 식으로도 가능하다(global 선언으로 최대값을 수정하는 식으로). 하지만 여기선 좀 더 재귀적으로 풀어보았다.
코드(Python3, Accepted, 33ms(상위 3.29%), 17.48MB(상위 6.92%))
아래 미들러 코드에서도 말하겠지만, 상위 몇%인지는 약간 허수가 있다. 나는 같은 코드도 몇 번 제출해서 제일 잘 나온 값으로 썼다(그게 기분좋으니까).
dfs에 인자로 depth를 넣지 않고도 재귀적으로 하는 방법도 있다. return하는 값을 max(dfs(node.right),dfs(node.left)) + 1 대충 이런식으로 해버리면 되기 때문.
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
def dfs(node, depth):
if not node:
return depth
return max(dfs(node.left, depth + 1), dfs(node.right, depth + 1))
return dfs(root, 0)미들러 문제 : Reverse Odd Levels of Binary Tree
풀이 접근
bfs로 푸는게 dfs보다 좋다. 같은 depth에 있는 노드끼리 값을 서로 바꿔야 되기 때문에, dfs로 하면 값을 따로 어디다 저장해 뒀다가 나중에 바꿀 때도 귀찮고 여러모로 좋지 않다.
bfs에 원소로 한 level(같은 depth의 모든 노드)을 한번에 list의 형태로 입력으로 넣고(편하게 하기 위해 level이 몇인지도 같이 넣어주고), level이 홀수면 있는 노드의 값을 앞뒤로 뒤집어 준다.
앞뒤로 뒤집을 때는 값을 리스트로 만들고 reverse해버리거나, idx를 이용해서 바꿀 수도 있지만, 뒤에 코드에 쓸 것처럼 바꿔주면 더 효율이 좋다.
코드(Python3, Accepted, 617ms(상위 0.35%), 20.84MB(상위 0.35%))
상위 0.35%라는 것은 사실 약간의 허수가 있을 수도 있다. leetcode는 같은 코드를 반복해서 제출하면 제출할 때마다 꽤 큰 범위에서 결과가 변하기 때문이다. (아래 코드를 다시 제출하면 상위 30%로 뜰 때도 있다) 하지만 아무튼 결과가 아주 훌륭해서 맘에 들었다.
bfs에 넣는 arr은 node들의 list이다(node의 value들의 리스트가 아님에 유의한다. value를 입력값으로 넣으면 구조상 그 자식 노드를 찾을 수 없다).
level이 홀수이면, 해당 level에 노드가 몇 갠지 세고(2^level이다), a,b = b,a 형태의 코드로 앞에서부터 i번째 노드의 값과 뒤에서부터 i번째 노드의 값을 서로 바꿔준다. i의 range가 n이 아니라 n//2임에 유의한다.
이렇게 하면 주석처리해둔 방식으로 node의 value를 list로 만드는 것보다 효율이 좋다.
문제에서 주어진 트리가 완전 이진 트리라는 조건이 있으므로, 아무 원소나 뽑아서 아무 자식이라도 없으면 bfs를 즉시 종료해도 된다.
# 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 reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def bfs(arr, level):
if level % 2:
# values = []
# for node in arr:
# values.append(node.val)
# for i in range(len(arr)):
# arr[i].val = values[len(arr) - i - 1]
n = 2 ** level
for i in range(n // 2):
arr[i].val, arr[n - i - 1].val = arr[n - i - 1].val, arr[i].val
next_level = []
if not arr[0].left:
return
for node in arr:
next_level.append(node.left)
next_level.append(node.right)
bfs(next_level, level + 1)
return
bfs([root],0)
return root
코드(java, Accepted, 3ms(상위 50%), 48.8MB(상위 60%))
파이썬스러운 코드를 자바로 거의 번역만 해서 옮겼더니 굉장히 불편한 부분이 많았어서 그런지, 결과가 매우 좋진 않다. 그래도 1ms를 다투는 영역이라 큰 차이는 아니라고 생각된다.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void bfs(List<TreeNode> arr, int level) {
if (level % 2 == 1) {
int n = arr.size();
for (int i = 0; i < n/2; i++) {
int temp = arr.get(i).val;
arr.get(i).val = arr.get(n - i - 1).val;
arr.get(n - i - 1).val = temp;
}
}
if (arr.get(0).left==null) {
return;
}
List<TreeNode> nextLevel = new ArrayList<>();
for (TreeNode node:arr) {
nextLevel.add(node.left);
nextLevel.add(node.right);
}
bfs(nextLevel, level + 1);
return;
}
public TreeNode reverseOddLevels(TreeNode root) {
List<TreeNode> rootLevel = new ArrayList<>();
rootLevel.add(root);
bfs(rootLevel, 0);
return root;
}
}챌린저 문제 : 네트워크
풀이 접근
dfs로 아주 쉽게 풀리는 문제이다. 한 네트워크에 속한 모든 노드를 dfs로 훑는다. 훑을 때마다 방문처리한다. 방문처리되지 않은 노드를 발견하면 또 dfs한다(dfs를 한 번 할 때마다 answer에 1씩 더해준다). 끝!
코드(Python3, 통과, 최대 0.49ms, 10.3MB)
모든 노드에 대해서, visited[i]가 False이면(즉, 이미 탐색한 네트워크에 속하지 않은 노드를 발견하면), 새로운 네트워크를 구성하므로 answer에 1을 더해주고 그 노드에서 dfs를 돌려서 연결된 모든 노드를 방문하여 방문처리해준다.
def solution(n, computers):
visited = [False] * n
answer = 0
def dfs(k):
visited[k] = True
for i in range(n):
if computers[k][i] and not visited[i]:
dfs(i)
return
for i in range(n):
if not visited[i]:
answer += 1
dfs(i)
return answer