본문 바로가기

Medium174

[leetcode][1267] Count Servers that Communicate 문제 : https://leetcode.com/problems/count-servers-that-communicate/ m x n grid가 주어질 때, 1은 서버, 0은 빈 셸이라고 하자. 같은 행이나 열에 서버가 있는 경우 그 서버는 다른 서버와 통신할 수 있다고 한다. 다른 서버와 통신할 수 있는 서버의 총 개수를 구하는 문제이다. 예를 들어서 확인해보자. 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 grid가 위와같이 주워졌다고 하자. 1 1 0 0 1 1 1 0 1 1 2 0 1 1 2 1 열 subsum은 위와 같이 채워진다. 위에서 아래로 채운다고 생각하면 된다. 1 2 2 2 0 0 1 1 0 0 1 1 0 0 0 1 행 subsum은 위와 같이 채워진다. 왼쪽에서 오른쪽으로 .. 2020. 1. 26.
[leetcode][1288] Remove Covered Intervals 문제 : https://leetcode.com/problems/remove-covered-intervals/ 간격배열이 주어질 때, [a,b), [c,d)가 있는 경우 c 2020. 1. 25.
[leetcode][334] Increasing Triplet Subsequence 문제 : https://leetcode.com/problems/increasing-triplet-subsequence/ nums 배열이 주어진다. 인덱스 i, j, k (0 one: #2 two = three if three < one: #3 one = three #1 탐색 중인 수(three)가 two보다 큰 경우, one < two < three 인 부분배열이 있다는 뜻이므로 정답이 가능하다. 식은 (one 2020. 1. 2.
[leetcode][46] Permutations 문제 : https://leetcode.com/problems/permutations/ 고유한 정수 모음의 가능한 모든 순열을 구해서 반환하는 문제. 백트래킹으로도 풀 수 있지만 이번에는 반복문으로 풀어보았다. [1, 2, 3] 이 입력으로 주어질때 [] -> [1] -> [1,2] [2,1] -> [1,2,3] [1,3,2] [3,1,2] [2,1,3] [2,3,1] [3,2,1] 위와 같이 배열을 만들어나간다. [1,2] [2,1] -> [1,2,3] [1,3,2] [3,1,2] [2,1,3] [2,3,1] [3,2,1] 을 만드는 과정을 자세히 보면 [1,2] -> [1,2,3] [1,3,2] [3,1,2] / [2,1] -> [2,1,3] [2,3,1] [3,2,1] 이렇게 두가지 리스트 결과를 .. 2019. 12. 23.
[leetcode][979] Distribute Coins in Binary Tree 문제 : https://leetcode.com/problems/distribute-coins-in-binary-tree/ 루트에서 자식노드로 내려가면서 현재 탐색 중인 노드를 루트로 하는 서브트리의 모든 노드들이 코인을 하나씩 가지고 남는 코인개수를 반환한다. 이 함수를 getCoins라 한다면 수도코드는 다음과 같다. getCoins(root) = getCoins(root.left) + getCoins(root.right) + root.val - 1 root 노드의 val(가지고 있는 코인 개수)와 자식 노드들에게서 남는 코인개수를 가져와서 더해준다. 그리고 1을 빼준다. 이유는 root 노드도 1개의 코인을 가져야하기 때문에 root 몫의 코인 개수(1개)는 제외시켜야 하기 때문이다. 남는 코인개수를.. 2019. 12. 17.
[leetcode][539] Minimum Time Difference 문제 : https://leetcode.com/problems/minimum-time-difference/ 문자열들을 탐색하면서 ':' 기준으로 시, 분을 나눈다. 시 * 60 + 분 (분으로 변환. 정수형)을 리스트에 저장한다. 리스트를 오름차순 정렬한다. 가장 작은 수에 + 24*60 을 리스트의 가장뒤에 추가한다. 리스트를 앞에서부터 탐색하면서 인접한 분들의 차이를 구하고 이들 중 최소값이 정답이 된다. 시간복잡도는 O(NlogN) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1266.%20Minimum%20Time%20Visiting%20All%20Points.py 2019. 12. 8.

티스토리툴바