[오늘의 문제] 지폐 접기

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

민수는 다양한 지폐를 수집하는 취미를 가지고 있습니다. 지폐마다 크기가 달라 지갑에 넣으려면 여러 번 접어서 넣어야 합니다. 예를 들어 지갑의 크기가 30 15이고 지폐의 크기가 26 17이라면 한번 반으로 접어 13 * 17 크기로 만든 뒤 90도 돌려서 지갑에 넣을 수 있습니다. 지폐를 접을 때는 다음과 같은 규칙을 지킵니다.

지폐를 접을 때는 항상 길이가 긴 쪽을 반으로 접습니다.
접기 전 길이가 홀수였다면 접은 후 소수점 이하는 버립니다.
접힌 지폐를 그대로 또는 90도 돌려서 지갑에 넣을 수 있다면 그만 접습니다.
지갑의 가로, 세로 크기를 담은 정수 리스트 wallet과 지폐의 가로, 세로 크기를 담은 정수 리스트 bill가 주어질 때, 지갑에 넣기 위해서 지폐를 최소 몇 번 접어야 하는지 return하도록 solution함수를 완성해 주세요.

지폐를 지갑에 넣기 위해 접어야 하는 최소 횟수를 구하는 과정은 다음과 같습니다.

1. 지폐를 접은 횟수를 저장할 정수 변수 answer를 만들고 0을 저장합니다.
2. 반복문을 이용해 bill의 작은 값이 wallet의 작은 값 보다 크거나 bill의 큰 값이 wallet의 큰 값 보다 큰 동안 아래 과정을 반복합니다.
   2-1. bill[0]이 bill[1]보다 크다면
   bill[0]을 2로 나누고 나머지는 버립니다.
   2-2. 그렇지 않다면
   bill[1]을 2로 나누고 나머지는 버립니다.
   2-3. answer을 1 증가시킵니다.
3. answer을 return합니다.
   위의 의사코드와 작동방식이 다른 코드를 작성해도 상관없습니다.
   제한사항
   wallet의 길이 = bill의 길이 = 2
   10 ≤ wallet[0], wallet[1] ≤ 100
   10 ≤ bill[0], bill[1] ≤ 2,000
   입출력 예
   wallet bill result
   [30, 15][26, 17] 1
   [50, 50][100, 241] 4
   입출력 예 설명
   입출력 예 #1

지문과 동일합니다.
입출력 예 #2

지폐를 접으면 다음과 같이 크기가 줄어듭니다. 따라서 4번 접으면 지갑에 넣을 수 있습니다.
[100, 241] -> [100, 120] -> [100, 60] -> [50, 60] -> [50, 30]
cpp를 응시하는 경우 리스트는 배열과 동일한 의미이니 풀이에 참고해주세요.
ex) 번호가 담긴 정수 리스트 numbers가 주어집니다. => 번호가 담긴 정수 배열 numbers가 주어집니다.
java를 응시하는 경우 리스트는 배열, 함수는 메소드와 동일한 의미이니 풀이에 참고해주세요.
ex) solution 함수가 올바르게 작동하도록 한 줄을 수정해 주세요. => solution 메소드가 올바르게 작동하도록 한 줄을 수정해 주세요.

30분 이내로 작성 한 코드다.

class Solution {
public int solution(int[] wallet, int[] bill) {
int answer = 0;
// 지폐를 접을 때는 항상 길이가 긴 쪽을 반으로 접습니다.
// 접기 전 길이가 홀수였다면 접은 후 소수점 이하는 버립니다.
// 접힌 지폐를 그대로 또는 90도 돌려서 지갑에 넣을 수 있다면 그만 접습니다.
// 반복문을 이용해 bill의 작은 값이 wallet의 작은 값 보다 크거나 bill의 큰 값이 wallet의 큰 값 보다 큰 동안 아래 과정을 반복합니다.
int maxWallet = 0;// 지갑 원소 최댓값
int minWallet = 0;// 최솟값
if(wallet[0] > wallet[1]){
maxWallet = wallet[0];
minWallet = wallet[1];
} else {
maxWallet = wallet[1];
minWallet = wallet[0];
}

    for(int j = 0; j < bill.length; j++){// wallet 원소 큰 숫자도 비교 해야 함
        if(bill[0] > bill[1]){
            bill[0] = bill[0] / 2;// bill[0]을 2로 나누고 나머지는 버립니다.
            if(bill[1] > minWallet || bill[0] > maxWallet){
                // bill의 작은 값이 wallet의 작은 값 보다 크거나 bill의 큰 값이 wallet의 큰 값 보다 큰 동안 아래 과정을 반복합니다.
                continue;
            }
        } else {// 그렇지 않다면
            bill[1] = bill[1] / 2;// bill[1]을 2로 나누고 나머지는 버립니다.
            if(bill[0] > minWallet || bill[1] > maxWallet){
                // bill의 작은 값이 wallet의 작은 값 보다 크거나 bill의 큰 값이 wallet의 큰 값 보다 큰 동안 아래 과정을 반복합니다.
                continue;
            }
        }
        answer++;// answer을 1 증가시킵니다.  
    }


    return answer;
}

}

이렇게 하니

케이스1만 통과가 되었고, 제출 후 채점하기를 눌러보니 0점이 떴다..

테스트 1
입력값 〉 [30, 15], [26, 17]
기댓값 〉 1
실행 결과 〉 테스트를 통과하였습니다.
테스트 2
입력값 〉 [50, 50], [100, 241]
기댓값 〉 4
실행 결과 〉 실행한 결괏값 0이 기댓값 4과 다릅니다.

wallet 가로 세로 길이가 같은 경우는 생각 못했다.

지갑과 지폐의 가로세로가 같은 경우나, 회전 가능한 경우를 적절히 고려하지 못한 부분도 있었다.

우선, 지갑과 지폐 배열 원소를 항상 오름차순으로 정렬하게끔 해야 편하다.

// wallet을 항상 오름차순으로 정렬
int w1 = Math.min(wallet[0], wallet[1]);
int w2 = Math.max(wallet[0], wallet[1]);

int b1 = Math.min(bill[0], bill[1]);
int b2 = Math.max(bill[0], bill[1]);

이렇게 큰갑 작은값을 변수에 저장시킨다면 편하다.

또한, 반복문도 필요가 없는게, 항상 배열원소는 두개 밖에없으니..

우선, 이두가지 요구사항을 고려하여 다시 코드문을 작성해봤다.

class Solution {
public int solution(int[] wallet, int[] bill) {
int answer = 0;

    int w1 = Math.min(wallet[0], wallet[1]);
    int w2 = Math.max(wallet[0], wallet[1]);

    int b1 = Math.min(bill[0], bill[1]);
    int b2 = Math.max(bill[0], bill[1]);

    
    while(true){
        
        // bill의 작은 값이 wallet의 작은 값 보다 크거나 bill의 큰 값이 wallet의 큰 값 보다 큰 동안 아래 과정을 반복합니다.
        
        if(b1 > b2){
            b1 = b1 / 2;// bill[0]을 2로 나누고 나머지는 버립니다.
        } else {// 그렇지 않다면
            b2 = b2 / 2;// bill[1]을 2로 나누고 나머지는 버립니다.
        }
        answer++;// answer을 1 증가시킵니다.  
    }

    return answer;
}

}

여기서 bill의 작은 값이 wallet의 작은 값 보다 크거나 bill의 큰 값이 wallet의 큰 값 보다 큰 동안 아래 과정을 반복합니다.

이 요구사항의 반대일 경우 while문을 탈출하게 한다.

최종 코드문
class Solution {
public int solution(int[] wallet, int[] bill) {
int answer = 0;

    int w1 = Math.min(wallet[0], wallet[1]);
    int w2 = Math.max(wallet[0], wallet[1]);

    int b1 = Math.min(bill[0], bill[1]);
    int b2 = Math.max(bill[0], bill[1]);

    while(true){
        // bill의 작은 값이 wallet의 작은 값 보다 크거나 bill의 큰 값이 wallet의 큰 값 보다 큰 동안 아래 과정을 반복합니다.
        if((b1 <= w1 && b2 <= w2) || (b1 <= w2 && b2 <= w1)){
            break;
        }

        if(b1 > b2){
            b1 = b1 / 2;// bill[0]을 2로 나누고 나머지는 버립니다.
        } else {// 그렇지 않다면
            b2 = b2 / 2;// bill[1]을 2로 나누고 나머지는 버립니다.
        }
        answer++;// answer을 1 증가시킵니다.  
    }

    return answer;
}

}