[프로그래머스 C++] [1차] 뉴스 클러스터링

 

[프로그래머스 C++] [1차] 뉴스 클러스터링

 

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

프로그래머스

---

 

해결전략

 

문자열

 

isupper()    대문자인지 확인

tolower()    대문자를 소문자로 변환

 

	string tmp = str1.substr(i, 2);

C++의 std::string 클래스에서 사용할 수 있는 substr 함수를 사용하여 문자열에서 일부를 추출하는 코드.

str1은 원본 문자열이며, i는 현재 문자열에서 추출을 시작할 위치를 나타낸다.

 

i는 str1 문자열 내의 인덱스.
2는 추출하고자 하는 부분 문자열의 길이를 나타낸다. 

 

위의 코드의 경우, str1 문자열에서 i 위치부터 시작하여 2개의 문자를 추출한다.

예를 들어, str1이 "FRANCE"이고 i가 2라면, 위 코드는 "AN"이라는 문자열을 추출하여 tmp에 저장한다. substr 함수를 사용하면 문자열에서 부분 문자열을 추출하거나 잘라낼 수 있다.

---

 

처음 시도한 코드

 

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int solution(string str1, string str2) {
    int answer = 0;
    int is = 0, un = 0; //is: 교집합, un: 합집합

    //둘 다 공집합인 경우
    if (str1.size() == 0 && str2.size() == 0){
        return 65536;
    }

	for(int i=0; i<str1.size(); i++){
		if(isupper(str1[i])){
            str1[i] = tolower(str1[i]);
		}
	}
    for (int i = 0; i < str2.size(); i++) {
        if (isupper(str2[i])) {
            str2[i] = tolower(str2[i]);
        }
    }

    vector<string> s1;
    int x = 0;
    for(int i=0; i<str1.size()-1; i++){
        if('a' <= str1[i] && str1[i] <= 'z' &&
            'a' <= str1[i+1] && str1[i+1] <= 'z')
        {
            string tmp = str1.substr(i, 2); // 두 글자를 추출
            s1.push_back(tmp);
        }
    }
    vector<string> s2;
    x = 0;
    for (int i = 0; i < str2.size()-1; i++) {
        if ('a' <= str2[i] && str2[i] <= 'z' &&
            'a' <= str2[i + 1] && str2[i + 1] <= 'z')
        {
            string tmp = str2.substr(i, 2); // 두 글자를 추출
            s2.push_back(tmp);
        }
    }

    for(int i = 0; i < s1.size(); i++){
        for (int j = 0; j < s2.size(); j++)
        {
            if (s1[i] == s2[j]){
                s1[i] = '0';
                s2[i] = '0';
                is++;
                break;
            }
        }
    }
    
    un = s1.size() + s2.size() - is;

    if (un == 0) 
        answer = 65536;
    else
        answer = is * 65536 / un;
        
    return answer;
}

 

 

위의 코드가 잘못된 이유

    sort(s1.begin(), s1.end()); // 벡터를 정렬
    sort(s2.begin(), s2.end());

벡터 정렬를 하지 않았다.

s1과 s2를 정렬하는 이유는 두 문자열 집합 간의 교집합을 효율적으로 찾기 위함이다.

아래의 정답 코드에서는 병합 정렬 알고리즘과 유사한 방식을 사용하여 교집합을 찾아낸다. 이 방법은 두 리스트가 이미 정렬되어 있을 때 가장 효율적이다. s1[i]와 s2[j]가 동일할 경우에만 교집합의 크기를 증가시키며, 그 외에는 작은 값을 가진 쪽의 인덱스만 증가시킨다.

이런 방식으로 진행하면, 두 리스트를 한 번씩만 훑어보면서 교집합을 찾아낼 수 있다. 만약 리스트들이 정렬되지 않았다면, 각 원소에 대해 다른 리스트의 모든 원소와 비교해야 하므로 시간 복잡도가 매우 커지게 된다.

따라서 이런 알고리즘에서는 입력 리스트를 미리 정렬해놓는 것이 중요하다. 이로 인해 전체 알고리즘의 성능이 크게 향상된다.

 

 for(int i = 0; i < s1.size(); i++){
        for (int j = 0; j < s2.size(); j++)
        {
            if (s1[i] == s2[j]){
                s1[i] = '0';
                s2[i] = '0';
                is++;
                break;
            }
        }
    }

위의 코드는 문제가 되는 부분은 교집합(is)를 계산하는 부분이다. 이 부분에서 중첩 반복문을 사용하여 s1의 각 원소에 대해 s2의 모든 원소와 비교하고 있다. 이렇게 하면 동일한 원소가 여러 번 있는 경우, 그 원소가 한 번만 나타나더라도 is를 증가시키게 된다. 따라서 이 방법은 중복된 원소들이 있는 경우 올바른 결과를 주지 않는다.

반면에 아래의 코드는 정렬된 벡터에 대해 병합 정렬과 비슷한 방식으로 교집합을 찾아내므로 위와 같은 문제가 발생하지 않는다. s1[i]와 s2[j]가 동일할 때만 is를 증가시키며, 그 외에는 작은 값을 가진 쪽의 인덱스만 증가시킨다. 따라서 두 벡터에서 동일한 원소들이 몇 번 등장하는지 정확하게 계산할 수 있으므로 올바른 자카드 유사도를 반환한다.

 

수정한 코드

int i = 0, j = 0;
while (i < s1.size() && j < s2.size()) {
    if (s1[i] == s2[j]) {
        is++;
        i++;
        j++;
    } else if (s1[i] < s2[j]) {
        i++;
    } else {
        j++;
    }
}

 

---

 

 

정답 코드

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(string str1, string str2) {
    int answer = 0;
    int is = 0, un = 0; //is: 교집합, un: 합집합

    //둘 다 공집합인 경우
    if (str1.size() == 0 && str2.size() == 0){
        return 65536;
    }

	for(int i=0; i<str1.size(); i++){
		if(isupper(str1[i])){
            str1[i] = tolower(str1[i]);
		}
	}
    for (int i = 0; i < str2.size(); i++) {
        if (isupper(str2[i])) {
            str2[i] = tolower(str2[i]);
        }
    }

    vector<string> s1;
    int x = 0;
    for(int i=0; i<str1.size()-1; i++){
        if('a' <= str1[i] && str1[i] <= 'z' &&
            'a' <= str1[i+1] && str1[i+1] <= 'z')
        {
            string tmp = str1.substr(i, 2); // 두 글자를 추출
            s1.push_back(tmp);
        }
    }
    vector<string> s2;
    x = 0;
    for (int i = 0; i < str2.size()-1; i++) {
        if ('a' <= str2[i] && str2[i] <= 'z' &&
            'a' <= str2[i + 1] && str2[i + 1] <= 'z')
        {
            string tmp = str2.substr(i, 2); // 두 글자를 추출
            s2.push_back(tmp);
        }
    }

    sort(s1.begin(), s1.end()); // 벡터를 정렬
    sort(s2.begin(), s2.end());
	
    // 정렬된 벡터에서 병합 정렬 알고리즘과 비슷한 방식으로 교집합 구하기
	// 동일한 원소가 있는 경우만 is 증가시키고, 그 외에는 작은 값을 가진 쪽의 인덱스만 증가시킴
    int i = 0, j = 0;
    while (i < s1.size() && j < s2.size()) {
        if (s1[i] == s2[j]) {
            is++;
            i++;
            j++;
        } else if (s1[i] < s2[j]) {
            i++;
        } else {
            j++;
        }
    }

    un = s1.size() + s2.size() - is; // 합집합 구하기

    if (un == 0) // 합집합==0인 경우
        answer = 65536;
    else
        answer = is * 65536 / un;
    
    return answer;
}

 

 

 

 

---