프로그래머스 : 마법의 엘리베이터 (Kotlin)
문제
문제 확인하기
풀이
storey 층에서 0층으로 내려가야 한다.
내려가는 방법은 -10^c or +10^c (c >= 0) 중에서 선택해야 한다.
우선 storey로 한 자리 숫자가 주어졌을 때를 생각해보자.
3이 주어졌다고 할 때 단순히 -1 버튼을 3번 눌러서 0층으로 가는 것이 가장 빠르다.
7이 주어졌다고 해보자.
이 때는 -1을 7번 누르는 것 보다 +1을 3번 눌러서 10층으로 이동하고 -10 버튼을 눌러 0층으로 가는 것이 가장 빠르다.
5가 주어지면 어떨까?
5가 +1을 5번 누르고 -10을 한 번 누르는 것 보다는 단순히 -1을 5번 누르는 것이 더 빠르게 이동할 수 있다.
이번에는 storey가 두 자리 숫자가 주어졌을 때를 생각해보겠다.
13이 주어진다면 -1을 3번, -10을 한번 누르는 것이 가장 빠르다.
17이 주어진다면 -1을 7번 누르는 경우보다 +1을 3번, -10을 2번 누르는 경우가 더 빠르다.
각각 45와 55, 65가 주어진 경우를 생각해보자.
45가 주어진다면 -1을 5번, -10을 4번 누르는 경우가 총 9번 누르게 되어 가장 빠르다.
55가 주어진다면 -1을 5번, -10을 5번, 총 10번으로 이동 가능하고 또 다른 방법으로 +1을 5번, +10을 4번, -100을 1번 눌러 총 10번으로 이동하는 경우가 있다.
65가 주어진다면 +1을 5번, +10을 3번, -100을 1번 눌러 총 9번만 눌러서 0층으로 갈 수 있다.
즉, i번째 자릿수가 5이면 i+1번째 자릿수의 값에 따라 올라갈지 내려갈지 정해야 한다.
위 내용을 확인해보면 i+1번째 자릿수가 4 이하이면 - 버튼으로 내려가면 되고, 6 이상이면 + 버튼을 통해 올라가는 것이 빠르다.
그럼 i+1번째 자릿수가 5일 경우가 남는데, 이 때는 올라가든 내려가든 동일했기 때문에 아무 경우나 하나를 골라 선택하면 된다.
여기서 알고리즘을 도출할 수 있다.
- 1의 자릿수부터 마지막 자릿수까지 차례로 확인하여 아래 내용을 반복한다.
- 현재 확인중인 자릿수를
i라고 한다. i번째 자릿수의 값(k)에 따라 아래 내용을 수행한다.
k가 5보다 작으면, -10^(i-1) 버튼을 k번 눌러 내려간다.k가 5보다 크면, +10^(i-1) 버튼을 10 - k번 눌러 올라간다. 이 때, 다음 자릿수의 값이 1 증가한다.k가 5이면, 다시 아래 내용 중 하나를 선택해서 수행한다.
i+1번째 자릿수의 값(j)이 4 이하이면, -10^(i-1) 버튼을 k번 눌러 내려간다.i+1번째 자릿수의 값(j)이 5 이상이면, +10^(i-1) 버튼을 10 - k번 눌러 올라간다.
여기서 주의할 점은 storey의 자릿수 만큼 반복을 수행했다면, storey의 마지막 자릿수에서 자릿수 올림이 발생했는지의 여부이다.
만약 98765가 storey로 주어졌을 때, 총 자릿수의 갯수는 5개이다.
위 알고리즘을 통해 5번 반복수행 했다고 하자.
위 알고리즘을 이용하면 마지막 자릿수 9에서 자릿수 올림이 발생한다.
그럼 알고리즘 수행을 마쳤을 때 현재 위치한 층은 100000가 되어 0층으로 이동하지 않은 상태가 된다.
이 경우 -100000 버튼을 한번 눌러 0층으로 갈 수 있기 때문에 알고리즘 수행을 마쳤을 당시 총 버튼을 누른 횟수 + 1을 결과로 반환하면 된다.
아래는 해당 내용을 코틀린을 사용해서 작성한 코드이다.
class MagicElevator {
fun solution(storey: Int): Int {
// 총 버튼을 누른 횟수
var answer = 0
var remainStorey = storey
// 자릿수
val digitCount = remainStorey.toString().length
// 자릿수 만큼 진행
for (i in 1 .. digitCount) {
// 10^(i-1)의 자릿수 값
val digitNum = getDigitNumberFrom(digitAt = i, num = remainStorey)
// 자릿수의 값이 5보다 크면 +10^(i-1) 버튼을 통해 올라간다.
if (digitNum > 5) {
remainStorey += makeDigitNumber(digit = i, num = 10 - digitNum)
answer += (10 - digitNum)
}
// 자릿수의 값이 5보다 작으면 -10^(i-1) 버튼을 통해 내려간다.
else if (digitNum < 5) {
remainStorey -= makeDigitNumber(digit = i, num = digitNum)
answer += digitNum
}
// 자릿수의 값이 5이면 다음 자릿수를 확인한다.
else {
// 다음 자릿수가 없으면 -10^(i-1) 버튼을 통해 내려간다.
if (i + 1 > digitCount) {
remainStorey -= makeDigitNumber(digit = i, num = digitNum)
answer += digitNum
} else {
// 다음 자릿수
val nextDigitNumber = getDigitNumberFrom(num = remainStorey, digitAt = i + 1)
// 다음 자릿수가 4 이하이면 -10^(i-1) 버튼을 통해 내려간다.
if (nextDigitNumber <= 4) {
remainStorey -= makeDigitNumber(digit = i, num = digitNum)
answer += digitNum
}
// 다음 자릿수가 5 이상이면 +10^(i-1) 버튼을 통해 내려간다.
else {
remainStorey += makeDigitNumber(digit = i, num = 10 - digitNum)
answer += (10 - digitNum)
}
}
}
}
// 기존 storey 의 가장 큰 자릿수에서 자릿수가 하나 더 생겼을 경우
// ex) 9 -> 10이 된 경우, -10 버튼을 눌러줘야 한다.
if (remainStorey != 0 && remainStorey % 10 == 0) answer++;
return answer
}
// num * 10^(digit-1) 값 생성
private fun makeDigitNumber(digit: Int, num: Int) = ((10).toDouble().pow(digit - 1) * num).toInt()
// num 에서 digitAt 번째 자릿수 값 꺼냄
private fun getDigitNumberFrom(num: Int, digitAt: Int): Int = ((num / (10).toDouble().pow(digitAt - 1)) % 10).toInt()
}