[Programmers] 뉴스 클러스터링

주어진 문자열의 집합을 구한 후 두 집합의 교집합과 합집합을 구하는 문제이다.

문제풀이 전략
원소가 같으면 교집합, 다르면 합집합으로 처리해야 한다.

원소들을 벡터에 크기순으로 저장을 하면 투포인터를 이용하여 교집합과 합집합을 구할 수 있다.

예를들어 {'aa','ab','bb','bc'}와 {'ab','ac','bb'}가 있다고 하자.

두 벡터의 맨 앞 원소를 보면 aa가 더 작으므로 aa를 합집합에 넣어준 후 인덱스를 1 증가한다. ('ab'를 가리키게됨)

그리고 나서 각 벡터의 현재 인덱스 값을 비교해 보면 ab로 모두 같으므로 두 벡터의 인덱스를 모두 1 증가하고 교집합과 합집합에 추가한다.

이런 방식으로 투포인터를 이용하여 크기가 더 작은 것을 합집합에 넣고 인덱스를 증가시키는 방식을 활용하면 O(n)으로 구할 수 있다.
(정렬은 O(nlogn))

팁

• 문자를 대문자로 변경하는법
  char c = toupper(c);
  tolower()도 존재

코드

#include <string>
#include <algorithm>

using namespace std;

int solution(string str1, string str2) {
    int answer = 0;
    vector<string> s1;
    vector<string> s2;
    string str = "";
    for(int i=0;i<str1.size()-1;i++){
        if((str1[i]>='a'&&str1[i]<='z')||(str1[i]>='A'&&str1[i]<='Z')){
            if((str1[i+1]>='a'&&str1[i+1]<='z')||(str1[i+1]>='A'&&str1[i+1]<='Z')){
                str += toupper(str1[i]);
                str += toupper(str1[i+1]);
                s1.push_back(str);
                str = "";
            }
        }
    }
    
    for(int i=0;i<str2.size()-1;i++){
        if((str2[i]>='a'&&str2[i]<='z')||(str2[i]>='A'&&str2[i]<='Z')){
            if((str2[i+1]>='a'&&str2[i+1]<='z')||(str2[i+1]>='A'&&str2[i+1]<='Z')){
                str += toupper(str2[i]);
                str += toupper(str2[i+1]);
                s2.push_back(str);
                str = "";
            }
        }
    }
    
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());
    
    int kyo = 0;
    int hop = 0;
    
    int i1 = 0;
    int i2 = 0;
    while(1){
        if(i1 == s1.size() && i2 < s2.size()){
            hop++;
            i2++;
            continue;
        }else if(i2 == s2.size() && i1 < s1.size()){
            hop++;
            i1++;
            continue;
        }else if(i1 == s1.size() && i2 == s2.size())
            break;
        if(s1[i1] == s2[i2]){
            i1++;
            i2++;
            kyo++;
            hop++;
        }else if(s1[i1] > s2[i2]){
            i2++;
            hop++;
        }else{
            i1++;
            hop++;
        }
    }
    if(kyo == 0 && hop == 0)
        return 65536;
    answer = (int)(((float)kyo/(float)hop)*65536);
    return answer;
}

출처 : https://programmers.co.kr/learn/courses/30/lessons/17677