백준 c++ 1764 문제 풀이

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

목차

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, m;
    cin >> n >> m;

    vector<string> A(n);

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

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

    vector<string> answer;

    for (int i = 0; i < m; ++i)
    {
        string name;
        cin >> name;
        if (binary_search(A.begin(), A.end(), name))
        {
            answer.push_back(name);
        }
    }

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

    cout << answer.size() << '\n';
    for (const string& name : answer)
    {
        cout << name << "\n";
    }

}

 

문제 풀이 해석 내용

 

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

int n, m; // 첫 번째 목록 크기 n, 두 번째 목록 크기 m
cin >> n >> m;

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

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

int n, m;: 첫 번째 문자열 목록의 개수 n과 두 번째 문자열 목록의 개수 m을 저장할 변수입니다.
cin >> n >> m;: 사용자로부터 n과 m 값을 입력받습니다.
vector<string> A(n);: 크기가 n인 문자열 벡터 A를 생성합니다. 

이 벡터에는 첫 번째 문자열 목록이 저장될 것입니다.
for 루프를 사용하여 n번 반복하며 각 문자열을 입력받아 벡터 A에 순서대로 저장합니다.

 

 

첫 번째 문자열 목록 정렬

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

sort(A.begin(), A.end());: std::sort 함수를 사용하여 벡터 A의 모든 문자열을 사전순으로 오름차순 정렬합니다. 이진 탐색(binary_search)은 정렬된 데이터에서만 가능하므로 이 단계가 매우 중요하고 효율성을 결정짓습니다.

 

 

공통 문자열을 저장할 벡터 선언

vector<string> answer; // 공통 문자열을 저장할 빈 벡터

vector<string> answer;: 첫 번째 목록과 두 번째 목록 모두에 포함되는 문자열들을 저장할 빈 벡터 answer를 선언합니다.

 

 

두 번째 문자열 목록 입력 및 공통 문자열 찾기

for (int i = 0; i < m; ++i) // m번 반복 (두 번째 목록의 개수만큼)
{
    string name;
    cin >> name; // 두 번째 목록의 문자열(질의) 입력

    // 정렬된 벡터 A에서 현재 입력받은 name이 존재하는지 이진 탐색
    if (binary_search(A.begin(), A.end(), name))
    {
        answer.push_back(name); // 존재하면 answer 벡터에 추가
    }
}

for 루프를 사용하여 m번 반복하며 두 번째 문자열 목록의 각 문자열을 처리합니다.
string name; cin >> name;: 두 번째 목록에서 문자열 하나를 입력받아 name 변수에 저장합니다. 이 name이 첫 번째 목록(A)에 있는지 검색할 대상입니다.

binary_search(A.begin(), A.end(), name): std::binary_search 함수를 사용하여 정렬된 벡터 A의 시작부터 끝까지의 범위에서 현재 입력받은 name 문자열이 존재하는지 효율적으로 검색합니다. 존재하면 true를, 존재하지 않으면 false를 반환합니다.

if (binary_search(...)): binary_search 결과가 true이면 (즉, name이 첫 번째 목록 A에도 있다면).
answer.push_back(name);: name 문자열을 answer 벡터의 끝에 추가합니다.

 

 

공통 문자열 목록 정렬:

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

sort(answer.begin(), answer.end());: answer 벡터에 저장된 공통 문자열들을 사전순으로 다시 정렬합니다. 문제에서 요구하는 출력 형식에 맞추기 위함입니다.

 

 

결과 출력

cout << answer.size() << '\n'; // 공통 문자열 개수 출력
for (const string& name : answer) // answer 벡터 순회
{
    cout << name << "\n"; // 각 공통 문자열 출력
}

cout << answer.size() << '\n';: answer 벡터의 크기(answer.size())를 출력하여 공통된 문자열의 총 개수를 알려줍니다. '\n'으로 줄바꿈합니다.

for (const string& name : answer): 범위 기반 for 루프를 사용하여 answer 벡터에 있는 각 문자열을 name에 대입하며 순회합니다. const string&는 메모리 복사 없이 효율적으로 문자열을 참조하기 위함입니다.

cout << name << "\n";: 현재 answer 벡터의 요소인 name 문자열을 출력하고 "\n"으로 줄바꿈합니다. 이 과정을 통해 모든 공통 문자열이 사전순으로 한 줄씩 출력됩니다.

 

 

실행 결과