[백준 10815] C++ - 동적으로 배열 할당하기, 이진 탐색, 입출력 속도 향상

 

🟡틀린 코드

segment error나옴, 배열이 너무 커서 스택 메모리 초과라고 한다.

>> 동적으로 배열 할당해서 해결하기

#//백준 10815 - 숫자 카드
#include <iostream>
using namespace std;

int main(){
  int n, m;
  int have[500000], cards[500000];

  // 상근이가 가지고 있는 숫자 카드 입력
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> have[i];
  }

  // 비교할 카드 입력
  cin >> m;
  int i;
  for(i = 0; i < m; i++){
    cin >> cards[i];

    for(int j = 0; j < n; j++){
      if(have[j] == cards[i]){
        cards[i] = 1;
        break;
      }
      if(j == n-1) cards[i] = 0;
    }
  }

  // 결과 출력
  for(int i = 0; i < m; i++){
    cout << cards[i] << " ";
  }

  return 0;
}

 

🟡틀린 코드

이중 for문으로 시간 초과

>>이진 탐색 이용해서 해결

c++ 기초(동적 배열 할당)

#//백준 10815 - 숫자 카드
#include <iostream>
using namespace std;

int main(){
  int n, m;
  
  // 상근이가 가지고 있는 숫자 카드 입력
  cin >> n;
  int* have = new int[n];
  for(int i = 0; i < n; i++){
    cin >> have[i];
  }

  // 비교할 카드 입력
  cin >> m;
  int* cards = new int[m];
  int i;
  for(i = 0; i < m; i++){
    cin >> cards[i];

    for(int j = 0; j < n; j++){
      if(have[j] == cards[i]){
        cards[i] = 1;
        break;
      }
      if(j == n-1) cards[i] = 0;
    }
  }

  // 결과 출력
  for(int i = 0; i < m; i++){
    cout << cards[i] << " ";
  }

  return 0;
}

 

 

🔵수정 코드 >> 시간 초과

이진탐색하기 전에 정렬하기

#include <algorithm> 필요

[C++] STL 정렬(Sort) 함수

동적 할당 배열인 경우 정렬하는 법

cin >> n;
  int* have = new int[n];
  for(int i = 0; i < n; i++){
    cin >> have[i];
  }

  sort(have, have + n);

[C++]동적할당한 클래스 배열 sort로 정렬하기

#//백준 10815 - 숫자 카드
#include <iostream>
using namespace std;
#include <algorithm>

int main(){
  int n, m, num;
  
  // 상근이가 가지고 있는 숫자 카드 입력
  cin >> n;
  int* have = new int[n];
  for(int i = 0; i < n; i++){
    cin >> have[i];
  }

  sort(have, have + n); // 정렬

  // 이진 탐색
  cin >> m;
  for(int i = 0; i < m; i++){
    cin >> num;

    cout << binary_search(have, have+n, num) << " ";
  }

  return 0;
}

위처럼 binary_search를 사용해도 시간 초과나옴

 

>>입출력 부분 수정

#//백준 10815 - 숫자 카드
#include <iostream>
using namespace std;
#include <algorithm>

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n, m, num;
  
  // 상근이가 가지고 있는 숫자 카드 입력
  cin >> n;
  int* have = new int[n];
  for(int i = 0; i < n; i++){
    cin >> have[i];
  }

  sort(have, have + n); // 정렬

  // 이진 탐색
  cin >> m;
  for(int i = 0; i < m; i++){
    cin >> num;

    cout << binary_search(have, have+n, num) << " ";
  }
  
  delete[] have;
  return 0;
}

 

ios_base::sync_with_stdio(false); 는 c와 c++ 표준 stream의 동기화를 비활성화하기 때문에 입출력 속도가 빨라진다고 한다. 이때는 cin, cout만 사용해야한다.

 

ios::sync_with_stdio(false), cin.tie(0) 쓰는 이유, 백준 시간초과 해결