프로그래머스 N으로 표현 자바 풀이

문제 링크

문제 풀이 시간 : 1시간

문제 요약

숫자 N(1~9) 과 목표값 number(1~32,000) 가 주어짐
N과 사칙연산(+, -, ×, ÷) 및 괄호만을 사용하여 number를 만들어야 함
N을 이어붙인 수(예: 5, 55, 555 등) 도 사용할 수 있음
각 표현식에서 사용된 N의 개수를 계산하여
단, 나눗셈은 정수 나눗셈으로 처리
N을 8번 초과해 사용해야 하는 경우에는 -1을 반환

문제 풀이

이 문제는 처음에 보고 완전탐색밖에 생각이 나지 않았다.

하지만 문제의 분류가 dp라서 dp로 생각해보려 했지만 아무리 생각해도 풀이방법이 생각나지 않아

결국 풀이 방향성에 대한 힌트를 조금 보게 되었다.

결론부터 말하자면 완전탐색이 맞다!

하지만 dp와 결합된..

문제의 예시인 N=5, number=12인 경우를 보자면

1개를 사용한 경우
2개를 사용한 경우
3개를 사용한 경우

규칙이 보이는가?

3개를 사용한 경우에는 555를 제외하고는 1개를 사용한 경우와 2개를 사용한 경우를 조합하여 만들어진다!

이런 규칙을 인지한다면 문제는 아주 쉽게 풀린다!!

하지만 여기서 주의할 점은 더하기와 곱셈은 순서와 상관없이 결과가 동일하지만

빼기와 나눗셈은 순서에 따라 결과가 달라지기 때문에

같은 (5+5), 5를 조합하여 만든다고 하더라도 (5+5)-5, 5-(5+5)를 따로 계산해주어야 한다는 것이다.

처음에는 아래와 같이 코드를 작성했다.

초기 코드

java

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        int answer = 0;
        
        if(N==number)
            return 1;
        
        Set<Integer>[] dp = new HashSet[9];
        for(int i=1;i<9;i++){
            dp[i] = new HashSet<>();
        }
        
        dp[1].add(N);
        
        // 5,55,555와 같은 반복수 추가
        for(int i=2;i<=8;i++){
            int num = 0;
            for(int a=0;a<i;a++){
                num=num*10+N;
            }
            dp[i].add(num);
            
            //수 조합 생성
            for(int j=1;j<i;j++){
                int[] arr1 = dp[j].stream().mapToInt(Integer::intValue).toArray();
                int[] arr2 = dp[i-j].stream().mapToInt(Integer::intValue).toArray();
                
                for(int k=0;k<arr1.length;k++){
                    for(int l=0;l<arr2.length;l++){
                        dp[i].add(arr1[k]+arr2[l]);
                        dp[i].add(arr1[k]-arr2[l]);
                        dp[i].add(arr1[k]*arr2[l]);
                        dp[i].add(arr1[k]/arr2[l]);
                        dp[i].add(arr2[l]-arr1[k]);
                        dp[i].add(arr2[l]/arr1[k]);
                    }
                }
            }
            
            //nubmer가 포함된다면 i 리턴
            if(dp[i].contains(number)){
                answer = i;
                break;
            }
            //나눗셈 계산 오류 방지를 위한 0 제거
            dp[i].remove(0);
        }
        
        return answer==0?-1:answer;
    }
}

해당 코드도 물론 동작은 하고 통과는 하는 코드이다.

하지만 효율적이지 못한 코드라고 생각이 들어 몇가지를 수정하였다.

최종 코드

java

import java.util.*;

class Solution {
		//5, 55, 555와 같은 반복수 생성 함수
    public int repeat(int N, int i){
        int num = 0;
        for(int j=0;j<i;j++)
            num=num*10+N;
        return num;
    }
    
    public int solution(int N, int number) {
        int answer = -1;
        
        List<Set> dp = new ArrayList<>();
        for(int i=0;i<=8;i++){
            dp.add(new HashSet<Integer>());
        }
        
        for(int i=1;i<=8;i++){
            Set<Integer> cur = dp.get(i);
            
            cur.add(repeat(N,i));
            
            for(int j=1;j<i;j++){
		            //불필요한 배열로 변경하지 않고 Set 그대로 사용
                Set<Integer> A = dp.get(j);
                Set<Integer> B = dp.get(i-j);
                
                for(int a : A){
                    for(int b : B){
                        cur.add(a+b);
                        cur.add(a*b);
                        cur.add(a-b);
                        if(b!=0)
                            cur.add(a/b);
                    }
                }
            }
            
            if(cur.contains(number))
                return i;
        }
        
        return answer;
    }
}

계산 시 불필요한 배열 생성을 통한 메모리를 낭비를 막음
초기 코드에서는 a-b, b-a 를 동시에 계산했지만 어차피 j가 1부터 i-1까지 반복하면서 순차적으로 계산되기 때문에 불필요한 계산을 제외시켜주었다.
0을 따로 제거하기 보다는 나눗셈을 계산할 때, 분모가 0인지 체크해주는 방식으로 변경
new HashSet[] 은 제네릭 배열이라 문제가 있을 수 있어 List<Set<>> 형식으로 변경

N으로 표현

문제 풀이 시간 : 1시간

문제 요약

문제 풀이

초기 코드

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기