백준 c++ 1920 문제 풀이

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

목차

1. 설명

 

2. 내 코드

 

3. 문제 풀이 해석 내용

 

4. 실행 결과

 

설명

백준 실버 4 문제 입니다.

문제명 : 수 찾기

---

저번에 풀었던 문제와 큰 차이점이 없어 vector와 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;
    cin >> n;

    vector<string> A(n);

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

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

    int m;
    cin >> m;

    vector<string> M(m);

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

    for (int i = 0; i < m; ++i)
    {
        if (binary_search(A.begin(), A.end(), M[i]))
            cout << "1\n";
        else
            cout << "0\n";
    }

}

 

문제 풀이 해석 내용

 

변수 선언 및 첫 번째 문자열 목록 입력

int n, m; // 첫 번째 목록 개수 n, 두 번째 목록 개수 m
cin >> n >> m;

vector<string> A(n); // n 크기의 문자열 벡터 A (첫 번째 목록)

for (int i = 0; i < n; ++i)
{
    cin >> A[i]; // n개의 문자열 입력받아 벡터 A에 저장
}

n: 첫 번째 목록에 들어갈 문자열의 개수를 저장하는 변수입니다.
m: 두 번째 목록에 들어갈 (찾아볼) 문자열의 개수를 저장하는 변수입니다.
cin >> n >> m;: 사용자로부터 n과 m 값을 입력받습니다.

vector<string> A(n);: n개의 string을 저장할 수 있는 A라는 이름의 동적 배열(벡터)을 만듭니다.
for 루프를 사용하여 n번 반복하며, 사용자로부터 문자열을 하나씩 입력받아 벡터 A에 순서대로 저장합니다.

 

 

첫 번째 문자열 목록 정렬

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

sort(A.begin(), A.end());: 벡터 A에 저장된 모든 문자열을 사전순으로 오름차순 정렬합니다. 

이 단계가 중요한 이유는 이진 탐색(binary_search)은 데이터가 정렬되어 있을 때만 사용할 수 있기 때문입니다. 정렬을 통해 나중에 검색을 매우 빠르게 할 수 있습니다.

 

 

두 번째 문자열 목록 입력

vector<string> M(m);

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

vector<string> M(m);: 크기가 m인 문자열 벡터 M을 생성합니다. 

이 벡터에는 두 번째 문자열 목록 (찾아볼 문자열들)이 저장됩니다.

for 루프를 사용하여 m번 반복하며, 사용자로부터 문자열을 하나씩 입력받아 벡터 M에 순서대로 저장합니다. (참고: 이전 질문 코드에서는 이 벡터를 만들지 않고 cin >> query를 직접 사용했는데, 이번 코드에서는 벡터에 저장 후 사용합니다. 둘 다 가능하지만 벡터에 저장하는 것이 코드를 명확하게 할 수 있습니다.)

 

 

두 번째 목록 문자열 검색 및 결과 출력

for (int i = 0; i < m; ++i) // m번 반복 (두 번째 목록 개수만큼)
{
    // 벡터 M의 i번째 요소(찾아볼 문자열)가
    // 정렬된 벡터 A에 존재하는지 이진 탐색으로 확인
    if (binary_search(A.begin(), A.end(), M[i]))
        cout << "1\n"; // 존재하면 1 출력 후 줄바꿈
    else
        cout << "0\n"; // 존재하지 않으면 0 출력 후 줄바꿈
}

for 루프를 사용하여 m번 반복하며, 두 번째 목록에 있는 각 문자열을 순서대로 처리합니다.
binary_search(A.begin(), A.end(), M[i]): std::binary_search 함수를 사용합니다. 이 함수는 정렬된 범위인 벡터 A의 시작(A.begin())부터 끝(A.end())까지의 범위에서 현재 찾아볼 문자열 M[i]가 존재하는지 매우 빠르게 확인합니다. 존재하면 true를, 존재하지 않으면 false를 반환합니다.

if (binary_search(...)): binary_search 결과가 true이면 (즉, M[i]가 벡터 A에 포함되어 있으면).
cout << "1\n";: 1을 출력하고 줄바꿈합니다.

else: binary_search 결과가 false이면 (즉, M[i]가 벡터 A에 포함되어 있지 않으면).
cout << "0\n";: 0을 출력하고 줄바꿈합니다.

 

 

실행 결과