문제 url:
연산자 끼워넣기
문제:
🤔 문제 알아보기
삼성 SW 역량 테스트 문제라고 해서 겁을 좀 먹고 시작했는데, 생각보다 다른 문제들에 비해 구상하는데 몇분 걸리지 않아서 나도 풀 수 있겠는데? 한 문제이다.
그러니 필자처럼 겁을 먹었던 분이 있다면, IDE를 다시 켜서 코드를 작성해보고 그래도 안되면 보기를 추천한다.
먼저, 문제를 설명하면,
첫째 줄에는 입력받을 N개의 숫자 개수를 입력받는다.
둘째 줄에는 N개만큼 숫자를 입력받는다.
셋째 줄에는 N-1개만큼의 연산자의 개수를 입력받는다.
여기서 총 4개의 수를 입력받는데, 덧셈, 뺼셈, 곱셈, 나눗셈 순으로 개수를 입력받는다.
또한 연산자 우선순위를 고려하지 않아도 되며, 입력받는 숫자는 절대로 움직이지 않는다.
한 마디로 숫자 사이의 연산자만 바꿔주며 계산하면 된다는 얘기
그런 다음 해당 연산을 통해 나올 수 있는 값들 중 최댓값과 최솟값을 출력하면 된다.
🐱👤 실제 코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int[] arr;
static int[] operation;
static int min;
static int max;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
operation = new int[4];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < 4; i++) {
operation[i] = Integer.parseInt(st.nextToken());
}
min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;
dfs(1,arr[0] );
System.out.println(max);
System.out.println(min);
}
static void dfs(int depth, int sum) {
if(depth == N ) {
max = Math.max(max, sum);
min = Math.min(min, sum);
return;
}
for(int i = 0; i < 4; i++) {
if(operation[i] != 0) {
operation[i]--;
switch(i) {
case 0:
dfs(depth + 1, sum + arr[depth]);
break;
case 1:
dfs(depth + 1, sum - arr[depth]);
break;
case 2:
dfs(depth + 1, sum * arr[depth] );
break;
case 3:
dfs(depth + 1, sum / arr[depth]);
break;
}
operation[i]++;
}
}
}
}
😎 코드 풀이 및 해석
1번 쨰 코드
dfs(1,arr[0] );
static void dfs(int depth, int sum) {
if(depth == N ) {
max = Math.max(max, sum);
min = Math.min(min, sum);
return;
}
for(int i = 0; i < 4; i++) {
if(operation[i] != 0) {
operation[i]--;
switch(i) {
case 0:
dfs(depth + 1, sum + arr[depth]);
break;
case 1:
dfs(depth + 1, sum - arr[depth]);
break;
case 2:
dfs(depth + 1, sum * arr[depth] );
break;
case 3:
dfs(depth + 1, sum / arr[depth]);
break;
}
operation[i]++;
}
}
}생각보다 짧은 코드이다. 간단히 해석하자면,
우리 5와 6이라는 숫자를 입력받고 곱하기 연산자 한개[0,0,1,0] 를 입력받았다고 가정하자
사람의 머리로 계산하면 그냥 을 하면 되는데, 컴퓨터는 그렇지 않다.
컴퓨터로 하려면 먼저 arr[0]인 5를 구하고 operation[3]에 위치에 가서 해당 값을 가져오고 그런 다음 arr[1]인 6을 구해서 이 세 개를 합쳐야 을 아마 계산할 수 있을 것이다.
그럼 어떻게 하면 이를 더 편하게 계산할 수 있을까?
문제 조건에서 숫자는 해당 위치에서 변하지 않는다고 했다.
그렇기 때문에 초기값은 변하지 않으니 먼저 첫 값을 0번째 인덱스 값으로먼저 세팅해준 다음, 연산자를 구하고 이를 그 다음 배열에 위치한 6을 곱한 그 값을 넘겨주면 되지 않을까?
코드를 보면 이 말이 이해가 좀 쉽게 될 것이다.
dfs의 초기 sum값을 배열의 첫 번째 요소인 arr[0]을 입력
그런 다음, 연산자 배열을 반복하며 연산자를 식별한 후
재귀호출을 통해 다음 값에는 현재 sum과 대음 배열의 값을 연산자에 맞게 구한 다음 이를 다시 sum으로 넘겨주면 된다.
직접 실습해보자,
3 4 5
1 0 1 0
해당 값이 주어졌을 때,우리는
3 + 4 * 5 / 3 * 4 + 5이렇게 총 두 가지를 구할 수 있다.우리는 처음 dfs를 호출했을 때 이미 3의 값이 존재한다.
그 다음 연산자 배열을 반복하며 연산자를 식별하는데,if(operation[i] != 0)연산자 배열에 값이 0이라면 연산이 존재하지 않는다는 의미로, 연산자가 존재할 때 이를 동작한다.
operation[i]--;그런 다음 해당 연산횟수를 줄여 1이라면 0으로 2라면 1로 만들어 횟수를 조절 할 수 있다.
그럼 먼저 더하기 연산자가 한개 존재하니 더해보자,
dfs(depth +1 , 3 + arr[depth](4의 값을 가짐) )을 재귀호출한다.여기서 depth는 간단하게 숫자가 입력된 배열의 인덱스라고 생각하면 된다.
그런 다음 depth가 N과 같으면 해당 sum에 대해 최솟값과 최댓값을 비교해서 넣는 로직이 된다.operation[i]++;그런 다음, 다시 처음 재귀로 돌아왔을 때 횟수를 줄여줬던 것을 원상 복구해줘 모든 경우의 수를 구할 수 있도록 한다.
필자가 아직 초짜라 설명이 어렵다. 그리고 필자가 이해하고 푼 흐름대로 설명하다 보니 의식의 흐름대로 설명을 해버린다...
그래도 코드만 보고 바로 이해하기 어려운 분들을 위해 구석구석 설명하고자 한 것이니
너그러운 마음으로 눈을 부릅뜨고 읽어봐주면 좋겠다.
그래도 이해가 안된다면! 간단한 TC를 손으로 그려보면 코드가 금방 이해가 될 것이다.
🤢 트러블 슈팅
switch(i) {
case 0:
dfs(depth + 1, sum + arr[depth]);
break;
case 1:
dfs(depth + 1, sum - arr[depth]);
break;
case 2:
dfs(depth + 1, sum * arr[depth] );
break;
case 3:
dfs(depth + 1, sum / arr[depth]);
break;
}
필자는 해당 코드를 이전에는 아래와 같이 풀었다.
switch(i) {
case 0:
dfs(depth + 1, sum + arr[depth], i + 1);
break;
case 1:
dfs(depth + 1, sum - arr[depth], i + 1);
break;
case 2:
dfs(depth + 1, sum * arr[depth], i + 1);
break;
case 3:
dfs(depth + 1, sum < 0 ?
(-sum / arr[depth]) * -1 : sum / arr[depth], i + 1);
break;
}문제 조건을 읽어보니
나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.
이러한 조건이 있어서 저렇게 짯었는데, 자바는 이런 과정이 필요 없다고 한다.
아래는 그 이유를 챗지피티에 물어본 것이다.
if(depth == N ) {
max = Math.max(max, sum);
min = Math.min(min, sum);
return;
}
↓
if(depth == N ) {
System.out.println(sum);
if(sum > max) {
max = sum;
} else if(sum < min) {
min = sum;
}
return;
}처음에는 아래와 같이 풀었다. 이렇게 푸니
보기 문제 TC1번이 틀렸다고 한 것이다! 그래서 찾아보니
만약 값이 하나만 존재한다면, 해당값이 곧 최솟값이며 최댓값이 되는 것인데,
위와 같이 짜니 최댓값인 max만 바뀌고 min은 변하지 않은 것이다.
문제 조건에 특별한 조건이 없다면 위처럼 그냥 Math.min과 max로 최솟값 최댓값을 구해주는게 안전하다.
for(int i = 0; i < 4; i++) {
if(operation[i] != 0) {
operation[i]--;
switch(i) {
case 0:
dfs(depth + 1, sum + arr[depth]);
break;
case 1:
dfs(depth + 1, sum - arr[depth]);
break;
case 2:
dfs(depth + 1, sum * arr[depth] );
break;
case 3:
dfs(depth + 1, sum / arr[depth]);
break;
}
operation[i]++;
}
}
↓
for(int i = at; i < 4; i++) {
if(operation[i] != 0) {
operation[i]--;
switch(i) {
case 0:
dfs(depth + 1, sum + arr[depth], i + 1);
break;
case 1:
dfs(depth + 1, sum - arr[depth], i + 1);
break;
case 2:
dfs(depth + 1, sum * arr[depth], i + 1);
break;
case 3:
dfs(depth + 1, sum / arr[depth]);
break;
}
operation[i]++;
}
}처음에는 dfs에 i값을 넘겨줘서 움직이도록 했는데, 이렇게 하니
첫 번째 depth로 다시 가지 않고 멈추는 것이다.
그래서 이유를 계속 생각하니 연산자 배열은 연산자 개수를 가지고 판단해야지
연산자 위치를 움직이며 생각하니 풀리지 않았던 것이다.
즉, 더하기 연산자가 2개가 존재한다면! 더하기 연산자 두개를 모두 고려한 조건이 포함되어야 하는데,
저렇게 풀게 되면 더하기를 하나 하고 바로 빼기로 넘어가게 되어 틀렸던 것이다.
