백준 c++ 1269 문제 풀이

문제 링크 : https://www.acmicpc.net/problem/1269

목차

1. 설명

 

2. 내 코드

 

3. 문제 풀이 해석 내용

 

4. 실행 결과

 

설명

백준 실버 4 문제 입니다.

문제명 : 대칭 차집합

---

지금까지 푼 문제 모두 비슷한 느낌이 있어 이번에도 vector, sort로 binary_search를 사용하여 이진탐색 방법으로 풀었습니다.

확실히 이진탐색으로 문제 푸는 법에 대해서 알아가고 있다는 느낌이 드는 것 같습니다.

 

내 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;


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

    int n, m;
    cin >> n >> m;
    vector<int> nv(n);
    vector<int> mv(m);

    for (int i = 0; i < n; ++i)
    {
        cin >> nv[i];
    }
    for (int i = 0; i < m; ++i)
    {
        cin >> mv[i];
    }
    
    sort(nv.begin(), nv.end());
    sort(mv.begin(), mv.end());

    int cnt = 0;

    for (int i = 0; i < n; ++i)
    {
        if (!binary_search(mv.begin(), mv.end(), nv[i]))
        {
            cnt++;
        }
    }

    for (int i = 0; i < m; ++i)
    {
        if (!binary_search(nv.begin(), nv.end(), mv[i]))
        {
            cnt++;
        }
    }

    cout << cnt;

}

 

문제 풀이 해석 내용

 

변수 선언 및 배열 입력

int n, m; // 첫 번째 배열 크기 n, 두 번째 배열 크기 m
cin >> n >> m;

vector<int> nv(n); // n 크기의 정수 벡터 nv
vector<int> mv(m); // m 크기의 정수 벡터 mv

for (int i = 0; i < n; ++i)
{
    cin >> nv[i]; // 첫 번째 배열 요소 입력받아 nv에 저장
}
for (int i = 0; i < m; ++i)
{
    cin >> mv[i]; // 두 번째 배열 요소 입력받아 mv에 저장
}

int n, m;: 첫 번째 배열 nv의 크기 n과 두 번째 배열 mv의 크기 m을 저장하는 변수입니다.
cin >> n >> m;: 사용자로부터 n과 m 값을 입력받습니다.

vector<int> nv(n), mv(m);: 크기가 n인 정수형 벡터 nv와 크기가 m인 정수형 벡터 mv를 각각 만듭니다.
두 개의 for 루프를 사용하여 각각 n개와 m개의 정수를 입력받아 nv와 mv 벡터에 순서대로 저장합니다.

 

 

두 배열 정렬

sort(nv.begin(), nv.end()); // 벡터 nv 정렬
sort(mv.begin(), mv.end()); // 벡터 mv 정렬

sort(...): std::sort 함수를 사용하여 두 벡터 nv와 mv를 각각 오름차순으로 정렬합니다. 두 배열 모두 정렬되어야 이진 탐색(binary_search)을 효율적으로 사용할 수 있습니다.

 

 

공통되지 않는 요소 개수 세기 (첫 번째 방법)

int cnt = 0; // 공통되지 않는 요소 개수 초기화

for (int i = 0; i < n; ++i) // 벡터 nv의 각 요소에 대해 반복
{
    // 벡터 mv에서 nv[i]가 존재하는지 이진 탐색
    if (!binary_search(mv.begin(), mv.end(), nv[i]))
    {
        cnt++; // 존재하지 않으면 cnt 증가
    }
}

int cnt = 0;: 공통되지 않는 요소들의 총 개수를 저장할 변수입니다.
첫 번째 for 루프는 벡터 nv의 각 요소에 대해 반복합니다.

binary_search(mv.begin(), mv.end(), nv[i]): 정렬된 벡터 mv에서 현재 nv[i] 값이 존재하는지 이진 탐색합니다.
if (!binary_search(...)): binary_search 결과가 false이면 (즉, nv[i]가 벡터 mv에 존재하지 않으면)
cnt++;: nv[i]는 nv에만 존재하는 요소이므로 cnt를 1 증가시킵니다.

 

 

공통되지 않는 요소 개수 세기 (두 번째 방법)

for (int i = 0; i < m; ++i) // 벡터 mv의 각 요소에 대해 반복
{
    // 벡터 nv에서 mv[i]가 존재하는지 이진 탐색
    if (!binary_search(nv.begin(), nv.end(), mv[i]))
    {
        cnt++; // 존재하지 않으면 cnt 증가
    }
}

두 번째 for 루프는 벡터 mv의 각 요소에 대해 반복합니다.

binary_search(nv.begin(), nv.end(), mv[i]): 정렬된 벡터 nv에서 현재 mv[i] 값이 존재하는지 이진 탐색합니다.
if (!binary_search(...)): binary_search 결과가 false이면 (즉, mv[i]가 벡터 nv에 존재하지 않으면)
cnt++;: mv[i]는 mv에만 존재하는 요소이므로 cnt를 1 증가시킵니다.

 

 

최종 결과 출력

cout << cnt;

모든 계산이 끝난 후 cnt에 저장된, 두 배열에 공통으로 포함되지 않는 요소들의 총 개수를 출력합니다.

 

 

실행 결과