백준 13701 중복 제거

비트마스킹 중에서 무난하게 풀고 자려고 적당한것을 골라봤다.

숫자를 입력받는데, 중복으로 입력된것을 제외하고 주르륵 출력하면 된다.

처음 든 생각은 bool[] 배열을 선언해서 중복이면 true, 중복이 아니면 false 로 체크를 하는 것. bool[] 배열을 사용하는 구현은 정말 쉽게 구현이 되었는데, 바로 메모리 초과가 떴다.

33554432바이트 = 33MB 언저리 이므로 8MB만 허용하는 메모리 용량을 한참 초과한다.

 

처음엔 bool이 당연히 1bit 크기겠지 했는데 아니었다... 그럼 그냥 한 바이트짜리 변수에 각 비트로 표시하자... 는 생각으로 char배열을 선언했다.

그리고 각 배열의 값과 비트는 입력받은 수를 8로 나눈 몫, 8로 나눈 나머지로 사용했다. 최근 본 OS에서 페이징을 볼 때 페이지 번호와 오프셋으로 페이지 안의 주소를 접근한다고 해서 그것과 유사하게 생각한 것 같다.

 

해당 bit가 0이면, 입력받은 숫자를 그대로 출력하게 된다. 만약 1이면 출력하지 않는다.

구현은 되게 간단하다. 메모리 생각을 하고 변수에 값을 우겨넣는 생각만 하면 슬슬 작성할 수 있는것 같다.

---

#include <iostream>
#include <cstring>

int main()
{
    char mask[((1 << 25) / 8)];
    // char mask[10];
    memset(mask, 0, sizeof(mask));
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    while(!std::cin.eof())
    {
        int temp;
        std::cin >> temp;
        int page = temp / 8;
        int offset = temp % 8;
        if (!(mask[page] & (1 << offset)))
        {
            std::cout << temp << " ";
            mask[page] = mask[page] | (1 << offset);
        }
    }
}

 

골드3... 달달하다... 이런 문제만 풀고 싶다... 근데 이런 문제만 풀면 안 늘게 눈에 뻔하다...

비트마스킹은 비트마스킹 말고 다른 문제 유형과 얽어서 난이도를 올리는 것 같다. 조금 어려운것도 잡아봐야겠다.

 

오늘도 평온한 하루가 되길. 슨민.