[Android, 내일배움캠프] 공부일지(2024-05-28)

오늘 공부한 내용 정리(2024년 5월 28일)

 

 

1. 코드카타 문제풀이

A. 기사단원의 무기

문제 내용

 

문제 풀이 방법

• 기사 number번까지 기사가 있을 때, number의 약수의 개수만큼의 공격력을 가진 무기를 쓸 수 있다.
• 공격력이 limit를 초과했을 경우, power의 공격력을 가진 무기로 대체된다.
• 공격력이 3일 때, 철의 무게가 3이 필요하다. 이때 기사들에게 모두 무기를 쥐어주려면 철의 무게가 얼마나 필요한지 계산해서 return.

 

해결 코드(스포 주의)

import kotlin.math.sqrt

fun solution(number: Int, limit: Int, power: Int): Int {
    var answer: Int = 0

    repeat(number) { num ->
        val divisors = mutableListOf<Int>()

        // 약수 구하는 방법
        // N의 약수를 구할 때는, 1부터 N의 제곱근까지의 수만 0으로 나누어 떨어지는지 체크.
        // 이미 구해진 약수들에 N을 나누어 추가적인 약수를 구할 수 있음.
        val sqrt = sqrt((num+1).toDouble()).toInt()
        for (i in 1..sqrt+1) {
            if ((num+1) % i == 0) {
                divisors.add(i)
            }
        }

        var divisorCnt = divisors.size
        divisors.forEach {
            if (!divisors.contains((num+1) / it)) divisorCnt++
        }
        println("${num+1}까지의 약수의 개수: $divisorCnt")

        answer += if (divisorCnt > limit) power else divisorCnt
    }

    return answer
}

 

풀이 과정

• N의 약수를 구하기 위해서는 1부터 N의 제곱근 + 1까지의 수가 0으로 나누어 떨어지는지 확인한다.
  나누어 떨어진 숫자들을 divisors에 추가한다.
• divisors의 데이터들 중에 num+1과 약수를 나눈 값이 divisors에 포함되어 있지 않은 경우에만 divisorCnt를 1씩 더해준다.
• 위 과정까지 하게 되면 1부터 number까지의 각 숫자에 대한 약수의 개수가 나오는데 약수의 개수가 limit를 초과하는지 체크해서 초과한다면 power를 아니면 그냥 divisorCnt를 answer에 더해준다.

 

B. 숫자 짝꿍

문제 내용

 

문제 풀이 방법

• 두 숫자 문자열 x, y가 주어질 때, x와 y에 공통으로 나타는 숫자들을 return.
• 짝꿍이 존재하지 않으면 0을 return, 짝꿍 정수가 0밖에 없으면 0을 return.
• x, y의 자릿수가 3백만이기 때문에 시간 초과가 나기 쉽다.

 

해결 코드(스포 주의)

fun solution(x: String, y: String): String {
    val answer = StringBuilder()
    val xArr = MutableList(10) { 0 }
    val yArr = MutableList(10) { 0 }

    // x, y에서 0 ~ 9까지의 숫자의 개수를 센 다음. x, y에 숫자가 존재하는 애들만 builder에 넣기..
    x.forEach {
        xArr[it.digitToInt()]++
    }
    y.forEach {
        yArr[it.digitToInt()]++
    }

    // 0 ~ 9 까지 10종류의 숫자만 있음.
    for (number in 9 downTo 0) {
        // x와 y가 0보다 크다는 것은 x와 y에 숫자가 존재한다는 뜻.
        val xNumberCnt = xArr[number]
        val yNumberCnt = yArr[number]
        if (xNumberCnt > 0 && yNumberCnt > 0) {
            if (xNumberCnt > yNumberCnt) {
                repeat(yNumberCnt) { answer.append(number) }
            } else {
                // x, y가 같거가 y가 큰 경우.
                repeat(xNumberCnt) { answer.append(number) }
            }
        }
    }

    // answer가 비어 있으면 -1을 return.
    if (answer.isEmpty()) return "-1"
    // answer에서 0인 데이터들의 length와 answer의 length가 같을 때 => answer에 0밖에 없다는 뜻.
    if (answer.filter { it == '0' }.length == answer.length) return "0"
    return answer.toString()
}

 

풀이 과정

• 숫자는 0 ~ 9까지의 정수로 구성되어 있기 때문에 xArr, yArr 변수에 size를 10으로 설정하고 모든 값을 0으로 설정해 준다.
• answer에는 StringBuilder를 적용해 준다. 적용하지 않으면 시간 초과가 발생한다.
• 각각 x와 y의 size만큼 반복문을 돌려서 해당 숫자에 해당하는 index에 값을 +1만큼 해준다.
  x가 3212일 때, xArr = [0,1,2,1,0,0,0,0,0,0]
• number를 9에서 0으로 1씩 감소하는 for문을 만들어 준다(가장 큰 숫자를 구해야 하기 때문이다).
• xNumberCnt와 yNumberCnt 중에 더 작은 데이터 개수만큼 answer에 추가해 준다(xNumberCnt와 yNumberCnt의 데이터 개수는 0보다 커야 한다).
  StringBuilder.append(): 데이터 추가
• answer가 비어 있으면 짝꿍 정수가 없다는 뜻이므로 -1을 return.
• answer에서 0인 데이터들만 불러온 데이터의 length가 원래의 answer의 length와 같다면 answer 데이터가 0밖에 없다는 뜻이기 때문에 0을 return.
• 런타임 에러가 발생하는 경우 int, long으로 변환하는 코드에서 크기 초과가 발생해 에러가 발생하는 경우가 많다.
  자릿수가 3백만이면 long의 제한도 가볍게 뛰어넘기 때문에 무조건 string을 이용해 코드를 짜주어야 한다.

 

해결 과정

• 범위 제한이 너무 커서 런타임 에러와 시간 초과가 많이 발생했다.
• 시간 초과 문제는 StringBuilder를 이용해 해결했다. 테스트 케이스 1 기준으로 문제 풀이 시간이 70ms에서 2ms로 줄어들었다.
• 런타임 에러 문제는 검색해 보아도 많이 나오지 않아서 혹시 테스트할 때 숫자를 크게 만들면 되지 않을까 해서 999999999... 를 테스트해 보았는데 런타임 에러가 나서 특정 정수가 10개 이상으로 있을 때의 처리가 안되어 있어서 런타임 에러가 발생한 것을 알게 되고 기존의 StringBuilder로 구현한 코드를 다시 mutableList로 갈아야 했다.

// 문제 코드
// 0 ~ 9까지의 경우가 있기 때문에 0 10개로 초기화.
val xArr = StringBuilder("0000000000")

// 특정 정수가 10개 이상인 경우 런타임 에러가 발생하는 코드.
x.forEach {
	xArr[it.digitToInt()]++
}

 

2. 개인 공부

A. 부녀회장이 될테야(백준, 2775번)

문제 내용

 

문제 풀이 방법

• a층에 b호에 살기 위해서는 0층부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 할 때, 해당 집의 거주민을 출력(자신 제외)
• 위의 규칙을 모든 거주민이 지키고 있다.
• 0층의 i호에는 i명이 산다.
• 1층 3호의 거주민을 구하는 경우. 0층부터 1층까지 사람들의 수만큼 사람들을 데려와 살아야 한다.
  0층에는 3호까지 있기 때문에 1, 2, 3명으로 6명이다. 이 규칙을 모든 거주민이 지키고 있기 때문에 1층 1호의 경우 0층 1호의 사람을 끌고 와야 하기 때문에 1명. 1층 2호는 0층 2호의 사람들과 1층 1호의 사람들이 살 수 있어야 하기 때문에 3명... 위와 같은 규칙으로 반복된다.

	1호	2호	3호
0층	1명	2명	3명
1층	1명	3명	6명
2층	1명	4명	10명

 

• 위의 표를 참고하면, 2층 3호에 살려면 4명과 6명의 합인 10명이 살 수 있어야 한다. 4명과 6명은 각각 2층 2호, 1층 3호에 살기 위해 데려와서 살아야 하는 사람들의 수이다. 이미 사람들을 계속 데려와서 살고 있기 때문에, 옆집과 윗집 사람들만 불러와도 되는 것이다.

 

해결 코드(스포 주의)

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()

    repeat(case) {
        val floor = readLine().toInt()
        val room = readLine().toInt()
        val list = MutableList(floor+1) { MutableList(room) { 0 } }

        // 파스칼의 삼각형 알고리즘.
        // 구하고자 하는 수는 왼쪽 숫자와 위쪽 숫자의 합.
        for (i in 0..floor) {
            if (i == 0) {
                repeat(room) {
                    list[0][it] = it+1
                }
            } else {
                list[i][0] = 1
                for (j in 1 until room) {
                    list[i][j] = list[i-1][j] + list[i][j-1]
                }
            }
        }

        println(list[floor][room-1])
    }
}

 

풀이 과정

• 몇 개의 case가 있을지 case 변수를 만들어 입력받는다(Test case T)
• case만큼 반복해서 floor와 room을 입력받는다. 그리고 2중 MutableList를 만들어 층과 방마다 들어갈 수 있는 사람 수를 넣을 수 있게 함.
• a층 b호에 살기 위해서는 왼쪽 집과 윗집을 더한 값을 넣어 주어야 하기 때문에 list에 데이터를 추가한다.
• 반복문 완료 후 가장 마지막 index의 데이터를 불러온다. list의 가장 위층, 가장 끝집.

 

해결 과정

• 처음에 문제 이해를 하는 데 가장 어려움을 겪었던 것 같다.
• 모든 입주민이 자신의 1층부터 자신과 동일한 호실까지의 사람들의 수만큼을 데려와 살아야 한다는 것에서 찾아보다 위의 표처럼 특정 규칙을 찾았고 그것이 파스칼의 삼각형과 유사하다는 것을 알게 되었음(검색으로).
• 추가적으로 파스칼의 삼각형에 관련된 문제를 풀어볼 예정(검색 없이).

 

B. 파스칼의 삼각형(백준, 16395번)

문제 내용

 

문제 풀이 방법

• 파스칼의 삼각형을 구성해서 n번째 줄의 k번째 수를 return.

 

해결 코드(스포 주의)

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val input = nextLine()
    val line = input.split(" ")[0].toInt()
    val num = input.split(" ")[1].toInt()
    val pascalTriangle = MutableList(line) { MutableList(line) { 0 } }

    pascalTriangle[0][0] = 1
    for (i in 1 until line) {
        pascalTriangle[i][0] = 1
        pascalTriangle[i][i] = 1

        for (j in 1 until i) {
            pascalTriangle[i][j] = pascalTriangle[i-1][j] + pascalTriangle[i-1][j-1]
        }
    }

    println(pascalTriangle[line-1][num-1])
}

 

풀이 과정

• 몇 번째 줄인지 알 수 있는 line 변수와 몇 번째 숫자인지 알 수 있는 num 변수 생성
• 가로의 size가 line이고, 세로 size도 line인 2중 MutableList인 pascalTriangle 변수를 생성한다. 이 변수에 파스칼의 삼각형을 구성할 예정이다. 모든 숫자는 0으로 초기화한다.
• 2중 for문을 구성하는데, 바깥 for문은 1부터 line까지 반복하는 반복문이고 안쪽 for문은 1부터 i까지 반복하는 for문이다(파스칼의 삼각형은 1번째 줄이면 숫자 1개, 5번째 줄이면 5개, n번째 줄이면 n개이기 때문).
• 첫 번째 줄의 1은 for 문 시작하기 전에 1로 바꿔준다. 2중 for문이 모두 1로 시작하는 이유이다.
• 파스칼의 삼각형의 양 끝의 숫자는 모두 1이기 때문에 외부 반복문에서 이를 처리해 준다(i, 0이랑 i, i index에 해당하는 데이터를 1로 변경).
• 내부 반복문에서는 파스칼의 삼각형 규칙을 적용해 준다. 배열의 index로 비유하면 i, j index의 숫자는 i - 1, j index의 수와 i - 1, j - 1 index에 해당하는 숫자들의 합이다.

출력 결과

• 파스칼의 삼각형을 구성한 후, line번째 줄의 num번째 숫자이므로 line - 1, num - 1 index의 값을 출력한다(배열의 index가 0부터 시작하기 때문).

 

---

 

간단 정리

• 오늘 문제들은 시간 초과에 런타임 에러까지 고려해야 하는 문제가 있었다.
• 문제가 어제에 비해서는 어려운 축에 들었던 만큼. 새롭게 알게 된 StringBuilder와 파스칼의 삼각형 알고리즘을 공부해 볼 수 있었다.