Push Operator

Brute Force>순열, NM 시리즈

알고리즘 생각

• 재귀함수를 이용해서 풀 수 있다.(NM시리즈와 똑같은 문제)

  재귀를 이용해서 Brute Force 풀기! 기본 로직은 똑같다! 이 문제의 경우 2,3번 2가지 경우로 나눠서 구현할 수 있다.

1. 정답이 될 수 없는 경우

2. 정답 찾은 경우

3. 다음 경우 호출하는 경우

• 무엇이 어떻게 변형되었는지 파악! NM문제에서 0부터 N(i=0;i<=N;i++)까지 숫자를 선택했다면 이 문제에서는 4개의 연산자 중에서 op[i]-1>=0이면 그 연산자를 선택하는 것이 된다! 다음 경우 호출 : index+1번째 연산자 선택, 넘겨줄 숫자는 num (op[i]) num[idx+1]

흔나 오답

1. 더 이상 진행할 필요없는 경우

2. 다음 경우 호출 : 배열op에서 연산자 선택하고, 다음 재귀호출에 넘겨준다. 연산자 선택 : op[i] --; 재귀함수 호출 : go(index+1, exp+op[i]); 재귀함수 리턴 후 : op[i]++;

public static void go(int index,String exp) {//EXP를 완성한다!
		//1.더이상 진행할 필요 없는 경우. 정답 찾은 경우.
		if(index == n) {//n-1개의 연산자를 끼워넣는것이기 때문에 n이 되면 다 채워진 거임!
			ans.add(exp);
			return;
		}
		//2.다음 경우 호출
		for(int k = 0;k<n-1;k++) {
			for(int i=0;i<4;i++) {//4칙연산 연산자. op 배열 원소값만큼 
				if(op[i]>=1) {
					op[i]--;
				}
				go(index+1,exp+op[i]);
			}
		}
	}

틀린 부

1. 연산자를 선택함에 있어서, 재귀호출하고 리턴되고 나서 선택했던 연산자 다시 원래대로 처리해줘야한다! 아니면 한번 쓴 연산자는 다음 경우의 수에서 사용하지 못하기 때문이다!

//재귀함수 구현. - NM 시리즈 1-4,5-7,9-12 복기!
	public static void dfs(int num,int idx) {
		//정답 찾은 경우.더 이상 반복 X 
		if(idx == n) {//n개이면 다 찾은 것!
			MAX = Math.max(MAX, num);
			MIN = Math.min(MIN, num);
		}
		
		//다음 경우 호출.
		for(int i=0;i<4;i++) {
			if(op[i]>0) {
				op[i]--;//i번째 연산자 '선택'했다는 의미.
				switch(i) {
				case 0:dfs(num+nums[idx],idx+1);
						break;
				case 1:dfs(num-nums[idx],idx+1);
						break;
				case 2:dfs(num*nums[idx],idx+1);
						break;
				case 3:dfs(num/nums[idx],idx+1);
						break;
				}
				op[i]++;//재귀호출 종료되면 '선택'했던 연산자 갯수 다시 늘려준다!
			}
		}
	}

2. 연산자 순열을 만들어서 그 수식의 결과를 저장해야한다. - 구현까지는 하지 못함. => 어떤 연산자를 선택하느냐에 따라 연산이 달라지기 때문에 연산자를 선택하고, 연산을 한 결과값을 다음 재귀함수에 넘겨준다!!!!! 구현 : switch-case 문으로 구현해준다!

case 0: dfs(int index+1,num+nums[index+1]);//index는 현재 index이다.
        break;
case 1: dfs(int index+1,num-nums[index+1]);
        break;
case 2: dfs(int index+1,num*nums[index+1]);
        break;
case 3: dfs(int index+1,num/nums[index+1]);
        break;

3. break문은 왜 쓰나?

GitBook

조건에 부합하는 case문을 처리하고 나면 반드시 break문으로 switch블록을 탈출시켜야한다! 그렇지 않으면 불필요한(옳지 않은) 실행/연산이 반복되기 때문이다!!!

이 문제에서 각각의 case문은 선택하는 연산자에 따라서 다음 재귀함수를 호출한다. 재귀함수가 호출되어 실행되고 나면 리턴된 후에 다음 경우의 수를 만들어야한다. =>순열 0 1을 만들었으면 그 다음 순열 0 2를 만들어야하기 때문에 재귀함수 다음에 break문으로 switch문 탈출해서 i-for문 i++ 해야한다!!!!!!

4. 약한 부분

재귀함수를 이용해서 푸는 문제들 많이 틀린다. 이유는 재귀함수 종료조건을 명확하게 하지 않거나, 배열의 범위를 초과했기 때문이다. 다음 재귀함수를 호출할 때 넘겨주는 매개변수는 종국에 종료조건이 되기 때문에 이 업데이트되는 매개변수의 초기값부터 끝값을 생각해보도록 한다!