본문 바로가기

알고리즘 문제/Leetcode283

[leetcode][1189] Maximum Number of Balloons 문제 : https://leetcode.com/problems/maximum-number-of-balloons/ text문자열의 모든 문자를 탐색하면서 alph[문자] = 문자 나온 횟수 위 배열을 갱신한다. balloon은 a 1개, b 1개, l 2개, n 1개, o 2개로 이루어져있기 때문에 이 개수들을 모두 만족해야한다. 따라서 (alph[a] / 1), (alph[b] / 1), (alph[l] / 2), (alpha[n] / 1), (alpha[o] / 2) 중 최소값이 정답이 된다. 시간복잡도는 O(|text|). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1189.%20Maximum%20Number%20of%20Bal.. 2019. 9. 25.
[leetcode][1202] Smallest String With Swaps 문제 : https://leetcode.com/problems/smallest-string-with-swaps/ 만약 [(1,3), (1,2)] 라는 pairs 배열이 입력으로 주어진다면 s[1], s[2], s[3] 에 있는 문자들은 direct로는 아니더라도 서로 change 할 수 있다. ex) (2, 3) 을 바꾸려면 (1, 3), (1,2) (1,3)을 바꾸면 (2,3)을 바꾼 결과가 된다. 따라서 Union-Find로 문제를 풀 수 있다. 모든 pairs를 탐색하면서 Union-Find로 한 다리 건너서라도 바꿀 수 있는 인덱스들을 그룹으로 묶는다. 같은 그룹은 속한 그룹의 s 문자열의 최소 인덱스를 가진다. 위 예제에서는 [[0], [1,2,3]] 으로 묶일 것이다. 그룹으로 다 묵었으면 k.. 2019. 9. 23.
[leetcode][1192] Critical Connections in a Network 문제 : https://leetcode.com/problems/critical-connections-in-a-network/ tarjan 알고리즘으로 풀었다. dfs로 정점들을 방문하면서 해당 정점을 방문한 순번(num)과 하나의 간선만으로 갈 수 있는 정점들 중 가장 작은 정점(low)을 저장하는 배열들을 저장한다. low 저장하는 조건. now = 현재 탐색중인 정점 next = now에서 방문할 다음 정점 1. next 정점을 이미 방문한 경우(back edge) : low[now] = min(low[now], low[next]) 2. next 정점을 아직 방문하지 않은 경우 : low[now] = min(low[now], num[next]). 2번인 경우 next 정점을 dfs로 방문하면서 low.. 2019. 9. 23.
[leetcode][1200] Minimum Absolute Difference 문제 : https://leetcode.com/problems/minimum-absolute-difference/ arr 배열을 오름차순으로 정렬한다. b - a 값은 오름차순 정렬시 바로 옆에 있는 요소들의 차가 최소 값이 된다. 따라서 정렬된 arr 배열을 앞에서부터 탐색하면서 [arr[i], arr[i-1]]가 [a, b]이다. arr[i-1] - arr[i] 값을 구하고 이 값이 이때동안 계산한 diff의 최소값보다 크다면 정답이 될 수 있으므로 skip. diff 최소 값이랑 같다면 정답배열에 추가. diff 최소 값보다 작다면 이때동안 구한 정답 배열을 빈 배열로 초기화 시키고 정답 배열에 추가한다. 시간복잡도는 정렬하는데 걸리는 시간인 O(NlogN). 소스코드 : https://github.. 2019. 9. 22.
[leetcode] 1191. K-Concatenation Maximum Sum 문제 : https://leetcode.com/problems/k-concatenation-maximum-sum/ A : arr 배열 내 앞에서부터 최대부분합 B : arr 배열 내 뒤에서부터 최대부분합 C : arr 배열 내 최대부분합 D : arr 배열 총합 이라고 하자. 정답이 가능한 경우는 위와 같다. 위 그림에서 한 칸이 배열 arr이라고 했을 때 1. B D D D A 2. D D D D D 3. C 4. B A 이 네가지 중 최대 값이 정답이 된다. 시간복잡도는 O(arr.length + k) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1191.%20K-Concatenation%20Maximum%20Sum.cpp 2019. 9. 16.
[leetcode] 1048. Longest String Chain 문제 : https://leetcode.com/problems/longest-string-chain/ 먼저 words 배열을 문자열 길이 오름차순으로 정렬한다. 이제 반드시 [words[i], words[j]] (i < j) 식으로 string chain이 만들어진다. longest length를 저장하는 map을 하나 만든다. map dp; 위 map에는 key : words[i], value : longest length of a word chain 이 들어간다. 이제 words를 앞에서부터 탐색한다. 탐색 중인 words 문자열을 word2라고 했을 때 word2에서 문자를 하나씩 빼면서 string chain을 만드는 word1인지 확인한다. 만약 string chain을 만들 수 있는 word1.. 2019. 9. 11.

티스토리툴바