프로그래머스 | N으로 표현 - java

프로그래머스

 

# 핵심

Set을 활용하자!!

 

..

 

또 결국 혼자 못풀었다....

 

진짜 다 된 것 같았는데 접근 방식이 조금 잘못됐었다.

내 생각으로는 

 

이런 그림처럼 BFS같이 최단 거리를 보장하는 것 같은 방식을 사용하면 되지 않을까? 싶었는데 아쉽게도 이게 아니었다.

이런 느낌으로 푸는 DP 문제가 이전에 있었던 것 같았는데,, 순간이동 문제였나? 아무튼

 

이 방식에서 어디가 잘못되었길래 문제를 풀 수 없는 것일까??

내가 생각한 방식은 1레벨(5)에 N을 사칙연산 해서 4종류의 2레벨 원소(1,0,10,25) 그리고 N을 2번 이어붙인 55, 총 5가지를 만들어낸다

 

그리고 3레벨은 2레벨 원소 각각에 1레벨 원소를 사칙연산 해서 만들어낸다. 여기까지는 운이 좋게 잘 되는 것 같아 보인다.

 

근데 4레벨을 만들어 낸다면 어떻게 될까

3레벨 + 1레벨 해서 4레벨을 하나 만들어 낼 수 있는데, 이 뿐만 아니라 2레벨 + 2레벨, 1레벨 + 3레벨 원소들의 사칙연산으로도 4레벨 원소를 만들어낼 수 있다!!!

(3레벨 + 1레벨의 결과와 1레벨 + 3레벨의 결과는 다르다!!!)

 

그니까 내가 생각한 알고리즘은 3레벨 + 1레벨 = 4레벨 단 한가지 방식밖에 적용이 안되니 당연히 틀렸다고 나오는 것이었다.

 

5레벨을 만들 때에도

4 + 1 레벨 뿐만 아니라 3 + 2, 2 + 3, 1 + 4 총 4가지 경우의 수를 모두 고려해야 하는 것이다.

 

이렇게 다 하면 경우의 수가 너무 많아지는것 아닌가? 싶은 생각이 들 수 있는데, 해당 문제에서는 이를 고려해 최솟값이 8을 넘는 경우에는 -1을 리턴하라고 했다. 진짜 괜히 이런 말을 넣어놓은게 아니다. 이런걸 잘 캐치하는 것도 중요해보인다.

 

 

그럼 구현은 어떻게 할 수 있을까??

 

각 레벨별 원소를 Set에 담아놓고 이중 반복문을 돌면서 연산을 하면 된다!

위 그림을 고치면 대충 이렇게 생겨먹었다고 보면 될 것 같다.

 

그림이 크게 달라지지는 않은 것 처럼 보이는데 가장 중요한 것은 레벨별 원소를 Set에 담아놓고, 새로운 Set을 만들 때 이중 반복문을 돌면서 원소간 사칙연산을 돌린다는 것이다.

 

* 55, 555와 같이 N을 레벨 만큼 이어붙여 만든것은 사칙연산을 통해 나오는 것이 아니기 때문에 직접 넣어줘야 한다.

* 2레벨 Set(이전 레벨 셋)에 있던 원소가 연산에 따라 3레벨 Set(새로운 레벨 셋)에 또다시 나올 수 있다. 하지만 낮은 레벨부터 탐색하다가 제일 먼저 특정 원소를 발견한 Set에서 중단하면 되기 때문에 이는 큰 문제가 되지 않는다.

또한 Set의 특성상 같은 Set에 중복 원소는 들어가지 않기 때문에 불필요한 중복 탐색을 줄일 수 있다. 

 

# 통과 코드

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        List<Set<Integer>> setList = new ArrayList<>();
        for(int i = 0; i <= 8; i++) {
            setList.add(new HashSet<>());
        }
        // 1회
        setList.get(1).add(N);

        StringBuilder sb = new StringBuilder();
        sb.append(N);

        // 2회 이상
        for(int i = 2; i < setList.size(); i++) {
            sb.append(N);
            Set<Integer> newSet = setList.get(i);
            newSet.add(Integer.parseInt(sb.toString()));

            for(int j = 1; j <= i; j++) {
                Set<Integer> setA = setList.get(j);
                Set<Integer> setB = setList.get(i - j);

                for (Integer numA : setA) {
                    for (Integer numB : setB) {
                        newSet.add(numA + numB);
                        newSet.add(numA - numB);
                        newSet.add(numA * numB);
                        if(numA != 0 && numB != 0) {
                            newSet.add(numA / numB);
                        }
                    }
                }
            }
        }
        for (Set<Integer> set : setList) {
            if(set.contains(number)) return setList.indexOf(set);
        }
        return -1;
    }
}

 

 

쪼끔만 더 짱구를 굴렸다면 충분히 풀 수 있었을 것 같은데 뭔가 아쉬운 문제였다.. 진짜 쉽지 않구만...