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

 

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

---

1. 생각

이번에는 새로운 자료구조인 집합(set)을 배울 수 있는 문제를 가지고 왔다.

이 set이라는 자료구조는 삽입 순서에 상관없이 정렬되어 입력되며, 중복이 없게 입력된다.

 

기본적으로 set에 어떤 값을 삽입하기 위해서는 insert()를 사용하며,

자료에 접근하기 위해서는 반복자(iterator)라는 객체가 필요하다.

 

이 iterator는 ' 어떤 자료구조에 접근하든 동일한 방법으로 접근하기 위해 제공되는 객체'로써,

포인터와 비슷하게 내부 요소에 접근하는데,

어떤 자료구조든 해당 내부 구조를 몰라도 쉽게 순회할 수 있게 해주며,

서로 다른 자료구조에 통일된 인터페이스로 접근을 할 수 있도록 해주는 것이 iterator 이다.

 

set에서 어떠한 자료를 찾기 위해서는 find() 를 사용할 수 있는데,

이 find()는 '찾는 값이 존재하면 해당 위치의 iterator를 반환하고, 없으면 end()를 반환' 한다.

end()는 마지막 원소 뒤 공백구간의 주소값을 가지고 있으므로 빈값이다.

 

erase() 로 값, 범위, 반복자를 넣어 원하는 자료를 지울 수 있으며,

clear() 를 통해 원소 모두를 삭제할 수도 있다.

 

이런 방법들을 통해 문제를 한번 해결해보자.

 

2. 난관 & 해결방법

#include <iostream>
#include <set>

 

 set을  include 해줬다.

 

int N, M, num;
std::set <int> st;
std::cin.tie(NULL);
std::ios::sync_with_stdio(false);
std::cin >> N;
for (int i = 0; i < N; i ++){
    std::cin >> num;
    st.insert(num);
}

 

문제에서 N개의 값을 받아서 set에 넣어주도록 설정되어있다.

따라서 set을 위와 같이 선언해주고, for문에서 하나씩 값을 insert() 해줬다.

insert로 어떤 정수를 넣어주면 set에서는 기본적으로 오름차순으로 정렬되지만 greater 를 이용해 내림차순으로 바꿀 수도 있다.

 

std::cin >> M;
for (int i = 0; i < M; i ++){
    std::cin >> num;
    if (st.find(num) != st.end())
        std::cout << "1 ";
    else
        std::cout << "0 ";
}

 

이후 구별하기 위한 개수인 M을 입력받고, 해당 개수만큼 반복을 돌린다.

 

입력한 숫자가 find()를 통해 set에 존재하는지 확인하고,

find()의 결과가 end() iterator와 같지않으면 set에 존재한다는 뜻이므로 1을 출력, 같으면 0을 출력하게 했다.

추후에 수정한다면 std::cout << st.find(num) != st.end() << " "; 처럼 바로 출력에 넣어도 좋을 것 같다.

 

3. 코드 및 결론

[ 전체 코드 ]

#include <iostream>
#include <set>

int main(void){
    int N, M, num;
    std::set <int> st;
    std::cin.tie(NULL);
    std::ios::sync_with_stdio(false);
    std::cin >> N;
    for (int i = 0; i < N; i ++){
        std::cin >> num;
        st.insert(num);
    }
    std::cin >> M;
    for (int i = 0; i < M; i ++){
        std::cin >> num;
        if (st.find(num) != st.end())
            std::cout << "1 ";
        else
            std::cout << "0 ";
    }
}

 

[ 결론 ]

 

set의 활용법을 알아봤다.

또한 iterator를 쓰는 것을 처음 알게 되었는데,

앞으로 어떤 자료구조를 쓰든 활용할 가능성이 크므로 사용법을 잘 익혀둬야할 것 같다.