백준 c++ 14425 문제 풀이

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

목차

1. 설명

 

2. 내 코드

 

3. 문제 풀이 해석 내용

 

4. 실행 결과

 

설명

백준 실버 4 문제 입니다.

문제명 : 문자열 집합

---

많은 자료구조 중에서 빠른 문자열 탐색을 위한 자료구조를 사용해야 할 것 같았습니다.

문제 알고리즘 분류에는 자료구조,문자열 말고도 해시나 트리등이 적혀 있었으나 아직 배우지 않았고, 사용하기까지 오래 걸릴 것 같았기 때문에 vector(이진탐색)를 사용하는 법을 찾아서 풀어보았습니다.

 

문자열을 저장하고 검사 문자열들을 하나씩 확인하며 포함되는지 체크했습니다.

그리고 입출력 속도를 빠르게 하기 위해 특정 문자열을 사용했으며, endl보다는 '\n'을 사용했습니다.

 

 

내 코드

#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, cnt = 0;
    cin >> n >> m;

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

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

    string query;

    for (int i = 0; i < m; ++i)
    {
        cin >> query;
        if (binary_search(s.begin(), s.end(), query))
        {
            cnt++;
        }
    }

    cout << cnt << '\n';
}

 

문제 풀이 해석 내용

 

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

int n, m, cnt = 0;
cin >> n >> m; // 문자열 목록 개수 n, 질의 개수 m 입력

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

int n;: 주어진 문자열 목록의 개수를 저장합니다.
int m;: 검색할 질의 문자열의 개수를 저장합니다.

 

int cnt = 0;: 주어진 문자열 목록에 포함된 질의 문자열의 개수를 세기 위한 변수입니다.
cin >> n >> m;: 문자열 목록의 개수 n과 질의의 개수 m을 입력받습니다.
vector<string> s(n);: n개의 문자열을 저장할 수 있는 벡터 s를 생성합니다.
for 루프를 사용하여 n번 반복하며 각 문자열을 입력받아 s 벡터에 순서대로 저장합니다.

 

 

문자열 목록 정렬

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

sort(s.begin(), s.end());: std::sort 함수를 사용하여 s 벡터의 모든 문자열을 사전순으로 오름차순 정렬합니다. 이진 탐색은 정렬된 데이터에서만 가능하므로 이 단계가 필수적입니다.

 

 

질의 처리 및 개수 세기 루프

string query; // 검색할 질의 문자열 저장 변수

for (int i = 0; i < m; ++i) // m번 반복 (질의 개수만큼)
{
    cin >> query; // 검색할 질의 문자열 입력받기

    // 이진 탐색으로 문자열 존재 여부 확인
    if (binary_search(s.begin(), s.end(), query))
    {
        cnt++; // 존재하면 cnt 증가
    }
}

string query;: 검색할 질의 문자열을 저장할 변수입니다.
for 루프를 사용하여 m번 반복하며 각 질의 문자열을 처리합니다.
cin >> query;: 검색할 질의 문자열을 입력받습니다.

binary_search(s.begin(), s.end(), query): std::binary_search 함수를 사용합니다. 이 함수는 s 벡터의 시작(s.begin())부터 끝(s.end())까지의 범위에서 query 문자열이 존재하는지 효율적으로 검색합니다.
binary_search는 해당 문자열이 존재하면 true를, 존재하지 않으면 false를 반환합니다.
if (binary_search(...)) { cnt++; }: binary_search 결과가 true이면 cnt를 1 증가시킵니다.

 

 

최종 결과 출력

cout << cnt << '\n';

모든 질의를 처리한 후, cnt에 저장된, 주어진 문자열 목록에 포함된 질의 문자열의 총 개수를 출력하고 줄바꿈합니다.

 

 

실행 결과