[코드트리 조별과제] Preprocessing

시간을 줄일 수 있는 방법중 하나로 설명되는 전처리이다.

전처리라는 단어의 의미와 같이 입력받은 데이터에 대해 선제적으로 처리하여 완전탐색을 피할 수 있도록 하는 방법이다.

 

문제 1) 괄호 쌍 만들어주기

단순 모든 경우의 수를 탐색하면 모든 인덱스를 탐색하면서 여는 괄호가 두개인 시작점을 찾고, 닫는 괄호가 두개인 끝 점을 전부 찾아서 해야된다. 이는 (((()))), (())(())와 같은 경우가 최악의 경우로 생각할 수 있는데, ((을 잡고 ))을 찾기위해 모든 인덱스를 탐색하는 과정에서 시간복잡도는 O(N^2)가 나오게 된다.

 

sol1) 누적합 응용 전처리

누적합의 대상을 특정 인덱스 오른쪽의 ))의 개수로 한다.

 

( ( ) ) ( ( ) ) ( ( ) ) 와 같은 예시가 있다고 하자.

인덱스의 역순으로 ))의 누적 개수를 채우면

3 3 3 2 2 2 2 1 1 1 1 0 이 된다.

((와 ))가 쌍을 이루므로 처음 입력받은 문자열을 순차적으로 탐색하며 ((가 나올 경우 누적 개수를 전체 정답에 합해주면 된다.

 

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
string a;
queue<int>b1, b2;
long long ans;
int main() {
    cin>>a;
    for(int i=1; i<a.size(); i++) {
        if(a[i] == '(' && a[i-1] == '(')
            b1.push(i);
        if(a[i] == ')' && a[i-1] == ')')
            b2.push(i-1);
    }
    while(!b1.empty()) {
        int cur = b1.front(); b1.pop();
        while(b2.front() < cur && !b2.empty()) {
            b2.pop();
        }
        if(b2.empty())
            break;
        ans += b2.size();
    }
    cout<<ans;
    return 0;
}

 

나는 ((와 ))가 발생하는 경우의 인덱스를 전부 저장하고 )) queue의 front가 ((의 인덱스보다 작다면 빼주고 )) queue의 size를 더하는 방식으로 구현하였다.

 

 

문제 2) 이상한 폭탄

특정 번호를 가진 폭탄이 가장 최근 어느 인덱스에 입력이 들어왔는지 미리 체크해놓으면 된다.

폭탄은 무조건 순서대로 들어오고, K 거리 이내에 있는 같은 번호를 가진 폭탄들은 무조건 가장 최근 들어온 폭탄과 연관이 된다.

그러므로 가장 최근 들어온 같은 번호의 폭탄을 체크하고, K 이하인지 확인하면 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int N, K, bomb[1000001], ans;
int main() {
    cin>>N>>K;
    for(int i=1; i<=N; i++) {
        int bnum; cin>>bnum;
        if(!bomb[bnum]) bomb[bnum] = i;
        else if(i - bomb[bnum] <= K) ans = max(ans, bnum);
        else bomb[bnum] = i;
    }
    if(!ans) cout<<-1;
    else cout<<ans;
    return 0;
}

 

문제 3) 최소 에너지 비용

그리디 느낌의 풀이를 요구하는 문제이다.

특정 지점에 도달하기 위한 최소 코스트는 특정 지점 이전에 있는 다른 지점들 중에 가장 작은 코스트를 가진 지점에서 에너지를 채워 가져오는 방법이다.

그러므로 특정 지점에 해당하는 인덱스에 특정 지점까지의 모든 지점의 최소 코스트를 저장하고, 모든 지점 사이의 에너지 값을 곱해주면 된다.

 

#include <iostream>
using namespace std;

long long N, energy[100001], cost[100001], dp[100001], ans;
int main() {
    cin>>N;
    for(int i=0; i<N-1; i++) cin>>energy[i];
    for(int j=0; j<N; j++) cin>>cost[j];
    dp[0] = cost[0];
    for(int i=1; i<N-1; i++) {
        dp[i] = min(cost[i], dp[i-1]);
    }
    for(int i=0; i<N-1; i++) {
        ans += energy[i]*dp[i];
    }
    cout<<ans;
    return 0;
}