< 백준 BaekJoon : 10815번 숫자 카드 > C++

<<문제>>

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

<<풀이>>

상근이는 숫자를 N개 가지고 있고 M개의 숫자를 입력받아 같은 숫자를 상근이가 가지고 있는지 비교하는 문제.

 

자칫 입력받은 숫자 M개의 반복문에 상진이의 숫자 N개를 반복문으로 돌려 비교할 수 있는데,

이렇게 할 경우 숫자가 매우 커지면 메모리의 소모가 커지기에 문제가 해결되지 않는다.

↓ 잘못된 예시

int main(){
  int numN;
  scanf("%d", &numN);
  int* arrN = new int[numN];
  for(int i=0; i<numN; i++){
    scanf("%d", &arrN[i]);
  }

  int numM;
  scanf("%d", &numM);
  int* arrM = new int[numM];
  for(int i=0; i<numM; i++){
    scanf("%d", &arrM[i]);
  }

  bool isTrue;
  for(int m=0; m<numM; m++){
    isTrue = false;
    for(int n=0; n<numN; n++){
      if(arrN[n] == arrM[m]){
        isTrue = true;
      }
    }
    if(isTrue == true){printf("%d ", 1);}
    else{printf("%d ", 0);}
  }
  delete[] arrN;
  delete[] arrM;
}

본인은 -10,000,000 ~ 10,000,000 범위를 나타내는 20,000,001개 크기의 배열에

상근이가 가진 숫자에 해당하는 배열위치에 1, 아닌 숫자는 0을 저장하여

추후 입력받은 숫자에 해당하는 위치가 1이면 1을 출력, 아니면 0을 출력하게 했다.

 

<<코드>>

#include<stdio.h>

/*
  BaekJoon_10815 숫자 카드
  상근 숫자 n개 가짐, 정수 m개 가짐
  -10,000,000 ~ 10,000,000 범위를 나타내는
  20,000,001개 크기의 배열에 상근이가 가진 숫자에 해당하는 배열위치에 1, 아닌 숫자는 0을 저장
  추후 입력받은 숫자에 해당하는 위치가 1이면 1을 출력, 아니면 0을 출력
*/

int main(){

  // -10000000 ~ 10000000로 생각
  int* arrSG = new int[20000001]();
  
  int numN;
  scanf("%d", &numN);
  int tempNum;
  for(int i=0; i<numN; i++){
    scanf("%d", &tempNum);
    tempNum += 10000000;
    arrSG[tempNum] = 1;
  }

  int numM;
  scanf("%d", &numM);
  for(int i=0; i<numM; i++){
    scanf("%d", &tempNum);
    tempNum += 10000000;
    if(arrSG[tempNum] == 1){
      printf("%d ", 1);
    }
    else{
      printf("%d ", 0);
    }
  }

  delete[] arrSG;
}

 

<<깃헙>>

https://github.com/J2on/BaekjoonOnlineJudge/blob/master/V2/BaekJoon_10815.cpp

GitHub - J2on/BaekjoonOnlineJudge: My Study