백준 13701번 중복 제거

문제 링크입니다: https://www.acmicpc.net/problem/13701

http://donggod.tistory.com/54을 참고하였습니다.

메모리 제한이 다른 문제들과는 달리 고작 8MB이기 때문에 배열, 벡터, 링크드리스트와 같은 자료구조는 모두 사용할 수 없는 문제였습니다.

따라서 비트를 사용해야 했는데 int는 32비트이므로 비트를 최대 32개 사용할 수 있고 8MB(2^3 * 2^20)는 2^23이기 때문에 비트마스크를 이용해야지만 풀 수 있는 문제였습니다.

#include <cstdio>

//#include <iostream>

//using namespace std;

 

//c++는 헤더파일이 무거우므로 실행시간 면에서 불리

//cout, cin으로 코드 작성할 경우 시간초과

 

int arr[(1 << 25) / 32]; //8MB = 2^25, int는 32비트

 

int main(void)

{

        int num;

        //-1은 4바이트에서 비트로 표현하면 0xFFFFFFFF인데,

        //이를 비트 반전 시키면 0x00000000,

        //다시 말해 ~scanf("%10s", s)에서 입력이 더 이상 들어오지 않을 경우 0

        while (~scanf("%d", &num))

        {

               int quotient = num / 32; //int는 32비트

               int remainder = 1 << (num % 32); //나머지

 

               //몫을 배열의 인덱스

               //나머지를 해당 인덱스의 값

               if (!(arr[quotient] & remainder))

               {

                       arr[quotient] += remainder;

                       printf("%d ", num);

               }

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~