[프로그래머스/JAVA] 지폐 접기

목차 (OPEN)

• 🔗 문제 바로가기
• 📌 문제 요약
• 💡 아이디어
• 👩🏻‍💻 최종 코드
• 🕑 시간 복잡도

 

 

 

🔗 문제 바로가기

https://school.programmers.co.kr/learn/courses/30/lessons/340199

프로그래머스

 

---

📌 문제 요약

 

민수는 다양한 크기의 지폐를 수집하며, 지갑에 넣기 위해 지폐를 여러 번 반으로 접어야 한다.

이때, 아래의 규칙을 따라서 접어야 한다.

 

• 항상 더 긴 쪽을 반으로 접는다.
• 홀수인 경우, 반으로 접을 때 생긴 소수점 이하는 버린다.
• 지폐를 90도 회전시켜도 된다.
  →  즉, bill의 (가로, 세로)나 (세로, 가로)중 하나라도 지갑 크기 이하가 되면 넣을 수 있다.
• 접어야 하는 최소 횟수를 구해야 한다.

 

---

💡 아이디어

이 문제는 아이디어라고 할 것도 없는게, 문제에서 어떻게 풀어야 하는지를 알려줘서 코드로 옮기기만 하면 된다 😓

 

그래도 한 번 설명하자면 아래와 같다.

 

1️⃣ 지폐의 크기가 지갑보다 큰지 확인하기

돌려서 넣어도 상관 없으니,

단순히 지갑의 긴 쪽이 지폐의 긴 쪽보다 크고, 지갑의 짧은 쪽이 지갑의 짧은 쪽보다 크기만 하면

우리는 해당 지폐를 지갑에 넣을 수 있다.

 

따라서 아래와 같이 반복문의 조건을 설정해주었다.

Math.min(bill_width, bill_height) > Math.min(wallet_width, wallet_height) || Math.max(bill_width, bill_height) > Math.max(wallet_width, wallet_height))

 

 

2️⃣ 지갑보다 지폐가 크다면, 지폐를 반으로 접어주기

만약 반복문 조건 검사에서 실패했다면 (지폐가 지갑보다 크다면),

지폐의 긴 쪽을 찾아서 반으로 접어주면 된다.

if(bill_width > bill_height){
    bill_width /= 2;
}
else{
    bill_height /= 2;
}

 

 

3️⃣ 조건에 걸려서 지폐 접기를 수행했다면, 접은 횟수에 1씩 더하기

while문을 돌았다는 말은,

지폐가 지갑의 크기보다 커서 반으로 접는 과정을 한 번 수행했다는 의미니까

answer에다가 1을 더해주면 된다.

 

---

👩🏻‍💻 최종 코드

 

class Solution {
    public int solution(int[] wallet, int[] bill) {
        int wallet_height = wallet [1];
        int wallet_width = wallet[0];
        
        int bill_width = bill[0];
        int bill_height = bill[1];
        
        int answer = 0;
        
        while(Math.min(bill_width, bill_height) > Math.min(wallet_width, wallet_height) || Math.max(bill_width, bill_height) > Math.max(wallet_width, wallet_height)){
            if(bill_width > bill_height){
                bill_width /= 2;
            }
            else{
                bill_height /= 2;
            }
            answer++;
        }
        
        return answer;
    }
}

 

---

🕑 시간 복잡도

🔁 반복의 최대 횟수

지폐의 길이는 최대 2000인데,

매번 더 긴 쪽을 절반으로 줄이므로, 각 변은 로그 스케일로 줄어든다.

 

즉, 어떤 길이 L이 있다고 할 때,

L → L/2 → L/4 → ... → 1이 되기까지 log2(L)번 이하로 접는다.

 

따라서 최대 지폐의 크기 2000을 기준으로

log2(2000) ≈ 11 이므로,

최대 약 11번 접으면 지폐의 크기는 무조건 1 이하가 된다.

 

 

✅ 최종 시간 복잡도

• 한 번 접을 때마다 지폐가 지갑에 들어갈 수 있는지 확인 → 상수 시간 O(1)
• 최대 접는 횟수는 log2(max(bill 크기)) ≈ 11

따라서 전체 시간 복잡도는, O(log2(bill의 최대 길이))라고 볼 수 있다. 

 

👉🏻 즉, 최종 시간 복잡도는 O(logN)이다.