algorithm

🔒 문제 ⚠️ 실수 노트 1번 ~ 6번에 대해 전개도가 있으므로 동서남북 이동시 오게되는 윗 칸을 저장하는 6개 면을 의미하는 객체 생성 각 객체는 값을 가지고 객체별로 동서남북으로 주사위 방향이 이동했을 때 표현하는 객체 값을 고정해둠. 총 6개 면에 대해 동서남북 주사위 굴리기시 표현되는 윗칸을 '고정'하면 안된다. 굴리면서 보는 각도가 달라질 수 있기 때문이다. // 전개도의 각 면에대해 data class 를 미리 만들고 초기화 // ⚠️ 틀린 접근 방법 data class DiceSquare(var curVal: Int = 0, var east: DiceSquare?, var west: DiceSquare?, var south: DiceSquare?, var north: DiceSquare?, ..

🔒 문제 🧠 아이디어 가로 6, 세로 12를 갖는 테트리스 판의 일종이다 우선 4개 이상의 뿌요 조각이 인접해있을 때만 '.'으로 대치한다. + '.'으로 대치된 조각이 있으면 아래로 뿌요조각을 당겨야한다. 뿌요 조각을 당기는 아이디어가 핵심이다. 세로 막대를 의미하는 LinkedList 를 미리 6개 생성해두고 '.'만을 모두 제거해 남은 뿌요 조각을 뿌요판에 붙여넣는다. 또, 판 크기 자체가 12 * 6 == 72회로 작으므로 전체 판을 매번 긁어도 시간 초과하지 않겠다는 직관을 가지고 풀이했다. 하나의 뿌요조각이 다음 단계로 이어지려면 매번 4조각씩 해도 총 18라운드가 최대다. 72 * 72 * 18 => 약 10만 으로 절대 시간초과가 나지않는다. 🔑 Kotlin Code import java...

🔒 문제 🧠 아이디어 "()"을 모두 '*'로 미리 대치한다. 🔑 풀이 1. Kotlin Code ')' 을 만날 때마다 이전 '(' 까지 pop 하며 *의 개수를 카운팅하는 무식한 방법으로 풀이했다. import java.io.BufferedReader import java.io.InputStreamReader import java.util.* fun main() { val bufferedReader = BufferedReader(InputStreamReader(System.`in`)) val str = bufferedReader.readLine().replace("()", "*") val stack = Stack() var answer = 0 for (char in str) { when (char) ..

🔒 문제 🧠 아이디어 반드시 2개의 정점을 경유해서 가야하므로 Way point (경유지) 1, 2 가 존재할 때 선택할 수 있는 경로는 다음 2가지로 좁혀진다. 출발 노드 -> 경유지 1 -> 경유지 2 -> 목적지 출발 노드 -> 경유지 2 -> 경유지 1 -> 목적지 여기서 구해야 할 값은 다음 5가지다. 출발 노드 -> 경유지 1의 최단경로 출발 노드 -> 경유지 2의 최단경로 경유지 1 -> 목적지의 최단경로 경유지 2 -> 목적지의 최단경로 경유지 1 - 경유지2 의 최단경로 양방향 그래프기 때문에 경유지 1-> 경유지 2, 경유지 2-> 경유지1는 서로 거리가 같기 때문에 한 번만 구하면 된다. 최단 경로를 구해야하므로 Dijkstra 알고리즘 사용한다. 출발 노드 -> 경유지 1,2 는 한..

🔒 문제 🧠 아이디어 스티커를 포함한 모든 모눈 종이는 결국 직사각형 형태다. 바탕이 될 노트북 모눈종이판을 'noteBookTable' 스티커 조각들을 'sticker' 라고하면 1. 스티커 붙이기 가능 불가능 여부 판별법 다음 4가지 케이스가 존재한다. ✔️noteBookTable 에서는 0 (비어있고) sticker 에서는 1 (스티커) ✔️noteBookTable 에서는 1 (이미 다른 스티커가 붙어있고) sticker 에서는 0 (공백) ✔️noteBookTable 도 0 (비어있고) sticker 에서도 0 ❌noteBookTable 에서 1 (이미 다른 스티커가 붙어있고) sticker 에서도 1 (스티커) 위 케이스중 1,2,3 번만 스티커 붙이기가 가능한 케이스다. noteBookTabl..

알고리즘 문제에 간간히 등장하는 행렬 회전 로직, N * N 정사각형은 물론 N * M 직사각형 행렬에도 활용 가능한 코드를 미리 작성해보자. 📝 규칙 요점 정리 90도 회전함수 원본 행렬을 90도 회전시켜서 회전된 행렬을 반환한다. fun rotate(originalArray: Array) : Array { val originalRowSize = originalArray.size val originalColSize = originalArray.first().size // 행 열 크기 전환 val rotatedArray = Array(originalColSize){IntArray(originalRowSize)} for (row in originalArray.indices) { for (col in ori..