[Java] N으로 표현 - Lv3 프로그래머스 / 동적 계획법(Dynamic Programing)

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

프로그래머스

 

 

 

첫 풀이

---

최소 반복 횟수를 구하는 문제이기 때문에

Bottom-Up방식을 활용해서 8번 반복할 때까지 해당 해가 있는지 찾고, 반복횟수가 9번째가 될 때

answer = -1로 리턴해주게 하자.. 라고 생각하며 코드를 작성했다.

 

(DP공부를 한 뒤, 간단한 문제들을 풀고 처음으로 푸는 높은 난이도(??)의 문제라 설명이 부족할 수 있음.. 지나가던 고수분들 계시면 고쳐주시면 감사하겠습니다. 많은 도움이 됩니다 (__ )꾸벅)

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

class Solution {	
	int answer = 0;
	
    public int solution(int N, int number) {
    	if(N==number) return N;
    	
    	Set<Integer> set = new HashSet<Integer>() {{
    		add(N);
    		add(N+N);
    		add(N-N);
    		add(N*N);
    		add(N/N);
    		add((10*N) + N);
    	}};
    	
    	if(chk(set, number, 2)) return answer;
    	
    	dp(N, number, 3, set);
    	
    	System.out.println(answer);
    	return answer;
    }
    
    public void dp(int N, int number, int idx, Set<Integer> set) {
    	if(idx==9) {
    		answer = -1;
    		return;
    	}
    	
    	Set<Integer> num_set = new HashSet<>();
    	Iterator<Integer> iter = set.iterator();
    	while(iter.hasNext()) {
    		int num = iter.next();
    		num_set.add(num+N);
    		num_set.add(num-N);
    		if(num!=0) {
    			num_set.add(num*N);
        		num_set.add(num/N);
        		num_set.add((num*10)+N);
        		num_set.add(N/num);
    		}   		    		
    		num_set.add(N+num);
    		num_set.add(N-num);    		
			num_set.add(N*num);		    		    		
    	}
    	
    	if(chk(num_set, number, idx)) return;
    	
    	dp(N, number, idx+1, num_set);
    }
    
    public boolean chk(Set<Integer> set, int number, int idx) {
    	Iterator<Integer> iter = set.iterator();
    	while(iter.hasNext()) {
    		if(iter.next().equals(number)) {
    			answer = idx;
    			return true;
    		}
    	}
    	return false;
    }
}

 

테스트케이스를 무난하게 통과해서 제출해보았다. 과연?

 

그럼그렇지... 근데 실패하면 실패했지 왜 44.4점이냐  기분나쁘게 ..;;

 

생각해봤는데.. 내 코드는 아래와 같은 문제가 있었음(N이 4번 들어가야하는 상황부터 문제가 발생)

N이 3번 들어가는 상황에서

1번 ↔ 2번 / 2번 ↔ 1번 두가지를 모두 고려해서 set을 만듬.

 

N이 4번 들어가는 상황에서

3번 ↔ 1번 / 1번 ↔ 3번 이 두가지 상황만 고려하다보니 2번 ↔ 2번의 경우를 고려하지 못함...

(이걸 더 예쁘게 설명하지 못하겠다 .. ㅠㅠ)

 

그럼 N이 5번 돌아가는 상황에서

1 ↔ 4 / 2 ↔ 3 / 3 ↔ 2 / 4 ↔ 1의 경우를 고려해야하고.

6번의 경우

1 ↔ 5 / 2 ↔ 4 / 3 ↔ 3 / 4 ↔ 2 / 5 ↔ 1의 경우 모두 고려해야함...

 

이렇게 8번 모두 돌리고 찾고자 하는 number이 없으면 -1을 뱉어내야한다.

 

이렇게 적어놓고보니, 결국 Bottom-Up방식인 것은 같으나, 경우의 수를 저장해놓아야 한다.

어떻게? List안에 Set을 담아서 해보자..

 

 

 

두번째 풀이

---

첫 번째 풀이와 같은 구조에서, List안에 Set을 담아서 모든 경우를 고려할 수 있게 만들었다.

하나더, 첫 풀이에서 놓친 N=number일때 return값을 N으로해둬서, 1로 바꿨다.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

class Solution {	
	int answer = 0;
	
    public int solution(int N, int number) {
    	if(N==number) return 1;
    	
    	List<Set<Integer>> list = new ArrayList<Set<Integer>>();
    	Set<Integer> set = new HashSet<Integer>() {{
    		add(N);
    	}};    	
    	list.add(set);
    	
    	set = new HashSet<Integer>() {{
    		add(N);
    		add(N+N);
    		add(N-N);
    		add(N*N);
    		add(N/N);
    		add((10*N) + N);
    	}};
    	list.add(set);
    	
    	
    	if(chk(set, number, 2)) return answer;
    	
    	dp(N, number, 3, list);
    	
    	System.out.println(answer);
    	return answer;
    }
    
    public void dp(int N, int number, int idx, List<Set<Integer>> list) {    	
    	Set<Integer> num_set = new HashSet<>();
    	
    	for(int i=0; i<list.size(); i++) {
    		int reverse = (list.size()-1) -i;    		
    		
    		Iterator<Integer> iter1 = list.get(i).iterator();
    		Iterator<Integer> iter2 = list.get(reverse).iterator();
    		
    		while(iter1.hasNext()) {
    			int i1 = iter1.next();
    			
    			while(iter2.hasNext()) {
    				int i2 = iter2.next();
    				num_set.add(i1+i2);
    				num_set.add(i1-i2);
    				num_set.add(i1*i2);
    				num_set.add(i2+i1);
    				num_set.add(i2-i1);
    				num_set.add(i2*i1);
    				if(i2!=0) {
    					num_set.add(i1/i2);
    				}
    				if(i1!=0) {
    					num_set.add(i2/i1);
    				}    				
    				num_set.add((i1*10)+i2);
    				num_set.add((i2*10)+i1);
    			}
    			
    		}
    	}    	
    	if(chk(num_set, number, idx)) return;
    	
    	list.add(num_set);    	
    	if(idx==8) {
    		answer = -1;
    		return;
    	}
    	dp(N, number, idx+1, list);
    }
    
    public boolean chk(Set<Integer> set, int number, int idx) {
    	Iterator<Integer> iter = set.iterator();
    	while(iter.hasNext()) {
    		if(iter.next().equals(number)) {
    			answer = idx;
    			return true;
    		}
    	}
    	return false;
    }

}

 

 

음...? 뭐가 문제였을까..

 

 

 

 

 

세번째 풀이

---

한 문제를 너무 오래 끄는 것이 비효율적인 것 같아서 마지막으로 수정하기로 했다.

아래는 수정을 위해 정리한 내용이다.

 

1. 더럽게 긴 코드 수정

2. 굳이 N을 두번 반복할 때 미리 Set을 세팅하고 해야하나..? 1번 ↔ 1번을 돌리는 것까지 포함해서 코드를 짜면 안되나?

 

 - 포스팅이 너무 길어질까 코드를 하나 생략했는데, 8번을 초과하면 -1을 뱉어내야 하므로, 8번째 경우까지 포함해줘야했는데 해당 경우를 포함해 주지 않아 5,8번 테스트케이스의 실패가 발생했었다.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {	
	int answer = -1;
	
    public int solution(int N, int number) {
    	List<Set<Integer>> list = new ArrayList<Set<Integer>>();
    	list.add(null);
    	list.add(new HashSet<Integer>());
    	list.get(1).add(N);   	
    	
    	dp(N, number, list);
    	
    	System.out.println(answer);
    	return answer;
    }
    
    public void dp(int N, int number, List<Set<Integer>> list) {    	
    	
    	for(int i=1; i<=8; i++) {
    		if(i>=2) {
    			list.add(new HashSet<Integer>());
    			StringBuilder sb = new StringBuilder();
    			for(int j=0; j<i; j++) {    				
    				sb.append(N);
    			}
    			list.get(i).add(Integer.parseInt(sb.toString()));
    			
    			for(int j=1; j<i; j++) {
    				for(int k : list.get(j)) {
    					for(int l : list.get(i-j)) {
    						list.get(i).add(k+l);
    						list.get(i).add(k-l);
    						list.get(i).add(k*l);
    						if(l!=0) list.get(i).add(k/l);
    					}
    				}
    			}
    		}
    		if(chk(list.get(i), number, i)) return;
    	}
    	
    }
    
    public boolean chk(Set<Integer> set, int number, int idx) {
    	if(set.contains(number)) {
    		answer = idx;
    		return true;
    	}
    	return false;
    }

}

 

위의 짠 코드를 약간 수정했다.

1. 굳이 앞의 수와 뒤의 수를 번갈아가며 사칙연산 할 필요가 없었다. 조건만 잘 주면 사칙연산 한번씩이면 끝남.

2. N을 이어붙인 숫자를 따로 추가할 필요가 없고 set을 추가하는 과정에서 셋팅만 해주면 된다.