문제 https://leetcode.com/problems/find-missing-elements 풀이 연속된 정수 구간에 속한 모든 정수가 들어 있’던’ 수열 nums가 주어진다. 일부 원소가 사라진 상태인 상태인데, 이 사라진 원소들을 배열에 오름차순으로 담아 리턴하면 된다. 최대값과 최소값은 사라지지 않았다고 하니까, 정수 구간의 크기를 구할 수 있다. 그 정수 구간을 순회하면서 빠진 원소들을 찾으면 된다. 정렬을 이용해서 풀 수도 있는데, 이러면 시간 복잡도가 평균 $O(n \times \log n)$이 된다. 큰 차이는 안나지만 Hast Set을 이용하면 평균 $O(n)$에 풀 수 있다. ...
문제 https://codeforces.com/problemset/problem/520/B 풀이 정수 n, m이 주어지고, 연산 2개 (* 2, - 1)을 이용해서 n을 m으로 만드는데 필요한 연산의 최소 개수를 출력하면 된다. $1 <= n, m <= 10^4$ 제약조건과 2배로 만드는 연산을 생각해보면 만들 수 있는 숫자의 개수는 최대 2만개 정도이다. 이 숫자들을 각각을 노드라 생각하면, 연산으로 정의되는 노드간 연결도 명확한 그래프로 생각할 수 있다. 그러면 이 문제는 최단 거리 문제가 되므로 BFS를 사용해서 쉽게 풀 수 있다. 2배 연산이 있으므로 방문 확인 배열의 크기를 m * 2로 잡고 BFS를 하면된다. (방문 확인 배열도 할 겸 거리를 세는 기능도 넣으면 좋다.) ...
문제 https://leetcode.com/problems/stone-game-iii 풀이 번호가 적힌 돌이 있고, 두 명(Alice, Bob)이 번갈아 가면서 그 돌을 1개에서 3개까지 가져갈 수 있다. 2명 다 이상적으로 플레이 했을 때, 돌에 적힌 번호를 더한 합이 더 많이 가져간 사람의 이름을 리턴하면 된다. 항상 Alice가 먼저 시작한다. 약간 특이한 DP 문제이다. 점화식을 ‘Alice’ ‘Bob’을 특정하지 않고 ‘현재 차례인 사람이 상대보다 돌을 가질 수 있는 최대 개수’로 정의해야한다. 점화식은 다음과 같다. $$ dp[i] = \max \begin{cases} stoneValue[i] - dp[i+1] \\ stoneValue[i] + stoneValue[i+1] - dp[i+2] \\ stoneValue[i] + stoneValue[i+1] + stoneValue[i+2] - dp[i+3] \end{cases} $$ ...
문제 https://leetcode.com/problems/find-greatest-common-divisor-of-array 풀이 수열 nums의 원소 중 가장 큰 원소의 가장 작은 원소의 GCD를 리턴하면 된다. 처음에 max()와 min()을 썼는데, 제출 시간이 거의 최하위권이길래 for loop로 다시 작성했다. GCD 자체는 유클리드 호제법을 이용해서 구한다. 코드 class Solution { func findGCD(_ nums: [Int]) -> Int { func gcd(_ a: Int, _ b: Int) -> Int { b == 0 ? a : gcd(b, a % b) } var min = Int.max var max = 0 for num in nums { min = min > num ? num : min max = max < num ? num : max } return gcd(min, max) } }
문제 https://codeforces.com/problemset/problem/455/A 풀이 풀이 배열a에서 얻을 수 있는 최대 점수를 구하는 DP 문제이다. 어떤 값 x를 선택하면 x만큼의 점수를 얻고, 배열에 있는 x - 1과 x + 1은 모두 제거된다. 여기서 중요한 점은 같은 값을 여러 개 가지고 있다면 하나씩 선택할 이유가 없다는 것이다. x를 선택하는 순간 x - 1과 x + 1은 모두 사용할 수 없으므로, 선택한다면 값이 x인 원소는 모두 선택하는 것이 항상 이득이다. 따라서 입력 배열의 순서는 의미가 없어지고, 각 숫자가 몇 번 등장하는지만 알면 된다. 값 x가 frequencies[x]번 등장한다면, x를 선택했을 때 얻는 점수는 x * frequencies[x]이다. ...
문제 https://codeforces.com/problemset/problem/279/B 풀이 책을 읽는데 걸리는 시간이 담긴 크기 n 배열 a가 주어지고, 책을 읽을 수 있는 시간 t가 주어진다. 특정 인덱스를 정해서 그 인덱스부터 책을 순서대로 읽었을때, 최대로 읽을 수 있는 책의 개수를 출력하면된다. 모든 경우의 수를 탐색하려면 $O(n^2)$의 시간 복잡도를 가지는데 책의 개수가 10만개 이므로, 시간 내로 해결하기는 힘들다. ‘순서대로’라는 조건이 있으므로, 투 포인터를 이용하면 쉽게 풀 수 있다. 단 배열 a의 원소의 크기가 t보다 클 수 있으므로, 단 한권의 책도 읽지 못하는 경우가 있다. 그래서 책을 0권 읽는 경우의 수도 생각해서 코드를 짜야 한다. ...
문제 https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-i 풀이 휴대전화의 2에서 8까지의 숫자에 문자를 배치할 수 있고, 2개 이상의 수가 배치되었을 땐 여러번 눌러야 뒤에 있는 숫자를 타이핑 할 수 있다. 스트링 word가 주어졌을 때, 버튼을 가장 적게 눌러 word를 타이핑 했을 때의 타이핑 수를 리턴하면 된다. 각 키의 첫 번째 문자는 1번, 두 번째는 2번… 눌러야 하므로 많이 등장하는 문자일수록 누름 횟수가 적은 앞자리에 배치해야 한다. 빈도수 내림차순 정렬 후, 인덱스를 8로 나눈 몫 + 1이 해당 문자의 누름 횟수가 된다. ...
문제 https://codeforces.com/problemset/problem/189/A 풀이 길이가 n인 리본이 하나 주어지고, 이를 a, b, c 의 크기로만 조각낼 수 있을 때, 최대로 만들 수 있는 조각의 개수를 출력하는 문제이다. 잘린 리본 조각의 크기가 정해져 있으므로, 그리디가 아니라 DP로 접근해야 한다. 그리디로 접근하면 마지막에 남은 리본 조각의 크기를 확정할 수 없기 때문이다. dp[i]를 길이 i인 리본을 조각냈을 때의 최대 조각 수로 정의하면, 점화식은 다음과 같다. $$dp[i] = \max_{x \in {a, b, c}}(dp[i - x] + 1) \quad \text{if } i \geq x \text{ and } dp[i-x] \neq -1$$ ...
문제 https://leetcode.com/problems/smallest-palindromic-rearrangement-ii 풀이 1번 문제와 마찬가지로 팰린드롬의 성질상 절반만 결정하면 전체가 결정된다. 따라서 이 문제는 절반 문자열의 k번째 사전순 순열을 구하는 문제로 단순화된다. 각 문자의 등장 횟수를 세고, 홀수 번 등장하는 문자는 팰린드롬의 가운데에 배치한다. 나머지는 2로 나눠 halfTable을 만든다. 절반 문자열에는 중복 문자가 있을 수 있으므로, 전체 순열 수는 단순히 $n!$이 아니라 중복 순열 공식으로 구해야 한다. $$\frac{n!}{\prod_{i} n_i!}$$ 여기서 n은 절반 문자열의 길이, n_i는 각 문자의 개수이다. 이 값이 k보다 작으면 k번째 순열이 존재하지 않으므로 빈 문자열을 반환한다. ...
문제 https://codeforces.com/problemset/problem/230/B 풀이 T-Prime을 약수가 3개인 수라고 정의하고, $n$개의 크기의 수열 $x$의 원소 각각에 대해서 그 수가 T-Prime인지 확인하는 문제이다. 약수가 3개라는 뜻은, $1$과 자기 자신 그리고 $\sqrt{x_i}$만을 약수로 가진다는 뜻이다. 즉, T-Prime은 어떤 수의 제곱이어야 한다. 그 ‘어떤 수’의 조건은 무엇일까? 약수의 약수는 결국 약수이다. T-Prime은 $1$, ‘어떤 수’, 자기 자신만을 약수로 가지므로, ‘어떤 수’는 소수여야 한다. 결국 이 문제는 소수 판별 문제로 단순화된다. $x_i$의 최댓값이 $10^{12}$이지만, T-Prime 여부를 판별하려면 $\sqrt{x_i}$가 소수인지만 확인하면 되므로 체는 $\sqrt{10^{12}} = 10^6$까지만 구성하면 충분하다. 에라토스테네스의 체의 시간복잡도는 (거의) $O(N)$이고, 이후 각 쿼리는 $O(1)$에 처리되므로, $n \leq 10^5$인 입력 전체에 대해 전처리 $O(10^6)$ + 쿼리 $O(n)$으로 풀 수 있다. ...