# Push Operator **알고리즘 생각** * 재귀함수를 이용해서 풀 수 있다.(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]++;** ```java 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=1) { op[i]--; } go(index+1,exp+op[i]); } } } ``` **틀린 부** 1. 연산자를 선택함에 있어서, 재귀호출하고 리턴되고 나서 선택했던 연산자 다시 원래대로 처리해줘야한다! 아니면 한번 쓴 연산자는 다음 경우의 수에서 사용하지 못하기 때문이다! ```java //재귀함수 구현. - 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. 연산자 순열을 만들어서 그 수식의 결과를 저장**해야한다. - 구현까지는 하지 못함.\ \&#xNAN;**=> 어떤 연산자를 선택하느냐에 따라 연산이 달라지기 때문에 연산자를 선택하고, 연산을 한 결과값을 다음 재귀함수에 넘겨준다!!!!!**\ **구현 : switch-case 문으로 구현해준다!** ```java 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문은 왜 쓰나? {% embed url="" %} 조건에 부합하는 case문을 처리하고 나면 반드시 break문으로 switch블록을 탈출시켜야한다! 그렇지 않으면 불필요한(옳지 않은) 실행/연산이 반복되기 때문이다!!! 이 문제에서 각각의 case문은 선택하는 연산자에 따라서 다음 재귀함수를 호출한다. 재귀함수가 호출되어 실행되고 나면 리턴된 후에 다음 경우의 수를 만들어야한다.\ \=>순열 0 1을 만들었으면 **그 다음 순열** 0 2를 **만들어야하기 때문에** **재귀함수 다음에 break문**으로 **switch문 탈출**해서 **i-for문 i++** 해야한다!!!!!! 4\. **약한 부분** **재귀함수를 이용해서 푸는 문제**들 많이 틀린다. 이유는 재귀함수 종료조건을 명확하게 하지 않거나, 배열의 범위를 초과했기 때문이다. 다음 재귀함수를 호출할 때 넘겨주는 매개변수는 종국에 종료조건이 되기 때문에 이 업데이트되는 매개변수의 초기값부터 끝값을 생각해보도록 한다! --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/implementation/push-operator.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.