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

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

 

 

1. 코드카타 문제풀이

A. 과일 장수

문제 내용

 

문제 풀이 방법

• 사과를 m 개씩 담아서 포장할 때, 포장한 사과의 최저 점수와 담긴 사과의 개수(m)를 곱한 합을 return.
• 과일을 높은 점수의 과일끼리 포장해야 이익이 크기 때문에 score를 정렬해서 과일을 포장하면 최대의 이익을 도출할 수 있다.

 

해결 코드(스포 주의)

fun solution(k: Int, m: Int, score: IntArray): Int {
    var answer: Int = 0
    val fruitList = score.sortedArray()
    var fruitScore = k
    var addCnt = 0

    // fruitList(정렬됨)에서 m번씩 돌면서 fruit의 최소값을 구해줌.
    // answer에 최저 점수 * m을 넣어줌.
    for (i in fruitList.size-1 downTo 0) {
        fruitScore = fruitList[i]
        addCnt++

        if (addCnt == m) {
            answer += fruitScore * m
            addCnt = 0
        }
    }

    return answer
}

 

풀이 과정

• score를 정렬한 fruitList를 생성한다. 몇 개의 과일이 포장되었는지 일 수 있도록 addCnt 변수를 추가하고, 최저 점수를 알아야 하므로 fruitScore를 생성한다.
• 오름차순으로 정렬된 fruitList를 뒤에서 앞으로 반복을 하므로 큰 값에서 작은 값으로 index가 이동하게 될 것이다.
  그러면 자동으로 fruitScore에 fruitList[index]를 넣어주기만 하면 최솟값이 구해진다.
• 반복을 돌 때마다 addCnt를 1씩 더해준다. 1씩 더하면서 m과 같아지면(과일을 m개 포장함) addCnt를 초기화해 주고 answer에 fruitScore(최솟값) * m(포장된 과일 개수)을 더해준다.

 

문제 해결 과정

• 내장 정렬 함수를 쓰면 시간 초과가 날 것 같아서 indexOf를 이용해 최솟값을 찾고 answer에 값을 더하려 했는데 오히려 indexOf를 남발하니 시간 초과가 난 것 같았다(score 범위가 백만).
  그냥 한 번 정렬해 버리고 그것으로 반복문 돌리면서 판단하는 게 오히려 시간이 더 단축되었다.

// 문제의 코드
while (fruitList.size >= m) {
    var addCnt = 0
    var addIndex: Int

    while (addCnt < m) {
        addIndex = fruitList.indexOf(fruitScore)
        if (addIndex != -1) {
            addCnt++
            fruitList.removeAt(addIndex)
        } else fruitScore--
    }

    answer += fruitScore * addCnt
}

 

B. 수 정렬하기 5(백준, 15688번)

문제 내용

 

문제 풀이 방법

• 입력받은 수를 오름차순으로 출력한다.
• 시간 측정이 누적 형식으로 시간제한이 30초이다(30초 안에 모든 케이스를 통과해야 한다).

 

해결 코드(스포 주의)

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

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

    for (it in 0 until case) {
        inputList[it] = readLine().toInt()
    }

    Arrays.sort(inputList)
    for (it in inputList) {
        outputStr.append(it).append("\n")
    }

    println(outputStr)
}

 

풀이 과정

• case에서 입력받은 수만큼 반복해서 inputList(intarray)에 데이터를 입력한다.
• Arrays.sort(inputList)를 사용해 inputList를 정렬한다. 따로 변수에 담을 필요 없이 이 코드를 실행하고 inputList는 정렬된 list로 바뀐다.
• 출력은 시간 초과를 막기 위해 StringBuilder를 사용했다.

 

문제 해결 과정

• 시간 초과를 막기 위해 많은 것을 찾아보았다.
  기존에는 for문 대신 repeat을 사용했는데 repeat에 사용되는 lambda가 속도를 저하시킨다고 해서 for문으로 교체하고, Array<Int>를 사용했던 intpuList도 IntArray로 교체, 마지막 출력도 BufferedWriter로 일일이 하다가 StringBuilder로 다 모아 놨다가 println()으로 한 번에 출력하도록 해야 간신히 통과가 되더라.
• 코틀린을 사용할 때 lambda가 시간을 많이 잡아먹는다는 사실을 알게 되고, bufferedWriter를 여러 번 쓸 바에는 StringBuilder로 모아서 한 번에 출력하는 것이 더 나은 방법이라는 것도 알게 되었다. 

 

2. 개인 공부

A. 홀짝 칵테일(백준, 21312번)

문제 내용

 

문제 풀이 방법

• 숫자 3개를 입력받을 때, 홀수가 있다면 홀수들의 곱을, 홀수가 없다면 짝수들의 곱을 출력.

 

해결 코드(스포 주의)

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val evens = mutableListOf<Int>()
    var result = 1

    repeat(3) {
        // 우선순위, 홀수 -> 짝수, 큰 수 -> 작은 수
        // 홀수가 있는 경우: 짝수 데이터는 곱하지 않음.
        // 홀수가 없는 경우: 짝수를 모두 곱함.

        val cocktail = nextInt()
        if (cocktail % 2 != 0) result *= cocktail
        else evens.add(cocktail)
    }

    if (evens.size == 3) {
        // reduce로 for문을 돌리지 않고 list의 모든 데이터의 곱을 구할 수 있음.
        println(evens.reduce { total, cocktail -> total * cocktail })
    } else println(result)
}

 

풀이 과정

• 우선순위가 홀수 -> 짝수이고 큰 수 -> 작은 수이므로 입력받으면 홀수인지 체크해서 result에 곱해주기.
  아닌 경우에는 evens(list) 변수에 추가해 준다.
• 3번을 다 입력받고 evens의 size가 3이면(모두 짝수인 경우) 짝수끼리의 곱을 해줘서 return.
  그 외의 경우는 홀수가 있는 경우이므로 result를 출력.

 

문제 해결 과정

• 1년 전에 문제 이해를 못 하고 어렵게 풀려다가 포기한 문제다.
• 지금 풀고 나니 이걸 왜 못 풀었지?라는 생각이 들 만큼 쉽게 푼 문제다.

 

B. 카드 정렬하기(백준, 번)

문제 내용

 

문제 풀이 방법

• n개의 카드 묶음이 있을 때, 이를 비교하는 최소 비교 횟수를 출력.

 

해결 코드(스포 주의)

import java.util.*

// 카드를 합치는 순서(예시: 10, 20, 30, 40)
// 카드들에서 가장 작은 값과 그 다음으로 작은 값을 더함(리스트에서 삭제)
// 결과: 30, 30, 40
// 반복하기
// 우선순위 큐: 공부하기.
fun main() = with(Scanner(System.`in`)) {
    val case = nextInt()
    val pq = PriorityQueue<Int>()
    var result = 0

    for (i in 0 until case) {
        val card = nextInt()
        pq.add(card)
    }

    while (pq.size > 1) {
        val minIndex = pq.poll()
        val min2thIndex = pq.poll()

        result += minIndex + min2thIndex
        pq.add(minIndex + min2thIndex)
    }

    println(result)
}

 

풀이 과정

• 우선순위 큐 변수인 pq 생성.
• 우선순위 큐에 값을 입력받아 값을 추가함.
• pq.poll()을 해서 가장 작은 값과 2번째로 작은 값을 큐에서 빼낸다.
• 두 값을 합해 result에 추가하고 그 데이터를 pq에 넣어준다.

 

문제 해결 과정

• 우선순위 큐
  kotlin에 내장된 정렬 함수를 사용하면 시간 초과가 발생해서 찾아본 결과 우선순위 큐로 많이 해결했다고 해서 우선순위 큐를 사용했는데 따로 구현 코드 없이 poll 하고 add 하는 것으로 아주 쉽게 풀 수 있었다.
• 우선순위 큐는 백준에서 종종 사용해야 하는 개념이라 해서 이번 기회에 익혀보려 한다.

 

---

 

오늘 공부 내용 정리 및 회고

• 오늘부로 알고리즘 공부주간이 끝났다.
• 알고리즘 풀이에 흥미를 붙이고 있고, 풀다가 안되면 질문 게시판, 검색, 강좌를 이용해 풀고 있다.
• 시간 날 때마다 알고리즘 문제를 풀어 감을 잃지 않도록 해야겠다.