삼성 코딩테스트 기출문제 중 하나라는 연산자 끼워넣기 문제를 풀어보았다. 블로그 업데이트가 조금 늦었는데 최근에 코딩 테스트도 보고 다른것도 공부하다보니 늦어졌던거같다. 앞으로는 다시 각성해서 많이 풀어봐야겠고 최근에 풀었던 코딩 테스트를 기준으로 조금은 자신감이 생겼다.
이 문제는 + - * % 가 주어졌을때 해당 연산자의 숫자를 이용해서 만들수 있는 최대값과 최소값을 리턴하면 되는 문제이다. 언뜻보면은 어려워 보이는 문제지만 사실 backtracking 의 기본원리와 permutation 방식을 안다면 꽤 쉽게 풀수있는 문제이다. 맨 마지막 줄에 있는 숫자들을 index 로 표현해서 풀이해 보면 0인덱스는 더하기 1인덱스는 빼기 2인덱스는 곱하기 3인덱스는 나누기를 표현한다.
#include <iostream>
#include <bits/stdc++.h>
#define endl "\n"
#define MAX 100010
using namespace std;
int N;
vector<int> nums;
vector<int> expression;
void Input(){
cin >> N;
vector<int> copy1(N,0);
vector<int> copy2(4,0);
for(int i = 0; i < N; i++){
cin >> copy1[i];
}
for(int i = 0; i < 4; i++){
cin >> copy2[i];
}
nums = copy1;
expression = copy2;
}
void dfs(vector<int>& nums, vector<int>& expression,int& max_, int& min_,int curr_sum,int counter){
if(counter >= nums.size()){
//cout << curr_sum << ' ';
max_ = max(max_,curr_sum);
min_ = min(min_,curr_sum);
return;
}
for(int i = 0; i < expression.size(); i++){
if(expression[i] > 0){
//cout << i << ' ';
switch(i){
case 0:
curr_sum += nums[counter];
expression[i] -= 1;
dfs(nums,expression,max_,min_,curr_sum,counter+1);
curr_sum -= nums[counter];
expression[i] += 1;
break;
case 1:
curr_sum -= nums[counter];
expression[i] -= 1;
dfs(nums,expression,max_,min_,curr_sum,counter+1);
curr_sum += nums[counter];
expression[i] += 1;
break;
case 2:
curr_sum *= nums[counter];
expression[i] -= 1;
dfs(nums,expression,max_,min_,curr_sum,counter+1);
curr_sum /= nums[counter];
expression[i] += 1;
break;
case 3:
curr_sum /= nums[counter];
expression[i] -= 1;
dfs(nums,expression,max_,min_,curr_sum,counter+1);
curr_sum *= nums[counter];
expression[i] += 1;
break;
}
}
}
}
void Solution(){
int max_ = INT_MIN;
int min_ = INT_MAX;
int curr_sum = nums[0];
dfs(nums,expression,max_,min_,curr_sum,1);
cout << max_ << ' ';
cout << min_ << ' ';
}
void Solve(){
Input();
Solution();
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("input.txt", "r", stdin);
Solve();
return 0;
}
원래는 항상 캡쳐했는데 이렇게 올리는것도 꽤 괜찮은거같다. 분명 내 구성은 완벽했는데 원하는 답이 안나왔었는데 이유가 current_sum 을 call by referenc (&) 방식으로 넣었어서 이상한 답이 나왔었다. 이런 자잘한 실수를 줄여야하는데 한참 멀은거같다. 0, 1, 2, 3 은 swtich 와 case 로 다뤄줬으면서 나쁘지 않은 코드였던거같다.
배운점:
1. backtracking 의 원리 잊지말자
2. 자잘한 실수좀 하지말자