Algorithm/Algorithm (문제풀이)

🔒 문제 🧠 아이디어 문제 제목처럼 최소힙, 최대힙의 우선순위 큐 2개를 운영하는 방식을 떠올릴 수 있고 매우 직관적이다. 힙은 중복 데이터를 허용하므로 ㅎㅎ;; 중복원소를 허용하는 방식으로 탐색까지 $$ 모두 O(Log N) $$ 으로 만들 수 있는 방법이 있다. 바로 TreeMap 를 사용하는 것이다. 또, 굉장히 효자 API 를 제공한다. 우선순위 큐가 root 만 추출하기 편했다면 이 문제에서 요구하는 것 처럼 하나의 데이터셋 안에서 우선순위가 가장 높은 / 낮은 값을 추출할 수 있다. TreeMap, TreeSet 은 Binary Search Tree 로 구현되어 있으므로 모든 연산이 O(Log N) 이다. 근데 firstEntry(), firstKey() 이런거 시간복잡도 O(Log N) 맞아..

🔒 문제 🧠 아이디어 "마을로부터 면접장 까지의 최단 거리" => 다익스트라. V: 최대 10만 E: 최대 50만 K (면접장): 최대 10만 바로 다익스트라를 돌리면 안된다. 무식하게 모든 마을로부터 면접장까지의 거리를 다 구하려하면 $$ VE Log(E) + VK $$ 로 시간 초과가 발생한다. 모든 면접장에서 마을까지의 거리로 각각 다익스트라를 돌려도 안된다. 면접장 -> 마을까지의 거리도 무식하게 다구하면 $$ KE Log (E) + KV$$ 로 마찬가지로 시간초과 난다. 아니 이거 대체 어케해..? 따라서 마을 -> 면접장이 아닌 면접장 -> 마을까지의 최단 거리를 구하는 방식으로 접근한다. 이를 통해 다음과 같이 시간 복잡도를 줄일 수 있다. $$ E Log(E) + V $$ 여기서는 '시작 ..

🔒 문제 🧠 아이디어 💡 미리 나눈 값을 합산하여 오버플로우 방지 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader private fun getRemain(n: Long): Int { var dividend = 1L var cnt = 1 while (dividend % n != 0L) { dividend = (dividend * 10) % n + (1 % n) cnt++ } return cnt } fun main() { val br = BufferedReader(InputStreamReader(System.`in`)) val stringBuilder = StringBuilder() while (true) { val l..

🔒 문제 🧠 아이디어 $$ A^B % C $$ 1. 시간 복잡도 A를 그대로 B 번 곱하면 O(AB) 시간이 걸리고 A 와 B가 모두 Int 최대일때 2^64에 가까운 시간복잡도를 갖게된다. 어떻게 하면 시간 복잡도를 낮출 수 있을까? $$ O (Log B) $$ 로 해결할 수 있게되었다. 이 때, 주의해야 할 것이 지수승이 '짝수'냐 '홀수'냐에 따라 분기되어야 한다는 것이다. 예를 들면 A^6 % c == (A^3 % c * A^3 %c) %c 지만 A^7 % c == (A^3 % c * A^3 %c A^1 % c) %c 로 나뉘어야한다. /2 연산을 할 때 피제수가 홀수인 경우 나머지 1이 버려지기 때문이다. 2. 자료형 Int 자료형은 4바이트로 $$ ~ 2^{32} - 1 $$ Long 자료형이..

🔒 문제 🧠 아이디어 세 수의 모든 조합을 구해서 해당 숫자가 집합 내에 존재하는지 확인하는 풀이를 떠올릴 수 있다. 그러나 시간초과가 반드시 걸리기 때문에 세 수의 합이라는 상황을 두 수의 합 + 나머지 한 수 == 결과 값 k 라는 식을 변형하여 시간복잡도를 낮추는데 있다. 이로서 $$ O(N^2 \,Log_2N) $$ 시간 복잡도로 풀이할 수 있다. 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader fun main() { val br = BufferedReader(InputStreamReader(System.`in`)) val N = br.readLine().toInt() val nums = IntArray(N)..

🔒 문제 🧠 접근 방법 문제풀이 자체보다 이 문제에서 요구하는 아이디어에서 얻어갈게 많다. 수의 범위와 개수가 클 때 순서대로 index 를 두고 해당 숫자를 저장-조회 할 수 없을까? 수의 범위가 크고 갯수가 많은 경우 무조건 큰 배열을 선언해서 대소비교를 하기보다 10, 15, 4, 4, 11, 14 이렇게 있다면 중복을 제거한 (4, 10, 11, 14, 15) 로 만들고 원하는 숫자를 입력했을 때 중복 제거한 배열 내에서 인덱스만 return 하면 된다. 4 -> 0 10 -> 1 11 -> 2 14 -> 3 15 -> 4 🔑 Kotlin Code 자신보다 작은 크기의 원소의 중복 제거 값을 얻기위해 오름차순 정렬 중복 원소 제거 원본 배열로부터 하나씩 해당 원소의 인덱스를 1, 2에서 만든 배열..