[BOJ] 백준 10816번: 숫자 카드 2 (C++)

 

- 문제 출처 : https://www.acmicpc.net/problem/10816

---

1. 생각

이번에도 map을 활용한 문제이다. 문제가 요구하는 사항 중에 이분탐색을 이용하는 것도 있었으나,

이분탐색 알고리즘을 아직 해보지 않아서 map만 활용해서 해보도록 하겠다.

 

2. 난관 & 해결방법

std::map <int, int> m;

 

숫자카드의 숫자와 개수를 각각 key, value로 두기 위해 int, int로 map을 만들었다.

 

for (int i = 0; i < N; i++)
{
    std::cin >> num;
    auto it = m.insert({num, 1});
    if (!(it.second))
        it.first -> second ++;
}

 

반복문에서는 insert로 값을 넣어주는데, 이 insert의 반환값이 pair <iterator, bool> 이라는 것을 알게 되어 활용해보았다.

이미 값이 존재하여 insert가 실패하면 if문에 걸려 second 값인 개수가 증가한다.

 

반환된 pair의 first는 insert 실패 시 해당 겹치는 key 값의 iterator 반환, 성공 시 insert된 key의 iterator 반환.

second는 insert에 성공하면 true, insert에 실패하면 false를 가진다.

이를 활용하여 it.second가 false 일 때, first가 가리키는 겹치는 key의 second(= 개수)를 증가시킨다.

 

for (int i = 0; i < M; i++)
{
    std::cin >> num;
    auto it = m.find(num);
    std::cout << it -> second << " ";
}

 

이번에는 find()를 활용하여 해당 iterator의 second를 출력하여 개수를 출력해주는 방식을 택했다.

 

추가적으로,

for (int i = 0; i < N; i++)
{
    std::cin >> num;
    m[num] ++;
}
std::cin >> M;
for (int i = 0; i < M; i++)
{
    std::cin >> num;
    std::cout << m[num] << " ";
}

 

map을 배열처럼 사용할 수도 있다는 것을 알게 되었는데,

이 방식은 위의 방식보다는 느려서 참고만 했다.

 

위처럼 사용하면 해당 num에 해당하는 key가 없으면 자동으로 추가해주고,

있으면 value만 ++ 해준다고 한다.

 

3. 코드 및 결론

[ 전체 코드 ]

#include <iostream>
#include <map>

int main(void){
    int N, M, num;
    std::map <int, int> m;
    std::cin.tie(NULL);
    std::ios::sync_with_stdio(false);
    std::cin >> N;
    for (int i = 0; i < N; i++)
    {
        std::cin >> num;
        auto it = m.insert({num, 1});
        if (!(it.second))
            it.first -> second ++;
    }
    std::cin >> M;
    for (int i = 0; i < M; i++)
    {
        std::cin >> num;
        auto it = m.find(num);
        std::cout << it -> second << " ";
    }
}

 

[ 결론 ]

 

자료구조 활용 방법이 정말 다양하다는 것을 알게 되었고,

이 방대한 활용 방법들을 전부 다 써먹을 수 있을지는 모르겠지만 최대한 다양하게 써보면서 익혀야겠다고 생각했다.

아직 알고리즘은 한발자국도 나가지 못했는데 벌써 벽이 하나씩 생기는 느낌이지만, 열심히 해봐야겠다.