[C++] 백준 10816번 숫자 카드 2

 

으... 힘들다.

 

오늘은 일어나자마자 느꼈다...

지금 안 하면 저녁에 안 할 것이라는...

 

얼른 노트북을 켜고 앉았다.

 

오늘 풀 문제는 어제 풀려고 했었던 '숫자 카드 2'~~!!

 

문제

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

10816번: 숫자 카드 2

 

이번 문제도 풀었던 문제지만, 예전에 자바로 풀었던 문제라서 기억이 잘 나지 않는다 ㅎㅎ

 

 

... 모르겠다... 모르겠어...

저번에 풀었던 숫자 카드 1처럼 풀면 될 것 같은데... 머리가 안 돌아간다 ㅠㅠ

왜 점점 할수록 머리가 안 돌아가지...?(주말이라 그런가...)

 

그래서 그냥 숫자 카드 1처럼 말고 생각나는 대로 풀어봤다.

 

 

//완전 망한 틀린 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

vector <int> card_s;
unordered_map <int, int> card;

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

	int n, m, a;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		card_s.push_back(a);
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> a;
		card.insert(make_pair(a,0));
	}
	for (int i = 0; i < n; i++) {
		if (card.find(card_s[i]) != card.end()) {
			card[card_s[i]]++;
		}
	}
	for (auto i:card) {
		cout << i.second << " ";
	}
	return 0;
}

 

역시...ㅠㅠ

 

 

일단 각각 벡터랑 unordered_map에 입력받았다. map으로 하면 key를 기준으로 오름차순 자동정렬을 해주기 때문에 정렬 없이 저장해 주기 위해 unordered_map을 사용해 주었다. 그리고 해당 값이 있으면 그것의 value를 1씩 증가시켜 주었는데, 순서가 이상하게 출력되었다. 그래서 card의 key 부분에 들어있는 것들을 출력해 주었더니 뒤에 있어야 하는 2가 앞에 있는 상태로 저장되어 있었다. 왜 그런지는 모르겠는데, 일단 이 코드는 틀릴 것을 알고 써본 것이기 때문에 다른 사람의 풀이를 찾아보기로 했다.

[unordered_map 참고] https://eocoding.tistory.com/6

 

 

 

찾아보니 map으로 푸는 방법과 이분탐색을 사용한 풀이가 있었다.

시간제한으로 1초가 있기 때문에 시간 복잡도가 O(1)인 HashMap 또는 O(logN)인 이분탐색을 이용해야 한다.

 

// map 사용

#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

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

  int N,M,x;
  cin >> N;
  map<int, int> arr;
  for (int i = 0; i < N; i++) {
    cin >> x;
    arr[x]++;
  }

  cin >> M;
  for (int i=0; i<M; i++){
    cin >> x;
    cout << arr[x] << " ";
  }
}
출처: https://portable-paper.tistory.com/entry/10816-%EC%88%AB%EC%9E%90-%EC%B9%B4%EB%93%9C2-C

 

map <int, int>로 중복이 없는 map을 만들고 한번 입력이 들어올 때마다 1씩 더해준다. 그렇게 개수가 저장되어 있는 map을 가지고 4번째 줄에 받는 입력에서 개수를 출력해주었다고 한다.

 

아!!! map을 하나만 사용해서 상근이가 가지고 있는 카드를 먼저 입력받아서 몇 개를 가지고 있는지 더해주고, 해당 카드만 출력해 주면 되는구나!! 난 이런 생각을 못했다... (머리에 입력하자... 입력)

 

 

// 이분탐색 사용

#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

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

  int N,M,x;
  cin >> N;
  int arr[N];
  for(int i=0; i<N; i++){
    cin >> arr[i];
  }

  sort(arr, arr+N);

  cin >> M;
  for(int i=0; i<M; i++){
    cin >> x;
    cout << upper_bound(arr, arr+N, x) - lower_bound(arr, arr+N, x) << " ";
  }
    
}
출처: https://portable-paper.tistory.com/entry/10816-%EC%88%AB%EC%9E%90-%EC%B9%B4%EB%93%9C2-C

 

첫 번째 입력받은 숫자를 정렬해서 저장해 두고, algorithm의 upper_bound와 lower_bound를 사용해서 개수를 파악하였다고 한다.

 

아... 자바에서도 저런 거 있었던 것 같은데... C++도 algorithm STL에 있다고 한다.

먼저 오름차순으로 정렬(이분탐색을 위해)해주고 upper_bound와 lower_bound를 이용하면 되는 것 같다.

 

upper_bound: 찾으려는 key 값을 초과하는 숫자 배열 몇 번째에서 처음 등장하는지 찾기 위함

lower_bound: 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함

https://chanhuiseok.github.io/posts/algo-55/

 

이 두 값을 빼주면 저장된 값의 개수를 알 수 있다!!

 

 

다음엔... 잊어버리지 말자...

 

내일부터 다시 파이팅~~~~