2017 하반기 삼성 SW 역량 테스트 - 연산자 끼워넣기

2018-12-03 00:36:05 | 조회수 5081


2017년 하반기 채용 문제로 나온 연산자 끼워넣기 문제입니다. 이미 SW 역량 테스트 공부를 해보셨던 분들은 아시겠지만, 삼성전자에서는 채용 문제로 완전 탐색, DFS, BFS 문제를 굉장히 많이 출제하고 있는 것을 알 수 있습니다. 어떻게 보면 이 3가지는 비단 알고리즘 문제 뿐만 아니라, 실무에서도 사용할 수 있는 개념이기 때문에 이런 유형의 시험이 많은 것은 나쁘지 않다고 생각합니다.


연산자의 우선순위를 무시하고, 주어진 수 사이에 연산자를 끼워넣어 계산했을 때 나올 수 있는 최댓값과 최솟값을 구하는 문제입니다. 나올 수 있는 숫자는 총 11개이므로 연산자는 10개이고, 나올 수 있는 가장 큰 경우의 수는 각 부호에 대해 $10! / (A_+)!(A_-)!(A_*)!(A_/)!$ 가 됩니다. 그러므로 완전 탐색을 통해 문제를 해결할 수 있음을 알 수 있습니다.


완전 탐색을 하는 방법에는 dfs로 하는 방법과, STL을 이용할 수 있는 환경에서는 next_permutation 이라는 함수를 통해 모든 경우를 다 테스트해볼 수 있습니다. 하단 소스코드에는 next_permutation 으로 푸는 방법을 올려놓았습니다. 추가글로 dfs로 푼 소스코드도 첨부하겠습니다. (추가된 소스를 보려면 하단의 빨간색 버튼을 누르면 됩니다.)


그렇게 해서 모든 경우를 다 따져 최대, 최소를 구하면 됩니다. 여기서 조심해야 되는 경우가 있는데, -10억 ~ 10억 의 값을 가질 수 있으므로 최댓값을 비교하는 변수는 -10억보다 작은 값을 가진 상태에서 시작, 최솟값은 10억보다 큰 값을 가진 상태에서 시작해야 한다는 점입니다.


※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, k, no[11], ari[11], ap = 0, ans1 = -2e9, ans2 = 2e9;

    cin >> n;
    for (int i = 0; i < n; i++) cin >> no[i];
    for (int i = 0; i < 4; i++) {
        cin >> k;
        for (int j = 0; j < k; j++) ari[ap++] = i;
    }
    do {
        int cmp = no[0];
        for (int i = 0; i < ap; i++) {
            if (ari[i] == 0) cmp += no[i + 1];
            if (ari[i] == 1) cmp -= no[i + 1];
            if (ari[i] == 2) cmp *= no[i + 1];
            if (ari[i] == 3) cmp /= no[i + 1];
        }
        ans1 = max(ans1, cmp);
        ans2 = min(ans2, cmp);
    } while (next_permutation(ari, ari + ap));
    cout << ans1 << "\n" << ans2;
}


2017 하반기 삼성 SW 역량 테스트 - 연산자 끼워넣기 - 알고리즘닷컴
32 개의 글