연산자 끼워넣기

NM9의 응용 버전! NM9 : 중복되는 숫자가 있을 때 중복을 제거한 숫자 저장, 중복 제거한 각각의 숫자들에 대해 중복횟수를 저장!

연산자 끼워넣기에서 주어지는 연산자에 대한 정보는 중복 횟수 저장배열을 의미한다. 고로, 재귀함수에서 다음 경우 호출하는 경우 NM9와 비슷하게 for문과 재귀함수 호출을 할 수 있다.

for(int i=0;i<N;i++){ if(op[i]>0){ //순열 생성, 재귀함수 호출 } }

틀린 부분

  1. for문 반복 조건에서 N은 중복을 제거한 후 갯수인데 이 문제는 N이 아니라 4라고 해야한다! N은 숫자 갯수를 의미하기 때문!!✅

  2. 재귀함수 호출 시 초기 값 : go(int index,int num)//index번째 연산자를 선택, num은 현재까지 계산한 값. ① go(0,0) : 0번째 연산자를 선택, 초기값은 0으로 전달했지만 0번째 연산자를 선택할 때, 연산자를 선택하기에 앞서 숫자를 먼저 선택해야 다음함수 호출시에 계산한 값을 넘기기 때문에 초기 호출시 계산한 값은 0이 아니라 Num[0]을 넘겨준다! =>go(0, Num[0]) ② index번째 연산자를 선택할 때, 연산자 뿐만 아니라 계산할 숫자에 대한 인덱스도 관리해야한다.⭐️⭐️⭐️⭐️⭐️ 초기 호출 시에 Num[0]으로 시작했으면 다음 계산될 값은 Num[1]이 된다! 그런데 index=0으로 시작해버리면 0번째 연산자를 선택할 때, 계산할 숫자는 Num[1]이 되버리므로 두 개의 인덱스를 따로 관리해줘야한다. => 선택할 연산자의 인덱스와 계산할 숫자의 인덱스를 맞춰주기 위해 index를 1부터 시작해서 N-1까지 선택하는 것으로 한다! => 종료 조건 : index == N이면 종료!

  3. 2번을 다시 정리 : 일단 재귀함수 뼈대부터 만든다. (int index, int num) index : 현재 선택할 연산자의 번호 : 총 N-1개를 선택한다. num : 지금까지 계산한 계산값 => 초기에는 Num[0]으로 시작한다!!! 이후에 계산할 값은 num +-*/ Num[1]부터 시작한다! 이처럼 이후에 계산할 값의 인덱스도 기억해줘야하기 때문에 1부터 시작하는 인덱스를 매개변수 index를 활용한다! ⭐️⭐️⭐️⭐️⭐️ index는 총 몇개를 선택했는지 판단하기 위해 존재하므로 사실 0부터 시작하든 1부터 시작하든 100부터 시작하든 상관없다! N-1개를 선택하면 종료해주기만 하면 된다!

index번째 연산자를 선택할 때, 사실 index를 0부터 시작할지 1부터시작할지는 크게 상관 없다. 중요한 건, 계산할 Num의 인덱스다! 처음에 Num[0]에서 연산을 시작하기 때문에 초기값으로 Num[0]을 받은 후 Num의 인덱스는 1부터 시작한다. 이 때 이 인덱스의 범위는 1부터 시작, N-1까지이다. index == 1부터 N-1개 정해지면 끝난다! ex) N = 3인 경 1. index = 1 연산자 선택 O 2. index = 2 연산자 선택 O // 정답 찾은 경우! 3. index = 3 // 종료 조건 : index== N인 경우 정답 찾은 경우로, 재귀함수 종료한다! 리턴⭐️⭐️⭐️ 정답 찾은 경우 리턴하기 때문에 N-1개 연산자를 선택하고 나면 정답 찾은 경우로서, 바로 리턴되기 때문에 Num의 index(3)번째에 접근하는 배열범위초과 에러가 날 이유가 없다! (정답 찾은 경우 리턴문 안 넣어서 배열범위 초과 에러 나서 틀림)

생각했지만 제대로 구현하지 못한 부분

  1. 선택한 Index를 연산자 기호로 바꿔서 수식 결과값을 계산

  2. 최댓값, 최솟값 저장

1번 : (재귀함수-다음 경우 호출)재귀함수를 호출할 때, 몇번째 인덱스를 선택하느냐에 따라 해당 연산자로 연산해서 연산한 결과값을 다음 재귀함수 호출 매개변수로 넘겨준다! => switch-case문으로 구현 가능!!⭐️

2번 : (재귀함수-정답 찾은 경우)총 N-1개의 연산자를 다 선택했을 때, MAX = Math.max(num, 아주 작은 값) MIN = Math.min(num,아주 큰 값)

문제 정답과 내가 접근, 생각했던 것과 차이점

나 : 연산자를 N-1개 모두 선택하면 재귀함수-정답 찾은 경우 부분에서 일괄적으로 연산자 인덱스를 String 또는 char 타입의 연산자 기호로 변환하려고 했다. 그런데 한꺼번에 바꾸고, 계산을 하려고 하니까 어디서부터 손대야할지 복잡했다. 재귀함수 - 불가능한 경우 없어도 된다. 어차피 정답 찾은 경우에서 정답 저장하고 리턴되버리기 때문에 밑으로 내려가지 않는다.

정답 : 연산자 인덱스를 선택하고, 다음 재귀함수를 호출할 때, 선택한 연산자로 현재까지 계산값을 넘겨준다! 문제 조건에서 연산자 우선순위와 상관없이 앞에서부터 연산이 가능하다고 했기 때문에 이렇게 하는 것이 가능하다!

2번째로 푼 경우

  • N-1 개 연산자 다 선택했을 때 계산하는 부분 구현은 맞았다. 다만 추가적으로 정답이 되는 최댓값, 최솟값 비교&갱신해서 저장하는 부분만 추가해주면 된다. => void 타입, 계산해서 min,Max값 셋

  • 순열 생성하는 부분에서 틀린 것 같다. =>Op[i]의 배열값을 더하는 것이 아니라, 연산자의 인덱스인 i를 더하는 것이다‼️‼️‼️‼️‼️‼️‼️😂😭

일단, 연산자를 선택하면서 계산을 하는 경우와 연산자를 다 선택하고 난 후 마지막에 계산하는 경우 중에 후자를 선택했다. calculate(String operators) 메서드에서 계산한 것을 구현하는데 결과값이 제대로 나오지 않았다. 분명 for(int i=0;i<4;i++) { if(Op[i] >0 ) 조건을 걸어서 양수일 때만 선택하는 처리를 했는데도 불고하고 선택가능하나 갯수가 0인 연산자도 선택하는 일이 발생했다. 원인이 뭐지? 나오 비슷한 코드를 짠 사람의 코드를 참고해야함.

틀린 이유!!! 선택 가능한 연산자 갯수를 의미하는ㄴ 입력갑 Op배열값을 이용해서 선택하면, 1감소시키고, 이 배열 값이 0보다 큰 경우에만 선택한다! 이 때 Op[i]값은 중복 선택을 방지하기 위해 증가 감소ㅗ하는 값일 뿐이고, 선택하는 값은 연산자의 인덱스이다!!!!!!!!!!!! 몇번째 연산자를 선택하는지, 그 연산자의 인덱스를 만들어가야하는 것이다!!!!!!

틀린 코드 : operator+Op[i]가 아니라, operator+i이다!ㅜㅜㅜ 디버깅을 해보니까, 선택가능한 연산자 갯수가 1개씩 있을 때 0, 00 이런식으로 나오는 것을 알 수 있었다. 선택하는 i를 출력해보니 내가 i를 선택서 더하는 게 아니라, 1감소 Op[i] 갯수값을 더하기 때문 기존에 1이였던 Op[i]는 당연히 0이 되고, 이 0이 되는 틀린 값을 더해가기 때문에 오답이 되는 것이였다. 

static void go(int index,String operator) {
		//1.재귀 종료 N-1개의 연산자들 선택 다 한 경우 : 선택한 결과로 만든 계산값 set에 넣는다!
		if(index == N-1) {
			calculate(operator);
			return;
		}
		//2.현재 index 선택, 다음 경우 호출
		for(int i=0;i<4;i++) {//4가 아니라 N-1?
			if(Op[i]>0) {
				//System.out.println("선택한 i:"+i);//2가 나올 것.
				Op[i]--;
				go(index+1,operator+Op[i]);
				Op[i]++;
			}
		}
	}

정답 코드 : 

static void go(int index,String operator) {
		//1.재귀 종료 N-1개의 연산자들 선택 다 한 경우 : 선택한 결과로 만든 계산값 set에 넣는다!
		if(index == N-1) {
			calculate(operator);
			return;
		}
		//2.현재 index 선택, 다음 경우 호출
		for(int i=0;i<4;i++) {//4가 아니라 N-1?
			if(Op[i]>0) {
				//System.out.println("선택한 i:"+i);//2가 나올 것.
				Op[i]--;
				go(index+1,operator+i);
				Op[i]++;
			}
		}
	}

일단 반복문 구현은 알겠는데, 지금까지 연산결과가 다음 연산의 피연산자1이 된다. 그러니까 현재 계산한 값이 result가 되고, 그 다음 계산에서 result가 피연산자1이 되는 것이다.

static int calculate(String op) {
		int result = 0;
		char[] opArr = op.toCharArray();
		for(int i=0;i<N-1;i++) {
			if(i==0) {
				if(opArr[i]-'0'==0) {
					result = Num[i]+Num[i+1];
				} else if(opArr[i]-'0'==1) {
					result = Num[i]-Num[i+1];
				} else if(opArr[i]-'0'==2) {
					result = Num[i]*Num[i+1];
				} else if(opArr[i]-'0'==3) {
					result = Num[i]/Num[i+1];
				}
			} else {
				if(opArr[i]-'0'==0) {
					result += Num[i+1];
				} else if(opArr[i]-'0'==1) {
					result -= Num[i+1];
				} else if(opArr[i]-'0'==2) {
					result *= Num[i+1];
				} else if(opArr[i]-'0'==3) {
					result /= Num[i+1];
				}
			}
		}
		return  result;
	}

문제 정리

일단 기본적으로, 선택을 다 한 경우에 계산을 하려면 계산하려는 숫자1과 숫자2를 인덱스를 조회하는 과정이나 선택한 연산자로 순서대로 계산하는 과정이 코드가 길어지고 더 번거로워진다.

문제 푼 사람들이 많아서 그런 것일수도 있는데 앞의 열댓명 정 대부분의 사람들은 선택하면서 계산한 값을 다음 재귀함수에 넘겨서 푸는 방법을 선택했고, 이 방법으로 풀었을 때 시간 복잡도는 100ms 안으로 나왔다. 그렇기 때문에 재귀함수 이용, 0123가 의미하는 연산자로 계산하는 구현 능력을 기르기 위해서는 선택 다 한 후에 값을 계산하는 방법으로 풀어봐도 되지만, 시간 효율성을 따져봤을 때는 좋지 않기 때문에 선택하면서 계산하는 더 나은 방법으로 풀기로 한다.

Previous컨베이어 벨트Next연구소3 문제 풀기 위한 비트마스킹 복습⭐️

Last updated