오늘의 문제 - 탐욕법(Greedy)
프로그래머스 - 마법의 엘리베이터
https://school.programmers.co.kr/learn/courses/30/lessons/148653
내 풀이 및 접근 방식
문제의 핵심은 가장 적은 수의 버튼으로 0층에 도달하는 방법을 선택하는 것이다.
자리수가 5보다 작은 수는 1 버튼만을 사용하여 0층에 도달하는 것, 5보다 큰 수는 거꾸로 10에 가까운 수로 만들고 다음 자리수에서 10을 빼는 것이 0층으로 가기 위한 최소값임을 파악해야한다. 그리고 자리수가 5인 경우에는 그 다음 자리수를 고려하는 것이 중요하다.
def solution(storey):
answer = 0
while storey > 0:
cur = storey % 10
if cur > 5:
answer += (10-cur)
storey += 10
elif cur < 5:
answer += cur
else:
if (storey // 10) % 10 > 4:
storey += 10
answer += cur
storey //= 10
return answer
풀이
- 현재 자리수 추출: 먼저, 현재 층수 storey의 마지막 자리수를 storey % 10을 통해 구한다. 이 값을 cur로 설정한다.
- 현재 자리수(cur)가 5보다 큰 경우:
- 만약 cur이 5보다 크다면, 예를 들어 6, 7, 8, 9 같은 숫자라면, 이 자리수를 10에 더 가깝게 만드는 것이 더 적은 마법의 돌을 사용할 수 있다.
- 이 경우 10 - cur만큼 마법의 돌을 사용해 현재 층수를 10에 가깝게 만들고, storey에 10을 더해 다음 자리수로 넘어간다.
- 현재 자리수(cur)가 5보다 작은 경우:
- cur이 0, 1, 2, 3, 4와 같이 5보다 작다면, 이 자리수를 0으로 만드는 것이 최적이다.
- 이 경우 cur만큼 마법의 돌을 사용하여 이 자리수를 0으로 만든다.
- 현재 자리수(cur)가 5인 경우:
- cur이 정확히 5인 경우, 다음 자리수를 확인한다.
- 다음 자리수가 5보다 크거나 같다면, storey에 10을 더하여 cur을 10에 가깝게 만든다. 그렇지 않다면, 현재 자리수를 cur만큼 마법의 돌을 사용하여 0으로 만든다.
- 자리수 이동:
- storey를 10으로 나누어 다음 자리수로 넘어간다.
- 위 과정을 storey가 0이 될 때까지 반복하며, 필요한 최소한의 마법의 돌 개수인 answer를 반환한다.
시간 복잡도
- 주어진 storey의 자리수 만큼 반복문을 수행하므로, 이 코드의 시간 복잡도는 O(log n)(n: storey값)이다.
- storey의 자리수는 최대 8자리(최대 100,000,000)까지 가능하므로, 최대 약 8번의 반복을 수행한다.
- 각 반복에서 수행하는 작업은 상수 시간(O(1))이다.
따라서, 최종 시간 복잡도는 O(log n)이다.
회고
각 자리수에서 가능한 최적의 결정을 구하는 그리디 문제였다. 이 문제를 풀기 위해서는 5보다 작은 경우, 5보다 큰 경우, 5인 경우와 같이 3가지 경우를 판단해야했는데 5인 경우를 고려하지 못해 계속해서 실패했다. 앞으로 더 꼼꼼히 여러가지 경우의 수를 찾도록 하자,,