본문 바로가기

Medium174

[leetcode][260] Single Number III 문제 : https://leetcode.com/problems/single-number-iii/ 2개의 요소는 단 하나만 존재하고 이 외의 요소들은 두 개씩 있는 nums 배열이 주어진다. 하나만 존재하는 2개 요소를 찾아라. (요소의 순서는 상관없다. 선형 시간복잡도로 구현하라.) nums 배열을 탐색하면서 모든 요소들의 XOR 연산 결과를 sum 변수에 저장한다. XOR 연산은 홀수번 나온 비트는 1, 짝수번(0포함) 나온 비트는 0으로 세팅된다. 즉, XOR연산 결과는 1개만 존재하는 수의 XOR 결과와 같다. (나머지 수들은 2번 XOR 연산되므로 A XOR A = 0. 이 되므로 무시해도 된다.) 하나만 존재하는 요소를 각각 A, B라고 했을 때, A는 B와 같지 않으므로 A XOR B = 0 .. 2020. 7. 24.
[leetcode][430] Flatten a Multilevel Doubly Linked List 문제 : https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/ doubly linked list 가 주어진다. 하나의 노드는 next, previous, child 포인터를 가지고 있다. 이를 prev, next만을 가진 linked list로 바꿔라. child와 next 포인터를 가지고 있다면 child 노드를 next 노드로 잇고 child 노드와 연결된 모든 노드들이 linked list로 만들어졌을 때 그 뒤에 next노드를 다시 이어나간다. dfs로 head 노드에서 child노드가 있다면 child 노드를 잇고 다음 next노드를 잇는 식으로 재귀함수를 만들어서 푼다. 이를 위해 최근 탐색했던 노드 포인터 before와.. 2020. 7. 10.
[leetcode][15] 3Sum 문제 : https://leetcode.com/problems/3sum/ nums 배열이 주어졌을 때 3개의 수 a,b,c를 nums 배열에서 고를 때 a, b, c의 합이 0이 되는 조합의 수를 구해라. https://withhamit.tistory.com/408 [BOJ][2143] 두 배열의 합 문제 : https://www.acmicpc.net/problem/2143 투 포인터(Two-Pointer)를 이용하여 풀었습니다. 배열 당 모든 부배열을 만드는 시간 복잡도는 O(n2)인데 n의 크기가 (1 2020. 7. 8.
[leetcode][63] Unique Paths II 문제 : https://leetcode.com/problems/unique-paths-ii/description/ 로봇이 M x N 그리드의 왼쪽 위 코너에 있다. 로봇은 아래나 오른쪽으로만 움직일 수 있다. 그리드에는 장애물들이 있다. 장애물이 있는 경우 해당 칸으로는 갈 수 없다. 로봇이 그리드의 오른쪽 아래 코너로 가려고 할때 경우의 수는 총 몇 가지인가. 2차원 배열을 만든다. d[i][j] = (i, j)에서 도착점까지 갈 수 있는 경우의 수. 위 배열을 채우면 되는데, 로봇이 이동할 수 있는 방향은 아래, 오른쪽이고 장애물은 이동할 수 없다는 것으로 점화식을 세울 수 있다. d[i][j] = d[i+1][j] + d[i][j+1] ((i, j)가 장애물이 아닌 경우) d[i][j] = 0 ((.. 2020. 6. 30.
[leetcode][96] Unique Binary Search Trees 문제 : https://leetcode.com/problems/unique-binary-search-trees/1..n 의 수로 만들어질 수 있는 BST의 수를 구하라.예시에서 보여주고 있는 n = 3일 때의 만들 수 있는 BST들을 노드 입력 순으로 나열해보자. 1. 1 2 3 2. 1 3 2 3. 2 1 3 (2 3 1) 4. 3 2 1 5. 3 1 2 3번을 보면 [2, 1, 3] 과 [2, 3, 1]의 BST 결과가 같다는 것을 알 수 있다.BST는 루트노드보다 작은 노드들은 루트노드의 왼쪽 서브트리로 가고, 루트노드보다 큰 노드들은 루트노드의 오른쪽 서브트리로 간다.그러므로 2 다음에 1이나올지 3이 나올지는 중요하지 않다는 것이다. 1은 반드시 2의 왼쪽 서브트리로 갈 것이고, 3은 반드시 2.. 2020. 6. 24.
[leetcode][275] H-Index II 문제 : https://leetcode.com/problems/h-index-ii/오름차순으로 정렬된 양의 정수 배열이 주어진다고 하자. (let, 배열 크기 = N)이 배열은 논문들이고, 각 배열 값은 i번째 논문이 몇 개의 논문을 인용했는지를 나타낸다. 즉, arr[2] = 3이라면 2번째 논문은 3개의 논문을 인용하여 작성되었음을 의미한다.N개의 논문중 h개의 논문이 h개 이상의 논문을 인용하고 N-h개는 h개 이하를 인용하는 경우 h-인덱스라고 한다.배열의 가능한 h-인덱스 값 중 최대값을 구해라.이분 탐색으로 풀어보자. 어쨌든 h의 범위는 논문의 개수이다.l, r 은 배열의 시작인덱스, 종료인덱스로 잡자.m = (l+r)/2이다.h = N - m라고 하고 h가 정답이 가능한지 판단한다.문제 초반.. 2020. 6. 18.

티스토리툴바