[프로그래머스/Lv. 3] N으로 표현 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int solution(int N, int number) {
        List<Set<Integer>> setList = new ArrayList<>();
 
        for(int i = 0 ; i < 9 ; i++)    setList.add(new HashSet<>());    // 개수 별 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 str = Integer.toString(N);
            setList.get(i).add(Integer.parseInt(str.repeat(i)));  
            
            for(int num : setList.get(i)) {
                if(num == number)
                    return i;
            }
        }
        
        return -1;
    }
    
    // 두 Set의 값 간 사칙연산 계산 메소드
    private static 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);
            }
        }
    }
}

 

 

🧩  해결 아이디어

• DP - Set을 활용한 메모이제이션

1) 숫자 N의 사용하는 갯수 별로 만들 수 있는 통 생성 (1~8까지)

2) 칸 숫자가 N인 경우, 합이 N이 되는 숫자 2개의 값 이용 (1+4 / 2+3 / 3 + 2 / 4 + 1 이런 식으로)

3) 각 통마다 연속된 숫자를 넣어줌 (Set 활용해 각 통마다 중복값 제거)

 

💥 유의사항

- 괄호 연산 때문에 양방향 다 계산해줘야하고, 연속된 숫자를 통마다 넣어줘야 한다.

- 통에 들어간 값은 중복되어서는 안 된다.

 

---

🔺 다른 풀이들

- Set 배열 활용, 연속수 넣는 방식 (* 10), 정답 얻는 방식(contains 활용) 이렇게 크게 총 3가지가 좀 다르다.

[동적계획법] N으로 표현 - Java 코드 ★★★(★★)

 

 

- 엥 DFS로 푸셨다ㅏ....  ㄴㅇㄱ

[알고리즘] 프로그래머스 - N으로 표현 - JAVA

---

💬 느낀 점

1시간 정도 고민해보고 풀었는데 못 풀었다...

Set 아이디어, 문자열로 생각해서 반복하는 아이디어는 혼자서 생각 못 했을 것 같다.

문제를 많이 안 풀었다는 것이겠지ㅎㅎ

분발하장,,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

 

https://velog.io/@doxxx93/programmers-pracice-42895

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