[Kotlin, S2] 백준 30804번 과일 탕후루

출처: unsplash.com

 

과일 탕후루(30804번)

Silver 2

#구현 #브루트포스 알고리즘 #두 포인터

 

문제 내용

 

 

문제 접근

탕후루에 꽂혀 있는 과일의 종류는 총 9종류이고 만들어야 하는 탕후루는 특정 과일 2개가 연속되어 있는 탕후루 중 가장 긴 경우를 확인하는 것이기 때문에 9C2의 경우를 모두 체크해서 가장 긴 길이가 정답이 될 것이다.

 

길이를 체크하기 위해서는 일단 9종류의 과일 중에서 중복을 포함하지 않고 선택해야 하기 때문에 2중 반복문으로 2가지의 경우를 선택할 수 있다.

자세한 설명은 조합 알고리즘을 검색해 보면 자세한 설명이 나올 것이다.

범위는 과일 1부터 9까지이기 때문에 1..9로 설정해 준다.

 

<조건 1>

그다음 선택된 두 과일이 입력값에 있으면 길이 카운트를 세줘야 한다.

입력값이 두 과일 중 하나인 경우를 고르는 조건을 코드로 나타내면 다음과 같다.

tanghulu[k] == i || tanghulu[k] == j

위 조건이 맞으면 길이 카운트를 세준다. 연속해서 위 조건이 만족한다면 추가적으로 길이가 늘어날 것이다.

 

<조건 2>

위 조건 1이 만족하지 않았을 경우에는 현재 기록된 길이 카운트와 현재 최대 길이 중에 더 큰 값을 골라줘야 한다.

원래라면 따로 조건문을 작성해야 하지만 Kotlin에서는 max() 함수로 쉽게 작성 가능하다.

res = max(res, cnt)
cnt = 0

res보다 cnt(길이 카운트)가 크면 res가 갱신이 될 것이다. 또한 갱신을 해주고 cnt를 초기화하는 것도 잊으면 안 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

private var tanghulu = listOf<Int>()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    readLine().toInt()
    tanghulu = readLine().split(" ").map { it.toInt() }
    var answer = 0

    for (i in 1 .. 9) {
        for (j in i + 1 .. 9) {
            answer = max(answer, getLongestTanghulu(i, j))
        }
    }

    println(answer)
}

private fun getLongestTanghulu(i: Int, j: Int): Int {
    var res = 0
    var cnt = 0

    for (k in tanghulu.indices) {
        if (tanghulu[k] == i || tanghulu[k] == j) {
            cnt++
        } else {
            res = max(res, cnt)
            cnt = 0
        }
    }

    res = max(res, cnt)
    return res
}

 

문제 풀이

현재 만든 탕후루를 tanghulu List에 입력받는다.

그리고 9종류의 과일 중에서 2개를 중복 없이 고르는 경우를 2중 for로 구성해서 안에서 answer를 갱신시켜 준다.

고른 과일 2개가 연속된 가장 긴 탕후루의 길이를 구하기 위해 getLongestTanghulu를 호출한다.

 

getLongestTanghulu에서는 tanghulu를 순회하면서 선택된 과일 2개가 연속해서 들어 있는 가장 긴 탕후루의 길이를 구하고, 구한 탕후루의 길이(cnt)가 현재 가장 긴 탕후루의 길이(res) 보다 큰지 확인해 주고 크면 교체한다.

반복이 끝난 후, 마지막에 조건 1을 만족하면서 끝나는 경우가 있기 때문에 조건 2를 반복 끝나고 다시 검사해 준다.

그래야 정확한 값을 return 할 수 있다.

 

 

문제 해결 과정

원래 투 포인터로 푸는 문제이지만, 과일 종류가 적어서 무지성 탐색(브루트포스)이 가능하다.

투 포인터에 대해서는 공부를 좀 해보고 다른 문제를 풀어볼 생각이다.

이해가 덜 된 투 포인터로 풀어보려다 실패하고 무지성 탐색으로 풀어본 문제이다.