백준 알고리즘, 11723 문제

---

이 문제는 비트연산자를 다루기 위한 문제이다.

까다로운 시간 제한 조건 때문에 풀어내고도 애를 먹었다.

시간 제한 조건을 맞추기 위해서 게시할 코드는 이 곳 을 상당부분 참고하였다.

1. cin, cout --> scanf, printf --> gets, puts

c++ 을 사용하면서 cin, cout 에 어느덧 익숙해졌지만, 이런 시간제한이 까다로운 문제에서는, 더군다나 반복된 입출력이 빈번히 등장한다면

cin, cout 은 상당한 시간을 잡아먹는다.

그래서 scanf, print 로 바꾸었으나.. 그마저도 문제가 되어 puts 로 바꾸었다.

printf 의 자료형에 맞게 파싱해주는 내부 구현이 상당한 시간을 잡아먹을 수 있다.

2. 함수의 호출

strcmp 함수를 초기에 호출하여 에러 핸들링 하려 했으나, 통과한 방법에 비해 2~3 번의 호출이 더 발생한다는 점 때문에 시간 제한에 통과하지 못했다.

또한, 분기마다 반복되는 x--; 와 x 의 validation 코드를 함수로 빼내었지만.. 이마저도 시간제한에 걸리고 말았다.

함수의 호출간에 stack 에 일어나는 어셈블리단에 과정들은 역시 무시하면 안된다.

3. for 문

처음에 add, remove 를 함수로 구성하여 all 호출 시 for 문을 통하여 20번의 add 를 호출해주려고 했다.

당연히 되는 방법이고, 간단히 해결했지만

역시나 시간제한에 걸리고 말았다.

총체적인 문제였다.

add, remove 를 함수로 구성한 것도 문제였고, for 문을 고작 20번 돌리겠다는 그 생각도 문제였다.

for( i = 1 to 20 ) {
    add(x);
}

// 시간 초과!!

만약  수십만, 수백만, 수억개의 데이터를 다뤄야 한다면 이렇게 for 문으로 수억개를 순회할 것 인가?

짜놓고 보니 한심한 코드였다.

    S = (1 << 20) - 1;

비트연산자를 활용한 이 한줄로 내가 하고자 했던

S 집합에 1 부터 20 까지 담는 일이 해결된다.

1 을 오른쪽으로 20번 이동하면 

    1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

여기서 1 을 빼주면

결과는 FFFFF 로 2진수로 표현하면 1 이 20개 있는 모습이 된다.

이 표현을 S 집합에 1 부터 20 까지 모두 차있다는 의미가 된다.

---

/**
 * @site: https://www.acmicpc.net/problem/11723
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 07. 13
 */

#include 
#include 

using namespace std;

int S, x;           // S is set of result

int main() {
    int i, M;           // M is test_case
    char op[10];        // operator

    // cin >> M;
    scanf("%d", &M);

    if( M < 1 || M > 3000000) {
        cout << "Input Error.." << endl;
        return -1;
    }

    while(M--) {
        scanf("%s", op);
        
        if(!strcmp(op, "add")) {
            scanf("%d", &x);
            x--;
            S |= (1 << x);
        }
        else if(!strcmp(op, "remove")) {
            scanf("%d", &x);
            x--;
            S = (S & ~(1 << x));
        }
        else if(!strcmp(op, "check")) {
            scanf("%d", &x);
            x--;
            int isExist = (S & (1 << x));
            if(isExist) {
                puts("1");
            }
            else puts("0");
        }
        else if(!strcmp(op, "toggle")) {
            scanf("%d", &x);
            x--;
            S ^= (1 << x);
        }
        else if(!strcmp(op, "all")) {
            S = (1 << 20) - 1;
        }
        else if(!strcmp(op, "empty")) {
            S = 0;
        }
        else {
            printf("Input Error..\n");
        }

    }

    return 0;
}

반복되는 일부 코드들이 참 거슬리지만

함수를 사용하지 않기 위해...

더 좋은 방법이 있는지 고민해볼 필요는 있다.