[백준(BOJ)] 14888번 연산자 끼워넣기 C++

문제 : https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

 

 

 

어떤 문제인가?

n개의 숫자와 n-1개의 연산자를 입력받는다.

그렇게 되면 만들 수 있는 식이 여러 개 생기게 된다.

이때 모든 식을 계산했을 때의 최댓값과 최솟값을 출력하면 된다.

 

특이한 점은 식을 계산할 때 연산자의 우선순위를 고려하지 않고 식의 앞쪽부터 차례대로 계산하는 것이다.

 

 

접근 방법

vector<int> num;
vector<int> oper;
vector<int> ans;

먼저 데이터들을 저장할 벡터를 선언해준다.

 

입력받은 수들을 저장할 num, 연산자들을 저장할 oper, 식의 결과들을 저장할 ans이다.

 

연산자들을 저장하는 벡터의 자료형이 int인 이유는 연산자들을 출력할 필요가 없이

나만 알아볼 수 있으면 되기 때문이다.

 

int n;
cin >> n;

for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    num.push_back(a);
}

 n번만큼 수를 입력받고 num에 추가해준다.

 

for (int i = 0; i < 4; i++) {
    int a;
    cin >> a;
    for (int j = 0; j < a; j++) {
        oper.push_back(i);
    }
}

이제 연산자를 입력받는다.

i가 0일 때는 + 입력 차례,

1일 때는 - 입력 차례,

2일 때는 * 입력 차례,

3일 때는 / 입력 차례이다.

 

그래서 나는 각각의 i를 하나의 연산자라고 생각하기로 했다.

oper에 저장된 0은 +, 1은 -, 2는 *, 3은 /인 것이다.

 

 

 

이 문제 같은 경우는 연산자들을 나열하는 방법인 순열을 사용해야 한다.

따라서 next_permutaion함수를 사용할 것이다.

 

do {

    int total = num[0];

    for (int i = 0; i < oper.size() + 1; i++) {
        switch (oper[i]) {
            case 0:
                total += num[i + 1];
                break;
            case 1:
                total -= num[i + 1];
                break;
            case 2:
                total *= num[i + 1];
                break;
            case 3:
                total /= num[i + 1];
                break;
        }
    }
    ans.push_back(total);

} while (next_permutation(oper.begin(), oper.end()));

do구문에서 반복문을 통해 식의 결과를 구할 것이다.

 

1 + 2 + 3 + 4를 예로 들면

 

1 (+2 )

(1 (+ 2) +3.... 의 순서로 계산을 한다.

따라서 total을 num의 0번 인덱스(식의 첫 번째 수)로 초기화하고 반복문을 통해 계산해나간다.

oper [i]의 값에 따라 연산을 다르게 해주면 된다.

아까 설명했듯이 0은 +, 1은 -, 2는 *, 3은 /인 것을 기억하자.

 

그리고 완성된 total을 ans에 추가해준다.

 

이렇게 모든 반복을 마치게 되면 모든 계산 값들이 ans에 저장되어 있을 것이다.

 

 

sort(ans.begin(), ans.end());

cout << ans.back() << "\n" << ans.front();

우리가 필요한 값은 가장 큰 값과 가장 작은 값이므로 ans벡터를 오름차순으로 정렬해준다.

그다음 ans의 back과 front를 차례대로 출력해주면 끝!

 

무엇이 어려웠는가?

문제를 읽고 순열을 사용해야되는 것을 알아서 크게 어렵지 않았다.

 

식을 계산하는 과정도 연산자의 종류에 따른 간단한 구현문제라서 크게 어렵지 않았다.

 

 

배운 점

문제를 꼼꼼하게 읽자..

사실 처음에는 문제를 대충 어느정도 파악만하고 문제를 풀었다.

 

이 때 푼 방법은,,,, 식의 모든 경우의 수를 중위표기식의 문자열로 바꾼 후 

이 중위 표기식을 또 후위 표기식으로 전환해서 또 후위표기식을 계산하도록했다.

 

실버 1에 왜 이런 문제가 있을까 짜증을 냈지만, 충분히 구현할 수 있을 것 같아서 계속 진행했다.

꽤 오래 걸려서 구현을 마치고 예제 입력을 돌렸을 때야 뭔가 잘못됐음을 깨달았다...

 

굉장히 허무했다..... 문제를 다시 읽으니 진작에 다 풀고 다른 문제를 고민할 시간이었다...

 

또 한 번의 교훈.... 문제를 꼼꼼하게 읽자.

 

 

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%99%84%EC%A0%84%ED%83%90%EC%83%89%20%26%20%EB%B0%B1%ED%8A%B8%EB%9E%99%ED%82%B9/14888.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.