[ 백준 5676 ] 음주코딩 (C++)

백준의 음주코딩(5676) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

본인은 이 문제를 'Segment Tree'를 이용해서 구현하였다. 구간에 대한 연산이 필요한 문제이고, 명령어가 떨어질 때 마다 해당 구간에 대한 연산을 하나하나 한다고 가정한다면, 최악의 경우 N = 10^5 , K = 10^5 이 주어진다면 연산을 10^5 x 10^5 만큼 해야하는 경우가 발생한다. 당연히 제 시간내에 문제를 해결할 수 없을 것이다.

따라서 구간에 대해서 보다 효율적인 자료구조인 'SegmentTree'를 이용해서 접근해 보았다.

아직 SegmentTree에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ SegmentTree 알아보기 (Click) ]

위에 걸려있는 SegmentTree에 대한 설명글은 '구간합'에 대한 연산을 기준으로 설명이 되어있다.

이제 이 부분을 문제에 맞게 바꿔보도록 하자.

먼저, 본인은 세그먼트 트리에 주어진 배열의 실제 값들을 저장하지 않았다. 왜냐하면 정답으로 출력해야 하는 것이 정확한 값이

아닌 음수인지 양수인지 0인지 이 3가지 경우만 판단을 해주면 되기 때문이다.

따라서, 세그먼트 트리에 배열의 실제 값과 구간에 대한 연산 결과값을 저장하는 것이 아니라 음수/양수/0인지 판단할 수 있도록

-1 / 1 / 0 의 값을 넣어주었다.

예를 들어서 { -10 , 10 , 20 } 이라는 배열이 있다. 여기서 배열의 1번 값부터 2번 값 까지의 곱이 음수/양수/0 인지 판단하라고

했을 때, 꼭 -10 x 10을 해야지만 그 값이 음수라는 것을 확인할 수 있을까 ?? 아니다. 본인이 위에서 말했듯이 위의 배열을

{ -1 , 1, 1 } 로 표현하더라도, -1 x 1 은 음수라는 것을 확인할 수 있다. 따라서 본인은 음수 = -1 , 양수 = 1, 0 = 0 으로 세그먼트

트리에 값을 저장해 주었다.

또한 구간에 대한 곱을 구할 때, 제 범위가 아닌 경우에는 곱셈의 항등원인 '1'을 return 시켜주면 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N, K;
int Arr[MAX];
vector<int> SegmentTree;
vector<pair<char, pair<int, int>>> Cmd;
vector<char> Answer;
 
void Initialize()
{
    SegmentTree.clear();
    Cmd.clear();
    Answer.clear();
}
 
void Input()
{
    for (int i = 0; i < N; i++) cin >> Arr[i];
    for (int i = 0; i < K; i++)
    {
        char C; cin >> C;
        int a, b; cin >> a >> b;
        Cmd.push_back(make_pair(C, make_pair(a, b)));
    }
}
 
int Invert(int x)
{
    if (x == 0) return 0;
    else if (x < 0) return -1;
    else if (x > 0) return 1;
}
 
int Make_SegmentTree(int Node, int Start, int End)
{
    if (Start == End) return SegmentTree[Node] = Invert(Arr[Start]);
    
    int Mid = (Start + End) / 2;
    int Left_Result = Make_SegmentTree(Node * 2, Start, Mid);
    int Right_Result = Make_SegmentTree(Node * 2 + 1, Mid + 1, End);
 
    return SegmentTree[Node] = Invert(Left_Result * Right_Result);
}
 
int Update(int Node, int Start, int End, int Idx, int Value)
{
    if (Idx < Start || Idx > End) return SegmentTree[Node];
    if (Start == End) return SegmentTree[Node] = Invert(Value);
    
    int Mid = (Start + End) / 2;
    int Left_Result = Update(Node * 2, Start, Mid, Idx, Value);
    int Right_Result = Update(Node * 2 + 1, Mid + 1, End, Idx, Value);
 
    return SegmentTree[Node] = Invert(Left_Result * Right_Result);
}
 
int Query(int Node, int Start, int End, int Left, int Right)
{
    if (Right < Start || Left > End) return 1;
    if (Left <= Start && End <= Right) return SegmentTree[Node];
    
    int Mid = (Start + End) / 2;
    int Left_Result = Query(Node * 2, Start, Mid, Left, Right);
    int Right_Result = Query(Node * 2 + 1, Mid + 1, End, Left, Right);
    return Invert(Left_Result * Right_Result);
}
 
void Solution()
{
    int Tree_Height = (int)ceil(log2(N));
    int Tree_Size = (1 << (Tree_Height + 1));
    SegmentTree.resize(Tree_Size);
    Make_SegmentTree(1, 0, N - 1);
 
    for (int i = 0; i < Cmd.size(); i++)
    {
        char C = Cmd[i].first;
        if (C == 'C')
        {
            int Index = Cmd[i].second.first - 1;
            int Value = Cmd[i].second.second;
            Update(1, 0, N - 1, Index, Value);
        }
        else
        {
            int Index = Cmd[i].second.first - 1;
            int Index2 = Cmd[i].second.second - 1;
            int Result = Query(1, 0, N - 1, Index, Index2);
 
            if (Result == 0) Answer.push_back('0');
            else if (Result < 0) Answer.push_back('-');
            else Answer.push_back('+');
        }
    }
    for (int i = 0; i < Answer.size(); i++) cout << Answer[i];
    cout << endl;
}
 
void Solve()
{
    while (cin >> N >> K)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}