백준 10816번 <숫자 카드 2> -C++

BinarySearch활용문제인 줄 알고 덤볐다가 의외의 복병들에 뚜드려 맞아서 포스팅한댜..

긍까 마지막줄에 입력된 각 원소에 대해서, 두 번째 줄에 몇 개씩 있는 지를 출력하는 문제다

 

한줄요약이라 간단해 보이지? 그랬다면 넌 이걸 직접 풀어보도록

 

n개의 숫자 카드를 갖고 있음(중복 가능) m개의 수를 입력받는데, 그 숫자 카드가 m에 몇 개나 있냐? hint : BinarySearch n개의 정수를 입력받을 때, 지금 입력한 수가 존재하면 arr[idx] ++; 그리고 중복된 수는 저장 안 해버리는 거지 -> 음수에 대해서는 어떻게 카운트할 것인가 음수 idx가 없잖아   -> 이것만 처리하면 사실상 끝나는 거긴 함     -> 음수 양수에 대해서 따로 배열 만들기       -> 아 배열로 왜 안 되지         -> segfalut : 인덱스로 그 수에 접근하게 했으니까 오버하지           -> 그렇다고 최대크기 넣으면 메모리 초과 나옴             -> 벡터를 사용해 보자              중복이 제거된 새로운 사이즈를 할당해서 BinarySearch를 적용하자

나와의 대화다.. 처음 간단하게 과정 써 놓고 코드 짜 보고 안 되면 이유 찾아서 답글달고 반박하고 답글달고 반박했다. 그래도 확실히 글로 쓰면서 푸니까 진전이 있음!!!

 

처음에 구상을 어떻게 했냐면, 10이 들어오면 arr[10]++; -5가 들어오면 arr[-5]++; 이런 식으로 떠올렸다. 근데 아뿔싸 나는 파이썬을 쓰고 있지 않아요 C++이라 음수 인덱스가 안 돼.

 

그래서 고민하던 중.. 그냥 양수랑 음수 저장할 거 따로 만들면 되지 않냐..? 멍청아

그리하여

arr1은 양수에 대한 개수를 저장하는 배열

arr2는 음수에 대한 개수를 저장하는 배열

로 선언을 해서 개수를 저장했다.

 

종합적인 로직은 이러하다

 

---

1. n개만큼 수를 입력받으면서, 양 음수에 대해 중복 개수를 세어 주는 배열을 열일시킴

2. 열일 시키면서, 중복을 제거한 녀석들만 넣는 벡터를 구성

3. 이 벡터를 sort

4. m을 반복하면서, 들어오는 타겟값에 대해 binary search

5. 값이 벡터에 존재하고 양수이면 arr1[target], 음수이면 arr2[-target]을, 없으면 0을 출력함

---

완벽하다 싶어서 제출했는데, segfault오류가 떴다. 당연하다.. 처음에 n 범위만 보고 arr[500000]로 선언했는데, 나는 입력되는 값 자체를 인덱스로 사용했기에, 최대가 10,000,000까지 가능하다. 그래서 arr[10000000]로 했더니 이번엔 메모리 초과가 난다. 배열 최댓값을 넘어섰다는 소리다. 1억까지 가능한 걸로 아는데 왜 그런 지 모르겠다.. 좀 찾아봐야겠다. 암튼 고민고민에 결국 배열도 걍 벡터로 바꿔볼까.. 해서 바꿨는데 맞았다 히히

한 시간 내로 풀긴 했지만 암튼 쉽진 않았음. binarysearch구현하려다가 이 무슨 봉변이냐!! 내일은 꼭 다시 구현해본다 주말이니까

 

Code Here~

#include <algorithm>
#include <cmath> //C++
#include <iostream>
#include <math.h> //C
#include <string>
#include <vector>
#include <queue>

using namespace std;

int main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n;
  cin >> n;
  vector <int> arr1(10000001); //양수 담을 배열
  vector <int> arr2(10000001); //음수 담을 배열 
  vector <int> v(n,0);
  
  for(int i=0; i<n; i++){
    int idx;
    cin >> idx;
    if(idx >= 0){
      if(arr1[idx]==0) v.push_back(idx);
      arr1[idx]++;
    }
    else{
      if(arr2[-idx]==0) v.push_back(idx);
      arr2[-idx]++;
    }
  }
    
  sort(v.begin(), v.end());

  int m;
  cin >> m;
  for(int i=0; i<m; i++){
    int target;
    cin >> target;
    if(binary_search(v.begin(), v.end(), target)){
      if(target>=0) cout << arr1[target] << " ";
      else cout << arr2[-target] << " ";
    }
    else cout << 0 << " ";
  }
  return 0;
}