🔎 문제
민수는 다양한 지폐를 수집한다.
지폐마다 크기가 달라 지갑에 넣기 위해 여러 번 접어야 한다.
접는 규칙은 다음과 같다:
1. 항상 긴 변을 반으로 접는다
2. 접기 전 길이가 홀수라면, 접은 뒤 소수점 이하는 버린다
3. 접힌 지폐를 그대로 또는 90도 회전해서 지갑에 넣을 수 있으면 종료
지갑의 크기 wallet = [w, h]
지폐의 크기 bill = [w, h]
지갑에 넣기 위해 최소 몇 번 접어야 하는지 구하는 문제다.
⸻
이 문제는 사실 세 가지 포인트만 이해하면 끝난다.
- 항상 긴 변을 접는다
즉, 매 단계에서 큰 쪽을 // 2 하면 된다.
⸻
- 90도 회전이 가능하다
이 조건 때문에 사고를 단순화할 수 있다.
회전이 가능하다는 것은
결국 작은 변끼리, 큰 변끼리 비교하면 된다는 뜻이다.
그래서 두 리스트를 정렬해두면:
wallet = sorted(wallet)
bill = sorted(bill)이렇게 놓고,
• bill[0] <= wallet[0]
• bill[1] <= wallet[1]이 둘을 동시에 만족하면 종료다.
⸻
- 둘 중 하나라도 크면 계속 접어야 한다
그래서 while 조건은 다음처럼 된다:
while wallet[0] < bill[0] or wallet[1] < bill[1]:둘 중 하나라도 지갑보다 크면 더 접어야 한다.
⸻
우당탕탕 첫 번째 풀이
def solution(wallet, bill):
answer = 0
wallet = sorted(wallet)
bill = sorted(bill)
while (wallet[0] < bill[0]) or (wallet[1] < bill[1]):
bill[1] = bill[1] // 2
bill = sorted(bill)
answer += 1
return answer동작 방식
• 매 반복마다 긴 변(bill[1])을 반으로 줄인다.
• 다시 정렬해서 긴/짧은 변 관계를 유지한다.
• 둘 다 지갑보다 작아질 때까지 반복한다.
구현은 단순하고 직관적이다.
⸻
추가 최적화 — sort 제거
생각해보니 원소는 2개뿐이다.
굳이 매번 sorted()를 호출할 필요가 없다.
긴 변을 줄인 뒤, 필요하면 swap만 해주면 된다.
def solution(wallet, bill):
w0, w1 = sorted(wallet)
b0, b1 = sorted(bill)
ans = 0
while b0 > w0 or b1 > w1:
b1 //= 2 # 항상 큰 변을 반으로
if b0 > b1: # 정렬 대신 swap
b0, b1 = b1, b0
ans += 1
return ans차이점
• sorted() 호출 제거
• 상수 시간 swap으로 대체
• 로직은 동일
엄청난 시간복잡도 차이는 없지만,
불필요한 연산을 제거한 더 깔끔한 구현이다.
막힘없이 푼 문제라 블로그에 안쓰려 했는데, 답을 맞추고 나서 추가 최적화를 하면서 sort에 치중된 내 사고를 고칠 수 있는 계기가 된듯해서 나름 뿌듯
