[ 백준 26876 ] - New Time (Kotlin)

 

 

26876번: New Time

 

문제 이해 & 기본 개념

잘못된 시간과 정확한 시간이 주어지고, 1분씩 증가하는 A버튼, 1시간씩 증가하는 B버튼이 있다.

버튼을 최소 횟수로 눌러서 정확한 시간에 맞추는 문제

---

중요 포인트

1. 시간이 증가하는 것은 분에 영향이 없지만, 분이 증가는 것은 시간에 영향을 줄 수 있음
   • 60분이 넘어가면 시간이 증가 됨
2. 분을 먼저 증가시켜야 함
   • 1번과 같은 이유로 시간은 분에 의해 증가될 수 있음
   • 따라서, 분을 먼저 증가시켜야 함

 

---

최종 풀이

1. 분이 다른 경우 분을 증가 시킴
2. 분이 같은 경우에만 시간을 증가 시킴

---

Tip

아래와 같이 시간/분을 증가(또는 감소) 시키는 로직을 별도의 메소드로 구분해놓으면 좋음

실수도 줄일 수 있고 중복 코드도 줄일 수 있음

fun Triple<Int, Int, Int>.addMinute(minute: Int = 1) 
	= copy((first + ((second + minute) / 60)) % 24, (second + minute) % 60, third+ minute)
    
fun Triple<Int, Int, Int>.addHour(hour: Int = 1) 
	= copy((first + hour) % 24, second, third+hour)

 

---

주의할 점

아래와 같이 특정 시간에서 시간과 분을 둘 다 증가시키면 시간 초과가 발생할 수 있음

조건 분기를 통해 불필요한 경우의 수를 찾는게 중요

    while (q.isNotEmpty()){
        val cur = q.poll()
        if(cur.first == nextHour && cur.second == nextMin) return cur.third

        if(nextHour != cur.first) q.add(cur.addHour())
        if(nextMin != cur.second) q.add(cur.addMinute())
    }

 

 

---

 

소스 코드

import java.util.LinkedList
import java.util.Queue

fun Triple<Int, Int, Int>.addMinute(minute: Int = 1) = copy((first + ((second + minute) / 60)) % 24, (second + minute) % 60, third+ minute)
fun Triple<Int, Int, Int>.addHour(hour: Int = 1) = copy((first + hour) % 24, second, third+hour)

fun bfs(hour:Int, min: Int, nextHour: Int, nextMin: Int): Int{
    val q: Queue<Triple<Int, Int, Int>> = LinkedList()
    q.add(Triple(hour, min, 0))

    while (q.isNotEmpty()){
        val cur = q.poll()
        if(cur.first == nextHour && cur.second == nextMin) return cur.third

        if(cur.second != nextMin) q.add(cur.addMinute())
        else q.add(cur.addHour())
    }

    return -1
}

fun main() {
    val (hour, min) = readln().split(":").map { it.toInt() }
    val (nextHour, nextMin) = readln().split(":").map { it.toInt() }

    println(bfs(hour, min, nextHour, nextMin))
}