algorithm

🔒 문제 🧠 아이디어 세 수의 모든 조합을 구해서 해당 숫자가 집합 내에 존재하는지 확인하는 풀이를 떠올릴 수 있다. 그러나 시간초과가 반드시 걸리기 때문에 세 수의 합이라는 상황을 두 수의 합 + 나머지 한 수 == 결과 값 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에서 만든 배열..

🔒 문제 🧠 아이디어 ArrayDeque 를 사용하여 테트리스의 밀어 붙이기 아이디어를 사용. 이 때, index 방향을 제대로 설정해줘야한다. 합치는 구간에서도 진행 방향쪽 블록을 먼저 합쳐야 하기 때문에 index 진행 방향에 유의해야한다. 이 부분에서 실수하기 굉장히 쉬운 문제다. 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader import kotlin.math.max enum class Direction{ EAST, WEST, SOUTH, NORTH } // (1) 0으로 빈칸은 모두 당겨오기 처리 // (2) 당겨온 다음에 겹치기. // 겹칠 때 상태 확인 // Current modification 방지 p..

🔒 문제 🧠 아이디어 톱니바퀴 회전 아이디어 시계 방향 반시계 방향 자료구조로 덱 사용 회전 방향을 결정하는 것은 index2, 6 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader import java.util.* import kotlin.collections.ArrayDeque private fun rotateGears(gearNum: Int, gears: Array, gearRotateDirection: IntArray) { when (gearRotateDirection[gearNum]) { -1 -> { gears[gearNum].addLast(gears[gearNum].removeFirst()) } 1 -> ..

🔒 문제 🧠 아이디어 1. 월-일을 모두 Days (일) 로 통일 1월 1일-> 1 12월 31일 -> 365 로 치환한다. 이를 위해 HashMap 을 생성하여 각 월마다 일수를 매핑시켜주었다. private final HashMap monthDayMap = new HashMap(); { monthDayMap.put(0, 0); monthDayMap.put(1, 31); monthDayMap.put(2, 28); monthDayMap.put(3, 31); monthDayMap.put(4, 30); monthDayMap.put(5, 31); monthDayMap.put(6, 30); monthDayMap.put(7, 31); monthDayMap.put(8, 31); monthDayMap.put(9, 3..

비트마스킹 기법을 사용하기 위해 익혀야할 비트연산자를 정리해보자. 1. 길이 N을 갖는 이진수를 모두 1 (flag on) 상태로 만들기 표현식 $$ (2 11111 // 십진수로는 2 ^ N - 1 로 표현가능하다. // 2 ^ 6 - 1 == 63 val num = (1 shl (5 + 1)) - 1 println("=============") println("All flag on") println(toDecimalString(num)) println(toBinaryString(num)) println("=============") } 결과 2. 특정 index flag bit 키기 표현식 $$ num\; or \; (1 11111 // 십진수로는 2 ^ N - 1 로 표현가능하다. // 2 ^ 6 ..