[프로그래머스] N으로 표현-JAVA

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

 

Dynamic Programming(동적 계획법)을 이용하여 풀었다.

 

풀이 방식

 

개인적으로 로직을 짜기 제일 까다로웠던 문제중 하나였던 것 같다.

필자는 이 문제를 'N을 사용한 횟수'를 기준으로 나눠 풀이하였다.

즉 N이 5라면, 5를 1번, 2번, 3번...8번(문제 조건에 8보다 크면 -1리턴이기 떄문)사용해서 만들 수 있는 숫자들의 경우로 나눈 것이다.

 

박스가 8개 있다고 해보자.

1번 박스에는 N을 1번 사용해서 만들 수 있는 숫자들이 담겨있다.

N = 5라고 한다면

1번 박스에는 5만 담겨있을 것이다.

2번 박스에서는 어떨까?

5 + 5 , 5 - 5, 5 * 5, 5 / 5, 55   의 경우가 있을 것이다.

즉, 작게 나눠서 생각해본다면, 2번 박스에는 사칙연산(더하기, 빼기, 곱하기, 나누기) 과 N 2개를 사용해서 만들 수 있다.

 

그렇다면 3번 박스는?

5 + 5 + 5,  5 - 5 - 5, 5 * 5 * 5..... 등 일일히 셀 수 가 없는 경우가 나오기 시작한다.

DP는 큰 문제를 작은 단위로 나누는 방식이다. 그렇다면 3번 박스를 어떻게 나눌 수 있을까?

바로 1번 박스와 2번 박스를 합치는 방법이다.

그림과 함께 보자.

 

3개는 (1 + 2) 이므로 1개로 만들수 있는 경우와, 2개로 만들수 있는 경우를 서로 사칙연산해주면 모든 경우가 나올 수 있다.

즉, 박스 1의 원소 5와, 박스 2의 원소 5가지(5+5, 5-5, 5*5, 5/5, 55)를 서로 더하고, 빼고, 나누고, 곱한 모든 경우의 수가 박스 3에 들어가는 것이다.

다만 주의해야 할 점은 (1 + 2)와 (2 + 1)이다. 해당 문제에서는 괄호연산이 가능하기 때문에 5 + 5 * 5와 (5 + 5) * 5가 다르기 때문에 둘의 연산을 반대로 하는 경우도 신경써줘야 한다.

박스 4의 경우는 (1 + 3) (3 + 1) (2 + 2)의 경우와 5555 <- 4번 연속의 5 숫자까지 넣어주면 된다.

이런 방식대로 박스 8까지 모두 만들어준 후, 각 통마다 number와 일치하는 결과값을 count해주면 된다.

 

다시 로직을 간단하게 정리해보자

1. 숫자 N의 개수별로 만들수 있는 박스를 1~8까지 만든다.

2. 박스 숫자가 n인 경우, 더해서 n이 되는 두 숫자의 박스값을 이용해 박스를 채워준다. (ex. 5인 경우 1+5 2+3 3+2 5+1)

3. 각 박스마다 연속된 숫자를 잊지 말고 넣어준다.

4. 각 박스마다 중복된 값이 들어가지 않도록 박스는 Set자료구조를 사용한다.

 

여기서 중요한 부분은 괄호연산때문에 1 + 2와 2 + 1을 둘 다 구해주고, 연속된 숫자(555 등..)를 박스별로 넣어줘야 한다. 또한 박스에 중복된 연산값이 들어가지 않도록 Set 자료구조를 이용해야한다.

 

코드 풀이

 

import java.util.HashSet;
import java.util.Set;
import java.util.ArrayList;
import java.util.List;
class Solution {
    //순서쌍 a에 b 합치기
    public void unionSet(Set<Integer> union, Set<Integer> a, Set<Integer> b) {
        for (int n1 : a) {
            for (int n2 : b) {
                union.add(n1 + n2);
                union.add(n1 - n2);
                union.add(n1 * n2);
                if (n2 != 0)
                    union.add(n1 / n2);
            }
        }
    }
    public int solution(int N, int number) {
        List<Set<Integer>> setList = new ArrayList<>();
        
        for (int i = 0; i < 9; i++)
            setList.add(new HashSet<>()); // 개수 별 해쉬셋
        setList.get(1).add(N); //1개로 만들 수 있는 건 나 자신뿐
        if (number == N)
            return 1;
        for (int i = 2; i < 9; i++) {
            for (int j = 1; j <= i / 2; j++) {
                unionSet(setList.get(i), setList.get(i - j), setList.get(j));
                unionSet(setList.get(i), setList.get(j), setList.get(i - j));
            }
            String n = Integer.toString(N);
            setList.get(i).add(Integer.parseInt(n.repeat(i))); //연속된 숫자 넣기
            for (int num : setList.get(i))
                if (num == number)
                    return i;
        }
        return -1;
    }
}

unionSet함수는 N이 3인경우 (1 + 2) (2 + 1)을 해주어 1번 박스와 2번 박스를 사칙연산한 결과를 넣어주는 메소드다. 즉, 박스인 Set을 List에 담아 8개의 Set(박스)가 담긴 리스트를 만들어 로직을 수행하는 것이다.

 

로직에 대해 한참 생각했던 문제..