N

(SWEA c++)2948. 문자열 교집합 본문

SW Expert Academy

(SWEA c++)2948. 문자열 교집합

naeunchan 2020. 10. 21. 23:29
728x90
반응형

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV-Un3G64SUDFAXr&categoryId=AV-Un3G64SUDFAXr&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

문자열을 비교해야 한다.

처음에는 map을 이용하여 접근했지만 시간초과로 인해 vector 방식으로 바꿨다.

 

N, M 크기만큼 v1, v2에 string을 저장한다.

저장이 끝나면 반드시 sort를 하여 오름차순으로 비교할 수 있도록 한다.

 

while문을 통해 v1과 v2의 iterator를 조건으로 비교한다.

itr1 = v1.begin()

itr2 = v2.begin()

으로 시작하여

while문의 조건으로 둘 중에 하나가 벡터의 끝에 다다르면 탈출한다.

 

만약 두 반복자에 해당하는 값이 같으면 ans++과 더불어 두 반복자를 + 1 해주어 진행한다.

하지만 둘 중 하나의 값이 작으면 작은 값에 해당하는 반복자를 + 1 해주면서 진행한다.

 

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

using namespace std;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    
    for(int tc = 1; tc <= t; tc++)
    {
        int N, M, ans = 0;
        vector<string> v1, v2;
        string s;
            
        cin >> N >> M;
        
        for(int i = 0; i < N; i++)
        {
            cin >> s;
            v1.push_back(s);
        }
        
        for(int i = 0; i < M; i++)
        {
            cin >> s;
            v2.push_back(s);
        }
        sort(v1.begin(), v1.end());
        sort(v2.begin(), v2.end());
        
        auto itr1 = v1.begin();
        auto itr2 = v2.begin();
        
        while(itr1 != v1.end() && itr2 != v2.end())
        {
            if(*itr1 == *itr2)
            {
                ans++;
                itr1++;
                itr2++;
            }
            else if(*itr1 < *itr2)
                itr1++;
            else if(*itr1 > *itr2)
                itr2++;
        }
       
        cout << "#" << tc << " " << ans << endl;
    }
    return 0;
}
728x90
반응형

'SW Expert Academy' 카테고리의 다른 글

(SWEA c++)3032. 홍준이의 숫자 놀이  (0) 2020.10.22
(SWEA c++)2930. 힙  (0) 2020.10.22
(SWEA c++)2817. 부분 수열의 합  (0) 2020.10.21
(SWEA c++)2814. 최장경로  (0) 2020.10.21
(SWEA c++)2805. 농작물 수확하기  (0) 2020.10.21