[C++ | 문자열] 프로그래머스 2단계 뉴스 클러스터링 문제 풀이 / 테스트 예제 4,7,9,10,11번 반례와 해결 방법

배울 점이 정말 많았던 코드였다. 1) 알파벳인지 아닌지 확인하는 방법, 2) 소문자를 대문자로 변환하는 방법, 3) 소수점 아래는 버려서 출력하는 방법, 4)Char 두 개 합쳐서 string으로 만드는 방법 등 사소하지만 모르면 알 수 없는 여러 가지 함수들을 익힐 수 있어서 유익했다. 또한, 테스트 예제의 반이 넘는 4,7,9,10,11번에서 오류가 났었는데 이를 관통하는 반례를 찾아냈다. 혹시 나와 같은 어려움을 겪은 사람들에게 도움이 되면 좋겠다. 

 

특히 문자 두 개를 합쳐서 문자열로 만드는 과정에서 '+' 연산자를 사용했는데 계속 아스키 코드 값으로 나오고 오류만 뱉어내서 정말 애를 많이 먹었다. 내가 해결한 방법은 문자열 s를 선언해서 s에 pushback 함수로 문자 하나씩 푸쉬해주고, 해당 문자열 s를 S1 벡터 집합에 푸쉬해주는 방법으로 구현했다.

 

문제 설명: 프로그래머스 2단계 뉴스 클러스터링 

프로그래머스

 

해결 코드

#include <string>
#include <vector>
#include <cctype> //타입 확인 헤더파일
#include <cmath>  //소수점 버림 헤더파일
using namespace std;


int solution(string str1, string str2) {
    int answer = 0;

    //각 문자열 소문자->대문자로 변환
    for (int i = 0; i < str1.size(); i++) {
        if (islower(str1[i])) str1[i] -= 32;
    }
    for (int i = 0; i < str2.size(); i++) {
        if (islower(str2[i])) str2[i] -= 32;
    }

    vector<string> S1;  
    for (int i = 0; i < str1.size()-1; i++) { //집합 S1 생성       
        if (isalpha(str1[i])&&isalpha(str1[i+1])) {
            string s;
            s.push_back(str1[i]);
            s.push_back(str1[i + 1]);
            S1.push_back(s);
        }       
    }

    vector<string> S2;
    for (int i = 0; i < str2.size() - 1; i++) { //집합 S2 생성
        if (isalpha(str2[i]) && isalpha(str2[i + 1])) {
            string s;
            s.push_back(str2[i]);
            s.push_back(str2[i + 1]);
            S2.push_back(s);
        }       
    }

    //두 벡터 S1, S2의 교집합 크기 구하기
    double intersection = 0.0;
    for (int i = 0; i < S1.size(); i++) {
        for (int j = 0; j < S2.size(); j++) {
            if (S1[i] == S2[j]) {
                S2[j]="0";                      //테스트 케이스 4,7,9,10,11 오류 체크포인트
                intersection++;
                break;
            }
        }
    }
    
    double sum= S1.size() + S2.size() - intersection; //합집합 크기 구하기

    double Jaccard; // 자카드 유사도
    if (sum == 0) Jaccard = 1;
    else Jaccard = (double)intersection / (double)sum;

    Jaccard *= 65536;
    answer = floor(Jaccard);
    return answer;
}

 

오류 반례

s1: [a, a, a, b, b]
s2: [a, a, b, b, b]

만약 4,7,9,10,11번에서 오류가 나는 경우 '교집합을 구하는 코드'를 수정해 보길 바란다. 

위와 같이 s1과 s2가 주어질 경우에 정상적인 상황이라면 교집합이 [aa, ab, bb]가 되어야 한다.

나의 경우에는 교집합을 구하는 코드를 for문 두 개로 구성해서 S1[i] == S2[j] 일 경우 교집합 카운트를 1씩 더하는 방식으로 만들었는데, 이렇게 하는 경우 교집합이 [aa, aa, ab, bb]로 오류 상황이 발생한다.

즉, if문에서 S1과 S2의 교집합을 찾으면 해당 원소를 S2에서 삭제해 줘야 중복 발생을 막을 수 있다.

 

 

감사합니다.