백준 C++ 10816번 숫자 카드 2 ( map, upper & lower )

 

오늘은 

4월의 1/3이 군요.

 

저는 오늘 잠실에 가기로 했습니다.

거기 녹차아이스크림이 맛있습니다.

 

그거 먹으러 가는 셈입니다.

교보문고에 가서 볼펜도 하나 사 올 겁니다.

예전부터 금색이 사고 싶었거든요.

 

볼펜은 많아지는데 쓸데는 없어지는 중...ㅎㅎㅋ

 

오늘의 문제를 풀고 가야 하기 때문에

후다닭 풀어보겠습니다.

 

---

 

정답률.. 39 퍼..

글자수가 50만 개인데..

하나씩 비교하는 건 너무 숫자가 커질 거 같고..

 

일단 50만 개를 담을 벡터 하나,

글자를 받아두고

그다음 50만 개를 받을 벡터하나

글자를 받아서..

 

글자수만큼 출력..?

 

일단 해보자

 

일단 벡터는 좀 어려울 거 같아서 배열로 변경.

 

그리고 풀면서 굳이 50만 개를 받을 배열하나도 필요 없어서

 

 

작성..

테케는 맞는데 답이 맞을지는 모르겠다.

 

답은 틀렸다.

런타임에러가 뜬다.

 

뭐가 문제였을까..

하긴 이렇게 쉬우면 39 퍼가 아니지..

 

배열사이즈에서 넘어간다고 이야기해 주었다.

 

아하..

내가 -10000000을 받았는데

배열개수가.. 50만 개여서 그런가 보다.

그러면 배열 크기를 애초에.. 2천만 개로 하면 안 되려나..ㅎㅋ

3천만 개..?

 

근데 그렇게 쉬우면.. 39 퍼가 아니지..

 

 

 

인지 씨를 찾았다.

 

 [-5] 이런 건 없다고 

나의 식에서 음수를 받으려면 -를 양수로 바꿔줘야 한다고 했다.

 

그러게 예전에 했었다

 

모든 카드에 천만을 더해주면 된다.

 

근데 이거는 지금 내 식은 풀 수 있지만

앞으로 풀 때에 도움이 되는 더 중요한 식으로 풀자고

다른 방법을 제안했다.

 

---

방법 1

정렬하고 난후

 

1 2 2 3 5 8 8 8 10

이러면

 

8의 시작점은 어디?

지금 인덱스로는 5이다

8의 다음 큰 수의 시작점은 어디?

지금 인덱스 하면 8이다

그럼 아 8은 

8-5 3개 있구나! 를 알 수 있다는 것.

 

 

방법 2

숫자가 들어오면

창고에서 그 숫자 만들어서 개수 1개를 넣어준다.

그리고 그다음에 똑같은 수가 나오면

창고에서 그냥 꺼내서 또 추가해 준다.

 

 

내가 생각했던 건데..?!

 

우리는 그렇게 쉽게 해 줄 수 있는 친구

map 이 있다고 했다.

---

 

 

일단 방법 1부터 해본다.

 

이분탐색이라고 말하는 거 같았는데

저번에 이분탐색이라고 뭔 바이너리 했었다.

 

binary_search

이 친구는! 질문에 true / false만 대답한다.

그렇게 글자를 줄여가는 거지.

 

하지만 여기서 사용될 이분탐색은

 

lower_bound

시작점

lower_bound(v.begin(), v.end(), 찾을 숫자);

 

upper_bound

끝점

upper_bound(v.begin(), v.end(), 찾을 숫자);

이 두 가지이다.

 

 

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> v;

    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        v.push_back(a);
    }

    sort(v.begin(),v.end());

    int m;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int b;
        cin >> b;
        cout << upper_bound(v.begin(),v.end(),b) - lower_bound(v.begin(),v.end(),b) << " "; 
    }
}

 

 

방법 2도 해보자!

 

 

무언가를 찾고 저장할 때 쓰는 핵심 도구

map

레드-블랙 트리.

데이터를 넣을 때마다 알아서 크기 순서대로 정렬

 

- 줄을 세울 때 시간이 오래 걸림

- lower_bound, upper_bound 사용가능

 

unordered_map

내부적으로 해시 테이블 구조 사용.

 

unordered_map <int, int> m;

앞 int 들어올 숫자

뒤 int 들어올 개수

 

데이터를 넣으면 그 숫자를 찾아서 바로 넣는다.

줄을 세워서 넣는 게 아니기 때문에 이론상 시간복잡도가 O(1)이라고 한다.

 

- 제일 작은 값 찾기 X, 구간별로 찾기 X

- 빠르게 이거 있어? 몇개 있어 ? 만 대답 가능

 

 

코테에서 90%는 unordered를 사용

 

이러 번 벡터도 쓸 필요가 없다.

 

map은 대괄호를 써서

대괄호 안에는 무조건 first 값만 들어갈 수 있고

결과로는 무조건 second로 나오게끔 되어있다고 한다.

 

그래서 m [a] 이렇게만 해줘도

m [a]++ 이렇게만 해줘도?

m <a,1> 이 되는 것

그리고 출력을 하면 1만 나오는 것!!

 

매우 중요한 사실!!

 

 

#include <bits/stdc++.h>
using namespace std;

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

    unordered_map<int, int> m;
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        m[a]++;
    }
    
    int k;
    cin >> k;

    for (int i = 0; i < k; i++)
    {
        int b;
        cin >> b;
        cout << m[b] << " ";
    }
}

 

---

 

이렇게

두 가지 방법으로 문제를 풀어봤다!

 

너어어어어무너무 어렵다.

map도 어렵고 이중탐색? 이것도 왜 이리 어려운지..

 

map을 그래도 기억해 두었으니

다음에도 써먹기를 기원해 본다.