프로그래머스[programmers]-1차 뉴스 클러스터링(C++)[LV2]

📕문제

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

프로그래머스

 

🔎문제 설명

두 문자열을 2개로 끊어서 집합을 생성한 후 교집합과 합집합을 구해서 유사도를 구하는 문제이다.

 

문제의 주요 특징은 다음과 같다.

1. 문자열을 2개씩 끊어서 하나의 원소로 만든다.
2. "알파벳"만 원소로 만들 수 있다.
   • 숫자, 공백, 특수문자가 포함된 경우 버린다.
3. 알파벳은 대 소문자의 차이를 무시한다.
4. 원소의 중복을 허용한다.

원소의 중복..? 말이 조금 어려운데 예시를 들면 쉽게 이해할 수 있다.

문제에서 주어진 테스트케이스를 인용해서

 

str1 = aa1+aa2 , str2 = AAAA12라고 가정하자

 

str1에서 집합을 구하면 {aa, aa}, str2에서 집합을 구하면 {AA, AA, AA}가 될 것이다.

(중복 원소를 허용하기 때문이다)

교집합은 {AA,AA}, 합집합은 {AA, AA, AA}가 될 것이다.

자카드 유사도를 구하면 2/3이다.

이렇게 똑같은 원소에 대해서 같지만 다른원소로 처리해야 하기 때문에 이 작업이 조금 까다롭다.

 

 

문자열을 집합의 원소로 뽑아내기

---

두글자씩 묶어서 원소로 만들어야 한다.

여기서 해야 하는 작업은 알파벳만 뽑아야 하고, 대소문자 중 하나로 통일해줘야 한다.

 

알파벳을 뽑는 작업은 C++에서 제공하는 isalpha()를 사용했다.

만약 문자가 알파벳이 아니라면 0을 리턴한다.

따라서 isalpah()로 먼저 거르고,

대소문자를 구분해야 한다.

나는 모든 문자를 대문자로 통일시키기 위해서 소문자인지 판별하는 islower()를 사용했다.

소문자라면 true를 반환한다.

이렇게 해서 두 개의 문자를 temp에 저장해서 각각의 집합에 push 해줬다.

 

vector<string> funct(string str){
    vector<string>ary;
    for(int i=0; i<str.size()-1; i++){
        string temp="";
        if(isalpha(str[i])!=0 && isalpha(str[i+1])!=0){ //알파벳 판별
            if(islower(str[i])) //소문자 판별
                temp+=str[i]-32; //소문자 -> 대문자
            else
                temp+=str[i];
            if(islower(str[i+1])) //소문자 판별
                temp+=str[i+1]-32; //소문자 -> 대문자
            else
                temp+=str[i+1];
            ary.push_back(temp); //결과 저장
        }
        else
            continue;
    }
    return ary;
}

 

이렇게 과정을 거쳤는데, 만약 두 집합이 공집합이라면 간단하게 65536을 리턴하면 된다.

 

합집합과 교집합 찾기

---

나는 두 집합을 vector로 표현했다.

초기에 두 집합의 크기의 하버를 미리 저장했다. (뒤에 합집합을 구하기 위해서 필요해서이다)

 

다음 이중포문으로 하나하나 비교했다.(더 좋은 방법이 있을 거 같은데.. 일단 해당 방법을 사용했다)

 

집합을 하나하나 비교하면서, 만약 같다면 교집합의 개수를 증가시키고, 원소를 제외시켰다.

왜 제외시켜야 하냐?

해당 집합들은 중복원소의 집합을 허용하기에 무조건 지워줘야 한다.

예를 들어서 {ab, ba, ab}와 {ba, ab, ba}를 비교할 때

ab는 각각 ba, ab, ba와 비교할 것이다. 여기서 일치하는 원소가 있기 때문에 교집합의 개수는 1개 증가한 1이 된다.

ba는 각각 ba, ab, ba를 비교하고, 일치하는 원소 ba가 있기 때문에 교집합의 개수는 1개 증가한 2가 된다.

ab는 각각 ba,ab,ba를 비교하고, 일치하는 원소 ab가 있지만, 해당 ab는 이미 교집합에 뽑힌 원소이기 때문에

지금 검사하는 ab는 교집합에 추가할 수 없다. 이러한 점이 있기 때문에 교집합에 뽑힌 원소들을 지워줘야 하는 것이다.

방문 체크를 하거나, 지우거나, 여러 방법이 있지만, 나는 erase를 사용해서 vector에서 지웠다.

 

교집합의 개수를 추출하면 처음에 두 집합의 크기의 합에서 교집합의 개수를 빼면 합집합이 될 것이다.

---

 

💻코드

/*
유사도 교집합 / 합집합 , 만약 두 집합이 모두 공집합일 경우 유사도는 1로 정의
다중집합도 적용 가능, 같은것도 다 적용해서 교집합,합집합을 따짐.
문자열을 두글자씩 끊어서 하는 듯. 문자열만 취급해야해서, 특수 문자는 버림.
대문자와 소문자의 차이를 무시함.
*/
#include <iostream>
#include <string>
#include <vector>
#include <cctype>
using namespace std;
int number = 65536;
vector<string> first;
vector<string> second;
double same=0,s=0;
vector<string> funct(string str){
    vector<string>ary;
    for(int i=0; i<str.size()-1; i++){
        string temp="";
        if(isalpha(str[i])!=0 && isalpha(str[i+1])!=0){ //알파벳 판별
            if(islower(str[i])) //소문자 판별
                temp+=str[i]-32; //소문자 -> 대문자
            else
                temp+=str[i];
            if(islower(str[i+1])) //소문자 판별
                temp+=str[i+1]-32; //소문자 -> 대문자
            else
                temp+=str[i+1];
            ary.push_back(temp); //결과 저장
        }
        else
            continue;
    }
    return ary;
}
int solution(string str1, string str2) {
    int answer = 0;
    first=funct(str1); //첫번째 집합 원소
    second=funct(str2); //두번째 집합 원소
    if(first.size()==0 && second.size()==0) //둘다 공집합일 때
        return number;
    s= first.size()+second.size(); //초기 두 집합의 합을 저장.
    for(auto iter = first.begin(); iter!=first.end(); iter++){
        for(auto iter2 = second.begin(); iter2!=second.end(); iter2++){
            if(*iter==*iter2){ //같다면
                same++; //교집합 개수 증가
                second.erase(iter2); //원소 지우기
                break;
            }
        }
    }
    s-=same; //합집합
    answer=(same/s)*number;
    return answer;
}

 

---

😀느낀 점

• iterator를 사용한 반복문을 많이 사용하지 않아서 조금은 어색했다.
  • 기존에는 map에서만 iterator를 사용했고, vector에서는 처음이었지만, 생각보다 접근하기 편해서 유용했다.
• isalpha(), islower(), isupper() 같은 문자열 처리하는 함수들을 알아두면 아주 유용하다고 느꼈다.
• c++은 문자열을 다루고, 자료형을 다루기에 정말 복잡하다..