[BOJ] 백준 20936 - 우선순위 계산기 (SUAPC 2021 Winter)

문제 링크

www.acmicpc.net/problem/20936

20936번: 우선순위 계산기

 

풀이

우선순위 큐를 이용한 구현 문제입니다.

사실 복잡한 구현 문제라 이해하기 쉽게 쓰기 힘들어 보여 귀찮아서 안 쓰려했는데.. 그래도 써야죠...

역시 알고리즘 문제는 푸는 것보다 설명하는 게 더 힘듭니다..

 

전체적인 풀이

1) $X_1\ Op_1\ X_2\ Op_2\ X_3\ Op_3\ ...\ Op_{n-1}\ X_n$ 꼴의 수식이 공백 없이 주어집니다. 이를 적절히 처리하여 $X$와 $Op$를 따로 저장해줍니다. 제 코드에서 수는 $p$ 배열에, 연산자는 $op$ 배열에 저장했습니다. (line 62 ~ 71)

 

2) 각 $X_i\ Op_i\ X_{i+1}$ 들을 모두 연산하여 우선순위 큐에 넣어줍니다. (line 76 ~ 79)

저는 우선순위 큐의 자료형을 따로 정의한 Node 타입으로 선언했습니다.

Node 구조체는 두 수의 연산 결과, 연산자 우선 순위, 왼쪽 피연산자의 인덱스, 오른쪽 피연산자의 인덱스를 멤버로 가지고, 그에 따라 비교 함수를 적절히 재정의합니다. (line 9 ~ 24)

 

3) 우선순위 큐에서 뽑은 두 수의 연산이 현재 시점에서 유효한 연산인지 확인합니다. 만약 유효하다면 연산 후 새로운 연산 결과를 큐에 넣어주고, 그렇지 않다면 무시합니다. (line 80 ~ 106)

 

유효한 연산인지 확인하기

아마 3번 단계에서 연산이 유효한지 판단하는 부분이 막혀 검색해보셨으리라 생각합니다.

 

저는 앞으로 연결된 유니온 파인드, 뒤로 연결된 유니온 파인드를 각각 관리하여 두 수가 이미 연산에 사용됐는지 확인했습니다. 앞으로 연결되었다는 말은 왼쪽 인덱스를 부모로, 뒤로 연결됐다는 말은 오른쪽 인덱스를 부모로 가진다는 말입니다. 사실상 수를 링크드 리스트로 관리하며 왼쪽, 오른쪽을 이어준다고 생각하면 이해하기 쉽습니다. 앞쪽으로 연결된 유니온 파인드를 $F$, 뒤로 연결된 유니온 파인드를 $B$라고 합시다.

 

항상 이웃한 수끼리 연산하기 때문에 이미 함께 연산된 수들을 한 구간으로 관리할 수 있고, $F$를 이용해 구간의 가장 왼쪽 인덱스를, $B$를 이용해 구간의 가장 오른쪽 인덱스를 빠르게 구할 수 있습니다.

그리고 각 구간의 양쪽 끝에는 가장 최근에 계산된 값을 넣어주도록 합시다.

 

 

판단을 위한 빌드업이 끝났습니다. 다음 규칙대로 유효한 연산인지 확인하면 됩니다.

1) 우선순위 큐에는 (계산된 값, 연산자 우선순위, 구간의 왼쪽 끝 인덱스, 구간의 오른쪽 끝 인덱스)가 들어갑니다. 이 쌍을 앞으로 노드라 합시다. 이때 왼쪽 인덱스, 오른쪽 인덱스는 항상 인접합니다.

 

2) 큐에서 뽑은 노드의 왼쪽 인덱스를 $l$, 오른쪽 인덱스를 $r$이라 합시다. 그리고 $F(i), B(i)$를 각각 인덱스 $i$가 속한 구간의 가장 왼쪽 인덱스, 오른쪽 인덱스라고 합시다.

 

2-1) $l \neq B(l)$ 이거나, $r \neq F(r)$ 이면 유효하지 않은 노드입니다.

어떤 구간의 양 끝이 아닌 수들은 이미 서로 계산된 수이고, 노드는 인접한 두 수의 인덱스를 갖고 있습니다. 즉, 이 노드가 유효하려면 두 수가 서로 다른 그룹이어야 하며, $l$은 그 구간의 가장 오른쪽, $r$은 그 구간의 가장 왼쪽이어야 한다는 말입니다.

따라서 위 조건을 만족한다면 $l$, $r$이 서로 다른 구간에 속하면서 아직 계산되지 않았다고 볼 수 있습니다.

 

2-2) 현재 시점에서 갱신된 $l$, $r$값을 이용해 다시한번 계산했을 때, 노드에 들어있는 계산 값과 같아야 유효합니다.

 

$1 - 2 + 3$ 을 예로 들어봅시다. 큐에 들어간 정보를 (계산된 값, $l$ 인덱스, $r$ 인덱스)라고 합시다. 편의상 인덱스는 1부터 세겠습니다.

 

처음엔 [ (5, (2, 3)), (-1, (1, 2)) ] 가 큐에 들어가게 됩니다.

2+3이 가장 큰 값이므로 2+3을 계산하고, 큐에 다시 (-4, (1, 2))를 넣습니다.

 

큐에는 [ (-1, (1, 2)), (-4, (1, 2)) ]가 들어있고, 우선순위에 따라서 (-1, (1, 2))를 뽑습니다. 

2번, 3번 인덱스가 한 구간으로 잡혔고, 각 구간의 양쪽 끝 값은 가장 최근에 계산된 값으로 갱신되기 때문에 2번 인덱스의 값은 5입니다. 현재 갱신된 값으로 다시 (1, 2)를 계산하면 이번에 뽑은 노드의 값인 -1과 다르기 때문에 이는 유효하지 않은 노드라고 판단할 수 있습니다.

 

3) 인접한 두 수를 계산하고 새로운 그룹으로 묶어주었을 때, 양 끝 구간이 $1, n$이 되면 종료합니다.

 

 

그림으로 알아보자

위 규칙을 생각하며 다음 예제를 시뮬레이션해봅시다.

$1 * 1 - 3 + 4 * 5 - 7$

각 단계에서 새로 갱신된 정보들을 파란색으로 표시합니다.

 

 

1) 초기상태입니다. 인접한 수들의 연산 결과를 우선순위 큐(PQ)에 넣어줍니다.

 

2) (4, 5)를 한 구간으로 묶어주고, 구간의 양 끝 인덱스를 새로 계산된 값으로 갱신해줍니다.

그 후 갱신된 값을 이용한 (3, 4), (5, 6)의 새로운 연산 결과를 큐에 넣어줍니다.

 

3) 위와 같은 과정을 거칩니다.

 

4) 위와 같은 과정을 거칩니다.

 

5) 이번에 뽑은 노드는 [13, (5, 6)]인데, (5, 6)이 규칙 2-1($l$, $r$이 서로 다른 구간)을 만족하지 않습니다.

[7, (3, 4)] 또한 같은 이유로 넘어가 줍시다.

 

6) (1, 2)를 구간으로 묶어주고 갱신된 값을 이용하여 (2, 3)의 연산 결과를 큐에 넣어줍니다.

 

7) 이번에 뽑은 [1, (2, 3)]은 규칙 2-1을 만족하지만 규칙 2-2(최근에 갱신된 값의 연산 결과와 같아야 함)를 만족하지 않습니다.

같은 이유로 [-14, (2, 3)] 또한 넘어가 줍니다.

 

8) 규칙 3에 따라 종료합니다.

정답 코드

#include <bits/stdc++.h>
#define ft first
#define sd second
#define mem(v, e) memset((v), (e), sizeof((v)))
using namespace std;
using ll = long long;
using vll = vector<ll>;

struct Node {
    ll val;
    int op, l, r;

    Node(ll v, int op, int l, int r) : val(v), op(op), l(l), r(r) {}

    tuple<ll, int, int, int> toTuple() {
        return {val, op, -l, -r};
    }
};

struct cmp {
    bool operator()(Node &a, Node &b) const {
        return a.toTuple() < b.toTuple();
    }
};

ll f[222'222], b[222'222];
priority_queue<Node, vector<Node>, cmp> q;

int n;
int findFront(int x) {
    if (f[x] < 0) return x;
    return f[x] = findFront(f[x]);
}

int findBack(int x) {
    if (b[x] < 0) return x;
    return b[x] = findBack(b[x]);
}

ll calc(ll x, ll y, char op) {
    if (op == '+') return x + y;
    else if (op == '-') return x - y;
    else if (op == '*') return x * y;
    else return x / y;
}

int opToBool(char op) {
    return op == '*' || op == '/';
}

vll p;
vector<char> op;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    mem(f, -1);
    mem(b, -1);
    for (ll i = 0, val = 0; i < s.size() + 1; i++) {
        if (isdigit(s[i])) {
            val = val * 10 + (s[i] - '0');
        } else {
            p.push_back(val);
            n++;
            val = 0;
            if (i < s.size()) op.push_back(s[i]);
        }
    }
    if (n == 1) {
        cout << p[0];
        return 0;
    }
    for (int i = 0; i < n - 1; i++) {
        ll u = p[i], v = p[i + 1];
        q.emplace(calc(u, v, op[i]), opToBool(op[i]), i, i + 1);
    }
    while (!q.empty()) {
        auto[val, _, u, v] = q.top();
        q.pop();

        if (u != findBack(u) || v != findFront(v)) continue;
        ll res = calc(p[u], p[v], op[u]);
        if (res != val) continue;
        f[v] = u;
        b[u] = v;
        u = findFront(u);
        v = findBack(v);
        p[u] = p[v] = res;
        if (u == 0 && v == n - 1) {
            cout << res;
            return 0;
        }
        if (u > 0) {
            int prev = u - 1;
            res = calc(p[prev], p[u], op[prev]);
            q.emplace(res, opToBool(op[prev]), prev, u);
        }
        if (v < n - 1) {
            int next = v + 1;
            res = calc(p[v], p[next], op[v]);
            q.emplace(res, opToBool(op[v]), v, next);
        }
    }
}