BOJ 32074. XOR 최대

 

문제 링크

 

문제 풀이

 이 문제는 어떤 0과 1로만 구성된 문자열이 주어질 때 그 문자열의 서로 다를 필요는 없는 부분 문자열끼리 XOR연산을 한 값의 최댓값을 출력하는 문제이다. 여러개의 테스트 케이스로 주어지고, 이때 주어지는 모든 문자열의 길이의 합은 $10^7$을 넘지않아서 $O(N)$풀이가 필요하다. 

 

 문제를 처음봤을 때 아이디어가 바로 떠올라서 플레4보단 쉽다고 느꼈는데, 구현을 해볼 수록 고려해야할 게 많다는 것을 깨달았다. 생각한 아이디어는 앞의 나오는 자릿수 중에 1이 많으면 좋으므로, 처음에 나오는 연속한 1들과 그 다음 나오는 0들을 XOR하는 것이었다. 예를 들어 11100010이라는 문자열이 주어지면 11100010과 11100을 XOR하여 앞의 0들을 모두 1로 만들어주어 숫자를 키울 수 있다. 하지만 1110010과 같은 경우는 1110010과 1110을 XOR하는 것보다 1110010과 1101을 XOR하는 것이 더 크다. 이런 경우에는 앞의 연속한 1의 개수와 바로 다음으로 연속한 0의 개수를 비교하여 적절히 처리를 해주어야한다.

 

 그래서 전체적인 풀이로는 문자열을 입력 받았을 때 그 문자열에서 최초로 등장하는 연속한 1들 인덱스와, 그 바로 다음으로 등장하는 연속한 0들의 인덱스를 저장해주고 최대한 앞쪽에서 0과 1이 XOR될 수 있게 해주면 된다. 그리고 예외적으로 111과 같은 경우는 무조건 1과 1이 XOR되는 경우가 발생할 수 밖에 없어서 맨 앞쪽에 0이 존재하지 않는 경우로 예외처리를 해주었다.

 

 

 

코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int NMAX = 10000001;

char XOR(char c1, char c2){
    if(c1 == c2) return '0';
    else return '1';
}

void solve(){
    int length;  cin>>length;
    string s;    cin>>s;
    
    int firstOneIdx = NMAX, lastOneIdx = NMAX;
    int firstZeroIdx = NMAX, lastZeroIdx = NMAX;
    bool isZeroExist = (s[0] == '0');
    
    for(int i=0;i<length;i++){
        if(firstOneIdx == NMAX){
            if(s[i] == '0') continue;
            else firstOneIdx = i;
        }
        if(lastOneIdx == NMAX){
            if(i == length - 1) lastOneIdx = i;
            else if(s[i+1] == '0'){
                lastOneIdx = i;
                firstZeroIdx = i+1;
            }
            else continue;
        }
        if(lastZeroIdx == NMAX){
            if(i == length - 1) lastZeroIdx = i;
            else if(s[i+1] == '1'){
                lastZeroIdx = i;
            }
            else continue;
        }
    }
    
    if(firstOneIdx == NMAX) cout<<'0'<<"\n";
    else {
        if(firstZeroIdx == NMAX){
            for(int i=firstOneIdx;i<length-1;i++) cout<<s[i];
            if(isZeroExist) cout<<'1'<<"\n";
            else cout<<'0'<<"\n";
        } else {
            for(int i=firstOneIdx;i<=lastOneIdx;i++) cout<<s[i];
            int XORIdx;
            if(lastOneIdx - firstOneIdx <= lastZeroIdx - firstZeroIdx){
                XORIdx = firstOneIdx;
            } else {
                XORIdx = lastOneIdx - (lastZeroIdx - firstZeroIdx);
            }
            for(int i=firstZeroIdx;i<length;i++){
                cout<<XOR(s[i],s[XORIdx]);
                XORIdx ++;
            }
            cout<<"\n";   
        }
    }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    int q; cin>>q;
    for(int i=0;i<q;i++){
        solve();
    }
}