인간-컴퓨터 상호작용

문제는 복잡하지만 아무튼 부분합을 구하는 문제이다.

조건이 좀 널널한 버전과, 조건이 빡센 버전 두개가 있다.

널널한 버전

풀이 1

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int q;
char a;
int start, end_num;
string str;

int main() {
    cin >> str;
    cin >> q;
    int ans[q];
    int count;
    for (int i = 0; i < q; i++) {
        cin >> a >> start >> end_num;
        count = 0;
        for (int j = start; j <= end_num; j++) {
            if (str[j] == a) count++;
        }
        ans[i] = count;
    }
    for(int i =0; i < q; i++) {
        cout << ans[i] <<"\n";
    }
}

단순하게 해당 구간을 빙빙 돌면서 그 안에 있는 a들의 수를 전부 카운팅한다.

풀이2

원래 2번째 케이스를 풀어보려고 준비한건데, 타임아웃이 나는건지 70%쯤에서 아예 풀리지가 않는다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int q;
int sum[222222];
char a;
char prev_char = 'K';
int start, end_num;
string str;

int main() {
    cin >> str;
    cin >> q;

    int ans[q];
    for (int i = 0; i < q; i++) {
        cin >> a >> start >> end_num;
        bool flag = true;
        if (prev_char == a)  flag = false;
        prev_char = a;
        if (i == 0) {
            if (str[0] == a) sum[0] = 1;
            else sum[0] = 0;
            for (int i = 1; i <= str.size(); i++) {
                if (str[i] != a) sum[i] = 0 + sum[i-1];
                else sum[i] = 1 + sum[i-1];
            }
        } else if (flag){
            if (str[0] == a) sum[0] = 1;
            else sum[0] = 0;
            for (int i = 1; i <= str.size(); i++) {
                if (str[i] != a) sum[i] = 0 + sum[i-1];
                else sum[i] = 1 + sum[i-1];
            }
        }
        ans[i] = sum[end_num] - sum[start-1];
    }
    for(int i =0; i < q; i++) {
        cout << ans[i] <<"\n";
    }
}

구조는 다음과 같다.

1. 입력받은 문자를 prev와 비교해서 같으면 flag를 true로 유지하고 아니면 false 처리한다.

2. 첫번째 경우는 일단 무조건 한번 실행한다.

2-1 문자가 a와 똑같으면 sum[i] = 1 + sum[i-1];
만약 다르다면 0 + sum[i-1]이다.

3. 그 다음 입력문자들은 flag에 맞춰서 처리한다.

4. 결과를 출력한다

아직까지 어디가 틀려서 이게 안되는지 모르겠다. 중복되면 for문 안돌도록 설정까지 해줬는데

정답

https://doorrock.tistory.com/53?category=921017

이렇게 풀어서 내니깐 일단 답은 나온다.
언젠가는 꼭 일차원 배열로 풀어보고싶은데
아마 이차원배열은 입력값이 abcde가 나와도 그냥 for문 한번만 돌면 되는데,

일차원배열을 쓰면 abcde마다 계속 돌려야해서 그런것같다.