[BOJ 5875 오타 c++] 자료구조 누적 합

문제

 

풀이

좀 조건이 까다로웠다.

 

( +1

) -1

로 놓고 생각했다.

순차적으로 해당 위치를 반대 괄호를 바꿨을 때 불가능한 경우를 생각해보면 (단, 한번의 오타만 냈다는 조건이 중요하다)

1. 양끝단 검사. 맨 앞은 ( , 맨 뒤는 ) 이어야한다.
2. 최종적으로 ( ) 개수가 같아야하므로 맨 끝에 합이 0 나와야한다.
3.  ( → )  : 해당 위치에서  ~ 맨 끝에 음수가 있는지 확인. 
4.  ) → (  : 해당 위치에서 앞 부분에 음수 있는지 확인.
   1. ( ) ) ( ( )  이 케이스를 생각해보면 된다. 

 

1차 코드

#include <iostream>

#define MAX_N 100001
using namespace std;

string str;
int arr[MAX_N];
int sum[MAX_N];
int len;

bool possible(int idx, int num) {
	if (!idx && num == -1) // 맨 앞에 ) 
		return false;
	if (idx == len - 1 && num == 1) //맨 뒤 (
		return false;
	if (sum[len - 1] + num * 2 != 0) return false;


	if (num == -1) { // '(' -> ')'
		// 뒷 부분 음수 되는지 검사 
		for (int i = idx; i < len; i++) {
			if (sum[i] + num * 2 < 0) 
				return false;
		}
	}
	else {  // ')' -> '('
		if (sum[idx] + num * 2 < 0) 
			return false;

		// ())(() 경우를 위해 앞부분 음수 검사
		for (int i = idx-1; i >= 0; i--) {
			if (sum[i] < 0) return false;
		}
	}

	return true;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> str;
	len = str.size();

	for (int i = 0; i < len; i++) {
		if (str[i] == '(') sum[i] = arr[i] = 1;
		else sum[i] = arr[i] = -1;
		if (i) sum[i] += sum[i - 1];
	}

	int ans = 0;
	for (int i = 0; i < len; i++) {
		if (possible(i, -arr[i])) 
			ans++;
	}

	cout << ans;
	return 0;
}

아무래도 시간이 좀 오래걸린다.

 

 

다른 분 코드

#include <bits/stdc++.h>
using namespace std;
string str;
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> str;
    int ans = 0;

    int sum = 0;
    int left = 0, right = 0;

    for (char c : str) {
        if (c == '(') {
            sum++; left++;
        }
        else if (c == ')') {
            sum--; right++;
        }

        if (sum <= 1) //위반되는 조건의 위치만 생각 
            left = 0;
        if (sum == -1) {
            ans = right;
            break;
            //유효하지 않은 순간 발생
            //유효하지 않은 곳은 한 곳이니 아기 앞부분을 고쳐야한다.
        }      
    }
    if (sum > 0) ans = left; 
    //개수 위반되는 (
    // 위반 되는 조건은 1초과인 순간 
    cout << ans;
}

훨씬 간단.