• 문제

    1

  • 고민

    문제 제한 사항을 보고 처음에는 1~32001 길이의 배열을 만들어 해당 값을 넣고 계산하며 처리하려했다. 테스트 케이스가 대부분 통과 못하자, 해당 범위를 벗어난 값이 다른 연산자에 의해 다시 결과값에 포함될 수 있는 사실을 깨닫고 List에 값을 관리하는 형식으로 생각을 변경했다. N의 리스트를 구할 때, 우선 5를 N만큼 이은 수가 (1 ~ N -1) 리스트에 없는 경우 N번째 리스트에 추가해주고 앞 전에 구한 리스트들로 값을 구하려 했다. 예를 들어 N = 6일 경우 N = 5인 리스트에 5와 덧셈, 곱셈, 뺄셈, 나눗셈을 하면되겠지 싶었다. 결과는 예외가 많았다. N = 2 인 리스트를 3번 계산한 결과를 생각지 못했다. 여기까지 생각 후 정답이 나왔다. 리스트의 길이가 N인경우 ( {1,N-1}, {2, N-2}, {3,N-3}, … {N-1, 1}) 의 리스트끼리의 계산 결과를 전부 포함하면 예외가 없다고 생각했다. 여기에 더해서 계산하는 범위는 절반까지만 진행하면되기에 N/2까지 계산하였다.

  • 코드

    import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
  
class Solution {
    public List<Integer>[] getNewList(List<Integer> list[], int N, int level){
		int tmp = 0;
		for( int i = level; i > 0 ; i-- ) {
			tmp += N * Math.pow(10, (i-1));
		}
  		
		list[level].add(tmp);
  		
		for(int i = 1; i <= level/2; i++) {
			int j = (level - i);
  			
			for(int left = 0; left < list[i].size(); left++) {
				for(int right = 0; right < list[j].size(); right++) {
					int l = list[i].get(left);
					int r = list[j].get(right);
					list[level].add(l + r);
					list[level].add(l * r);
					list[level].add(l - r);
					list[level].add(r - l);
					if ( r != 0 ) {
						list[level].add(l / r);	
					}
					if ( l != 0 ) {
						list[level].add(r / l);
					}
				}
			}
		}
		return list;
	}
    public int solution(int N, int number) {
        List<Integer> list[] = new ArrayList[9];
		for(int i = 0 ; i < 9; i++) {
			list[i] = new ArrayList<Integer>();
		}
		for(int level = 1; level < 9; level++) {
			list = getNewList(list, N, level);
			HashSet<Integer> tmp = new HashSet<Integer>(list[level]);
			list[level] = new ArrayList<Integer>(tmp);
			if( list[level].contains(number)) {
				return level;
			}
		}
		return -1;
    }
}