[프로그래머스] 42895. N으로 표현

프로그래머스

---

 ❄️ 문제

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

---

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

---

❄️ 예시

---

❄️ 풀이 설명

• 아래의 그림을 보면, 혹시 규칙이 보이시나요?
• 아래의 그림을 보면, N*10 + N의 값이 들어가고, 사칙연산으로 해당 값들을 만들 수 있는 것이 보일 것입니다.
• 또한 이 전에 2개에 있던 식이 3개에서 사용된 후, 그 뒤에 사칙연산과 N의 값으로 표현이 가능한 것을 확인할 수 있습니다.

---

• answer을 -1로 설정한 이유는, 만약 반복문을 돌았을 때에 해당 사항이 없으면 -1을 리턴시키기 위함이다.
• 문제에도 최솟값이 8보다 크면 -1을 리턴하라고 써있기 때문에, -1로 초기값을 설정해주고 시작하였다.
• 같은 값이 겹치면 안되기 때문에 Set을 사용해 주었다.
• n은 이후, 5나 55 등과 같은 값을 더해줄 변수로 사용하기 위해 선언해 주었다.

 

public static int solution(int N, int number) {
   int answer = -1;
   HashSet<Integer>[] set = new HashSet[9];
   int n = 0;
   
   return answer;
}

---

• 만약 N과 number가 같으면 1번이기 때문에 1을 리턴해준다.
• 그리고 반복문을 돌면서 안의 set을 초기화 해주었다.
• 그리고 n의 값을 계속 10을 곱하고, N을 더하며 해당 값들을 set에 넣어주었다.

 

public static int solution(int N, int number) {
   
   ...

   if (N == number) {
      return 1;
   }

   for (int i = 1; i < 9; i++) {
      n = (n * 10) + N;
      set[i] = new HashSet<>();
      set[i].add(n);
   }
}

---

• 반복문을 돌리면서 각 수의 사칙연산을 set에 추가해 주었다.
• 나눗셈은 0이 아니여야 하기 때문에 확인 후에 나누어 주었다.
• 그리고 만약, i번째 인덱스에 해당 넘버가 있으면,  반복문을 그 이후로 계속 돌 필요가 없기 때문에 바로 i 값을 리턴시켜주었다.
• 그리고 반복문을 다 돌렸음에도 넘버를 찾지 못하면 8보다 큰 값이기 때문에 -1을 리턴 시켜주었다.

 

public static int solution(int N, int number) {
   
   ...

   for (int i = 1; i < 9; i++) {
      for (int j = 1; j < i; j++) {

         for (Integer num1 : set[j]) {
            for (Integer num2 : set[i - j]) {
               set[i].add(num1 + num2);
               set[i].add(num1 - num2);
               set[i].add(num1 * num2);

               if (num2 != 0) {
                  set[i].add(num1 / num2);
               }
               if (num1 != 0) {
                  set[i].add(num2 / num1);
               }
            }
         }

         if (set[i].contains(number)) {
            return i;
         }
      }
   }

   return answer;
}

---

❄️ 최종 풀이

 

public static int solution(int N, int number) {
   int answer = -1;
   HashSet<Integer>[] set = new HashSet[9];
   int n = 0;

   if (N == number) {
      return 1;
   }

   for (int i = 1; i < 9; i++) {
      n = (n * 10) + N;
      set[i] = new HashSet<>();
      set[i].add(n);
   }

   for (int i = 1; i < 9; i++) {
      for (int j = 1; j < i; j++) {

         for (Integer num1 : set[j]) {
            for (Integer num2 : set[i - j]) {
               set[i].add(num1 + num2);
               set[i].add(num1 - num2);
               set[i].add(num1 * num2);

               if (num2 != 0) {
                  set[i].add(num1 / num2);
               }
               if (num1 != 0) {
                  set[i].add(num2 / num1);
               }
            }
         }

         if (set[i].contains(number)) {
            return i;
         }
      }
   }

   return answer;
}​

---