[Programmers] N으로 표현_Java

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

프로그래머스

문제

 

 

문제 해설

숫자 N을 9번 미만으로 사친연산 조합하여 target Number를 만들 수 있는 최소 개수를 출력하는 문제이다.

꽤 예전에 python으로 한번 풀었던 문제여서 풀이방법은 알고 있었으나, Java 연습겸 + code refactorying 겸으로 다시 풀어봤다. 너무 어려워서 해설 보고 풀었던 기억이 있다.

 

 

문제 풀이

(1) 숫자 N을 8개까지 겹친 숫자 List<HashSet> 만들기 (ex  N = 5일 경우 : 0, 5, 55, 555 ... 55555555)

(2) 위 List를 이중 for문으로 탐색하며 아래 계산을 진행한다.
  - 첫번째 for문은 2 <= i < 9까지 탐색한다.
  - 두번째 for문은 1 <= j < ( i / 2)까지 탐색한다.

  (3) (1)에서 만든 List의 j번째 숫자리스트(a)와 i - j번째 숫자 리스트(b)를 for문으로 탐색하며 사친연산한다.
    >> a + b, a - b, b - a, a * b, a / b, b / a를 진행하며, target number가 아닐 경우, (1)의 List i번째에 add해주며, target Number일 경우 바로 i를 return한다.

* 참고사항
  - (1)의 숫자 List를 만들 때도 target number와 일치하는지 체크해주어야 한다.
  - 중복된 연산값이 많으니 List 내부에는 HashSet으로 넣어주는 것이 좋을 거 같다.

 

 

* 코드

import java.util.ArrayList;
import java.util.HashSet;

class Solution {
    public int solution(int N, int number) {
        
        try{
            checkTarget(N, number);
        } catch (Exception e) {
            return 1;
        }
        
        ArrayList<HashSet> arr = new ArrayList<HashSet>();
        arr.add(new HashSet<>());
        HashSet<Integer> innerArr;

        int answer = -1;
        HashSet<Integer> arr1;
        HashSet<Integer> arr2;
        
        
        for(int i = 1; i < 9; i ++){
            try{
                checkTarget(Integer.parseInt((String.valueOf(N).repeat(i))), number);
                innerArr = new HashSet<>();
                innerArr.add(Integer.parseInt((String.valueOf(N).repeat(i))));
                arr.add(innerArr);
            }catch(Exception e){
                return i;
            }
        }

        for(int i = 2; i < 9; i ++){
            for(int j = 1; j < (i / 2) + 1; j ++){
                arr1 = arr.get(j);
                arr2 = arr.get(i - j);
                for(Integer n:arr1){
                    for(Integer nn:arr2){
                        try {
                            arr.get(i).add(checkTarget(n + nn, number));
                            arr.get(i).add(checkTarget(n * nn, number));
                            arr.get(i).add(checkTarget(n - nn, number));
                            arr.get(i).add(checkTarget(nn - n, number));
                            
                            if(nn > 0){
                                arr.get(i).add(checkTarget(n / nn, number));
                            }

                            if(n > 0){
                                arr.get(i).add(checkTarget(nn / n, number));
                            }
                            
                        } catch (Exception e) {
                            answer = i;
                            return answer;
                        }
                    }
                }
            
            }
        }
        return answer;
    }

    public int checkTarget(int n, int target) throws Exception{
        if(n == target){
            throw new Exception();
        }else{
            return n;
        }
    }
}