Today's Algorithm(2018-11-04)

programmers N으로 표현

사람들이 많이 못 푼 문제 중 하나라 어려울거라 생각했지만 정말 해법이 떠오르지 않더라구요. 약 40분 정도 고민을 했는데 도저히 방법이 떠오르지 않아 다른 사람의 풀이를 참고하였습니다. 그 이전에 제가 생각했던 아이디어랑 이 아이디어의 문제도 같이 기록해볼게요.

 

분명 문제 분류에서 말하듯이 '동적계획법'을 사용하는 문제입니다. '동적계획법'은 말 자체는 어려우나 그냥 한 마디로 '그 이전에 계산한 부분 계산을 이용하여 더 큰 계산을 해결한다'입니다. 이렇게 사용하기 위해선 컨셉을 잘 잡아야합니다. 그 이전의 부분계산을 어떻게 설정하느냐에 따라서 문제를 쉽게 해결할 수도 있고 더 미궁으로 빠져들 수도 있죠.

 

저의 경우 처음에 이렇게 설정하였습니다.

d[N의 자리수][사칙 연산] // 기존 수에 다음과 같은 연산을 했을 때 전체 N의 개수
n[N의 자리수][사칙 연산] // 기존 수에 다음과 같은 연산을 했을 때 수

이렇게 하면 문제점은 기존 수에 오게될 수를 어떻게 설정하냐는 것입니다. 차례대로 계산한다면 모르겠지만 3자리 수가 올수도 있고 5자리 수가 올수도 있는데 어떻게 받을 수 있을까 하는 고민이 생겼습니다. 그래서 다음과 같이 바꿔보았습니다.

d[N의 앞자리수][사칙연산][N의 뒷자리수]  

이렇게 하면 앞자리수랑 뒷자리수를 다 고려할 수 있을거라 생각했습니다. 그런데 3차원 배열로 푸는 건 너무 복잡할 것 같고 사실 계산도 어떻게 해야할지 방법이 떠오르지 않아 이쯤에서 다른 사람의 풀이를 보기로 결정하였습니다.

 

다른 사람들의 풀이는 다들 참 길었는데요. 눈에 띄게 짧고 깔끔한 코드가 하나 있었습니다. 다음 코드입니다.

class Solution {
    public int solution(int N, int number) {
        int answer = -1;  // 최소값이 8보다 크면 -1 처리
        Set<Integer>[] setArr = new Set[9];
        int t = N;
        for (int i = 1; i < 9; i++) {
            setArr[i] = new HashSet<>();
            setArr[i].add(t);
            t = t * 10 + N;
        }
        for (int i = 1; i < 9; i++) {  // 전체 자리
            for (int j = 1; j < i; j++) {
                for (Integer a : setArr[j]) {  // 앞에 자리
                    for (Integer b : setArr[i - j]) {  // 뒤에 자리
                        setArr[i].add(a + b);
                        setArr[i].add(a - b);
                        setArr[i].add(b - a);
                        setArr[i].add(a * b);
                        if (b != 0) {
                            setArr[i].add(a / b);
                        }
                        if (a != 0) {
                            setArr[i].add(b / a);
                        }
                    }
                }
            }
        }
        for (int i = 1; i < 9; i++) {
            if (setArr[i].contains(number)) {
                answer = i;
                break;
            }
        }
        return answer;
    }
}

이 코드를 보면 제가 고민했던 내용을 한번에 다 해결하고 있습니다. 이 코드를 보면서 가장 잘 짰다고 느꼈던 부분은 11줄에서 전체 자리를 설정하는 부분과 값을 Set으로 처리한 것입니다.

먼저 전체 자리를 설정한 부분을 살펴봅시다. 문제에 최솟값이 8보다 크면 -1 처리하라고 되어있는데요. 그렇기 때문에 전체 자리를 9보다 작게 일단 먼저 설정하는 것입니다. 그렇기 때문에 맨 처음에 setArr에 N자리 수 넣는 과정에서도 9자리보다 작은 수까지만 만들고 있는 것을 볼 수 있습니다.

다음은 Set로 처리하는 부분을 봅시다. 각 전체자리에 따른 Set이 만들어져 있는데요. 우선 전체자리를 for문 제일 밖에서 둘러 싸고 그 안에서 그 보다 작은 수를 하나를 선택하여 앞의 자리와 뒤의 자리를 고릅니다. 참 이 아이디어가 기똥찬데요. 그리곤 앞의 자리와 뒤의 자리가 만들어 낼 수 있는 수의 조합을 모두 Set에 집어넣습니다. 그리곤 제일 마지막에 각 N의 자리 Set 조사하여 우리가 구하고자 하는 수가 있는지 contains()메서드를 이용하여 찾는 것이죠.

 

역시 똑똑한 사람들은 참 많네요. 오늘도 한 수 배웁니다. 이 문제는 이후에 다시 도전해봐야겠습니다!