[Kotlin] 공부일지(2024-06-15)

오늘 공부한 내용 정리(2024년 6월 15일)

 

꾸준히 정진해 하늘로 계속 올라가는 열기구처럼 삶의 목표를 위해 나아가는 사람이 되자.

 

1. 알고리즘 문제풀이

A. 2xn 타일링 2(백준, S3, 11727번)

문제 내용

 

문제 풀이 방법

2 x n의 직사각형을 타일 1 x 2, 2 x 1, 2 x 2로 빠짐없이 채우는 경우의 수를 구해 출력.

 

 

해결 코드(스포 주의)

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val fillArray = Array(nextInt()) { 0 }

    for (i in fillArray.indices) {
        if (i == 0) fillArray[0] = 1
        else {
            // 홀수 index임
            if (i % 2 != 0) fillArray[i] = fillArray[i-1] *2 +1
            else fillArray[i] = fillArray[i-1] *2 -1
            fillArray[i] %= 10007
        }
    }

    println(fillArray.last())
}

 

풀이 과정

먼저 width가 1일 때부터 5까지 몇 개의 경우의 수가 있는지 직접 계산해 보았다.

2 x 1 = 1

2 x 2 = 3

2 x 3 = 5

2 x 4 = 11

2 x 5  = 21

위 경우의 수를 보아 width가 짝수일 때는 이전 경우의 수의 2배에서 1을 더하고 홀수일 때는 이전 경우의 수의 2배에서 1을 빼는 것이 규칙이라는 것을 알 수 있다.

fillArray를 만들어 배열에 경우의 수를 저장하겠다.

width가 1일 때는 무조건 1가지의 경우이므로 1로 값을 변경한다. 이 값을 기반으로 다음 데이터들의 값을 구해 나갈 것이다.

i가 2로 나누어 떨어지지 않으면 width가 짝수라는 뜻이다(0부터 시작했기 때문에 2로 나누어 떨어지지 않는 경우가 width가 짝수가 되는 경우일 것이다.). 그러므로 이전 데이터를 불러와 2를 곱하고 1을 더한다.

홀수일 때는 2를 곱하고 1을 뺀다.

마지막에 그 값에 10007을 나눈 나머지값으로 최종 확정 짓는다.

10007로 나누는 이유는 width가 1000까지 있는데 1000까지 가는 도중에 경우의 수가 int 범위를 초과하기 때문에 10007로 나눠 출력하라는 것이다.

 

문제 해결 과정

규칙을 찾아서 DP를 응용하면 매우 쉽게 풀리는 간단한 문제이다. DP를 풀기 위해서는 규칙을 찾는 것이 매우 중요할 것 같다는 것을 알게 해 준 문제.

 

B. 이중 우선순위 큐(백준, G4, 7662번)

문제 내용

 

문제 풀이 방법

test case가 주어지고 명령이 주어질 때 명령에 맞게 큐의 데이터를 변경한 후, 큐가 비어 있으면 EMPTY를 출력하고 그렇지 않으면 큐의 최댓값과 최솟값을 출력.

 

해결 코드(스포 주의)

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val testCase = readLine().toInt()

    for (c in 0 until testCase) {
        val commandCnt = readLine().toInt()
        val treemap = TreeMap<Int, Int>()

        for (i in 0 until commandCnt) {
            val (function, number) = readLine().split(" ")

            when (function) {
                "I" -> {
                    if (treemap.containsKey(number.toInt())) treemap[number.toInt()] = treemap[number.toInt()]!! + 1
                    else treemap[number.toInt()] = 1
                }
                "D" -> {
                    if (treemap.isNotEmpty()) {
                        if (number == "1") {
                            if (treemap[treemap.lastKey()] == 1) treemap.remove(treemap.lastKey())
                            else treemap[treemap.lastKey()] = treemap[treemap.lastKey()]!! - 1
                        } else {
                            if (treemap[treemap.firstKey()] == 1) treemap.remove(treemap.firstKey())
                            else treemap[treemap.firstKey()] = treemap[treemap.firstKey()]!! - 1
                        }
                    }
                }
            }
        }

        if (treemap.isEmpty()) bw.write("EMPTY\n")
        else bw.write("${treemap.lastKey()} ${treemap.firstKey()}\n")
    }

    bw.flush()
    bw.close()
}

 

풀이 과정

데이터 정보를 담을 treemap을 생성한다(key로 number를 넣고, value로 number의 개수를 저장할 것이다).

command 정보를 받아올 수 있도록 function와 number 변수를 선언한다.

function이 I이면 treemap에 같은 값이 있는지 확인하고, 있으면 기존 값에 value를 1씩 증가시키고, 아닌 경우는 새롭게 number를 key로 가지는 데이터를 생성한다.

function이 D인 경우는 treemap이 비어 있지 않을 때만 로직을 수행한다.

number가 1이면 최댓값을 제거해야 한다. treemap에는 가장 큰 값이 가장 뒤에 오므로 lastKey()로 마지막 key값을 불러온 다음 마지막 key값의 value가 1이면 1개밖에 없다는 뜻이므로 마지막 key의 값을 삭제한다.

1보다 큰 경우는 마지막 key의 value를 1을 뺀다.

반복을 종료한 후, treemap이 비어 있으면 EMPTY를 출력하고, 아닌 경우에는 마지막 키값(최댓값)과 첫 번째 키값(최솟값)을 출력한다.

 

 

문제 해결 과정

PriorityQueue를 사용해서 문제를 해결하려 했지만 시간 초과가 발목을 잡았다.

우선순위 큐에 데이터를 넣는 것이 많은 시간을 잡아먹는 것 같았다. 그래서 다른 자료 구조를 찾아보다가 treemap으로 푼 사람의 포스팅을 봐서 treemap을 이용해 문제를 해결했다.

treemap을 깊게 공부하고 해결하지는 않았지만 우선순위 큐보다 좋은 자료 구조인 것 같다. 기억해 뒀다가 나중에 써먹어야겠다.

---

 

오늘 공부 내용 정리 및 회고

알고리즘만 풀었던 날이다.

새로운 자료 구조를 알게 되었지만 DP에는 아직 진척이 없다. 역시 많이 풀어보는 게 답인 걸까?