Skip to main content

[Java] 340199 PCCE 9번 / 지폐 접기

1. 문제

프로그래머스 [Java] [PCCE 기출문제] 9번 / 지폐 접기

image.png

image.png

2. 오답

import java.util.Arrays;

class Solution {
    public int solution(int[] wallet, int[] bill) {
        int answer = 0;
        
        Arrays.sort(wallet);
        Arrays.sort(bill);
        
        // 지폐가 들어갈 때까지 반복
        while (bill[0] > wallet[0] || bill[1] > wallet[1]) {
            // 긴 쪽 반으로 접기
            if (bill[0] > bill[1]) {
                bill[0] /= 2;
            } else {
                bill[1] /= 2;
            }
            answer++;
        }
            
        return answer;
    }
}

image.png

지폐를 돌려서 넣는 경우를 반영하지 않아서 틀렸다.
지폐를 1번 접은 뒤 회전해서 지갑에 들어가는지 확인하는 로직을 추가해서 해결했다.

첫번째 케이스:

  • wallet = [30, 15]
  • bill = [26, 17]

인데 정렬하면

  • wallet = [15, 30]
  • bill = [17, 26]

while 조건을 보면, 17 > 15라서 무조건 접어야 한다고 판단하는데, 여기서 지폐를 회전하면 바로 들어간다.
처음에 쓴 코드는 회전 체크가 없어서 불필요하게 한번 더 접어서 기댓값이 1인데 2가 나왔다.

매 반복마다 회전 여부까지 포함해서 체크하는 코드를 while문 안에 한 줄 추가해서 해결

Arrays.sort(bill);

bill을 정렬해서 작은 값끼리, 큰 값끼리 비교만 하면 회전까지 고려 가능하다.


그래서 아래와 같이 코드 수정해서 통과되었다.

import java.util.Arrays;

class Solution {
    public int solution(int[] wallet, int[] bill) {
        int answer = 0;
        
        Arrays.sort(wallet);
        Arrays.sort(bill);
        
        // 지폐가 들어갈 때까지 반복
        while (bill[0] > wallet[0] || bill[1] > wallet[1]) {
            // 긴 쪽 반으로 접기
            if (bill[0] > bill[1]) {
                bill[0] /= 2;
            } else {
                bill[1] /= 2;
            }
            answer++;
            Arrays.sort(bill);
        }
            
        return answer;
    }
}

image.png

테스트 케이스가 제한적이라 통과했지만, 엄밀히 말하면 좋은 코드는 아니라고 한다.

정렬 위치 문제 때문이다.

  • 기존 코드에서는 Arrays.sort(bil)을 while문 진입 전에 한 번, while문 내부 끝에서 한번, 중복 2회 호출한다.
  • 이렇게 하면 처음부터 지폐를 회전에서 지갑에 넣을 수 있는 상황에서도 무조건 한 번 접고 확인을 시작한다.

3. 정답 코드

import java.util.Arrays;

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

        Arrays.sort(wallet); // 지갑 크기 오름차순 정렬

        while (true) {
            Arrays.sort(bill); // 지폐 크기 오름차순 정렬

            // 그대로 넣거나 회전해서 넣을 수 있으면 종료
            if ((bill[0] <= wallet[0] && bill[1] <= wallet[1]) ||
                (bill[0] <= wallet[1] && bill[1] <= wallet[0])) {
                break;
            }

            // 긴 쪽을 반으로 접기
            if (bill[0] >= bill[1]) {
                bill[0] /= 2;
            } else {
                bill[1] /= 2;
            }
            answer++;
        }

        return answer;
    }
}

수정 내역

  • Arrays.sort(bill); 위치를 while문 내부 맨 위로 옮겨서, 매 반복마다 길이를 정렬한 상태에서 회전 가능 여부를 먼저 확인한다.
  • 만약 회전 똔느 그대로 넣을 수 있으면 break로 반복을 종료한다.
  • 이렇게 하면 처음부터 불필요하게 접는 상황이 사라지고, 중복된 정렬 호출도 없어진다.


Back to top