(C++) 2018 KAKAO BLIND RECRUITMENT[1차] : 뉴스 클러스터링

1. 문제

programmers.co.kr/learn/courses/30/lessons/17677

코딩테스트 연습 - [1차] 뉴스 클러스터링

 

2. 풀이

영어를 스트링으로 비교하려다가 어떻게 비교하는지 모르겠어서 아스키코드로 다 숫자로 바꿨다.

영어가 두글자길래 앞에 두글자 뒤에 두글자가 오도록 앞에 영어에는 100을 곱했다. 

예를들어 ac라면

아스키 코드로 a= 97 c= 99이므로

숫자 9799로 바꾼 것이다. 

 

이렇게 숫자 배열을 2개 만든 뒤, 순서대로 비교하고, 같은 것을 발견하면 교집합에 +1을 한 후 

발견한 숫자를 0으로 바꾸었다 (중복으로 세는 것 방지)

 

마지막으로 합집합은 두 집합의 갯수 합 - 교집합의 크기 이므로 

total = Arr1.size() + Arr2.size() - interNum

으로 구해줬다!

 

이렇게 다구했는데도 답이 틀렸다고 나왔었는데.......

바로 개 빠가같게도 분모가 0일때 (total == 0)일때 답이 65536으로 나오게 했었어야 하는데

교집합 개수가 0일때 65536을 나오게 해버렸다..

이걸 발견 못해서 한시간동안 ㅠㅠ 헛짓했다ㅠㅠㅠㅠㅠ 숫자로 바꾸는게 잘못된 줄,,

 

3. 코드

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

int solution(string str1, string str2) {
    int answer = 0;
    vector <int> strArr1;
    vector <int> strArr2;
    
    for(int i = 0; i < str1.length()-1 ; i ++){
        if(isalpha(str1[i]) &&isalpha(str1[i+1]) !=0){
            int element = ((str1[i]&31)*100) + (str1[i+1]&31); 
            strArr1.push_back(element);
        }
    }
    
    for(int i = 0; i < str2.length()-1 ; i ++){
      if(isalpha(str2[i])&&isalpha(str2[i+1]) !=0){
        int element = ((str2[i]&31)*100) + (str2[i+1]&31); 
        strArr2.push_back(element);
        }
    }
    
    int interNum = 0;
    
    for (int i = 0; i < strArr1.size();i ++){
      for (int j = 0; j < strArr2.size();j ++){
        if(strArr1[i] == strArr2[j]){
            strArr2[j] = 0;
            interNum++;
            break;
        }
      }
    }
    
    int total = strArr1.size() + strArr2.size() - interNum;
    if(total != 0){
    float ans = (float)interNum / (float)total;
    answer = ans * 65536;}
    else answer = 65536;
    // answer = interNum;
    return answer;
}

 

4. 그외,,

오늘부터 갑자기 카카오 기출을 풀기 시작했다.

조금 어렵지만 노력하면 충분히 할 수 있을 것 같다

우리네 인생 화이팅..

---

참고. 다른 풀이

프로그래머스에서 다른 사람들의 풀이를 보다가 개 .. 오지는 풀이를 발견해서 블로그에 정리해놓는다. 

바로 이 분의 풀이인데.. 내가 이해한 바로 정리를 해놓겠다. 

 

1. 알파벳의 개수는 26개이며 알파벳은 2개씩 나온다. 즉 나올수있는 알파벳 2개의 나열은 26*26 = 676개

 

2. 크기가 676개인 배열 두개를 만든다.

 

3. 알파벳들을 모두 대소문자를 구분없는 숫자로 바꾼다 => 아스키연산 &31

* &31을 하면 대소문자 구분이 없어지는 이유

'a' = 65	1	0	0	0	0	0	1
'A' = 97	1	1	0	0	0	0	1
31	0	0	1	1	1	1	1
AND연산결과	0	0	0	0	0	0	1

소문자와 대문자는 아스키코드 상 32가 차이가 나고 이는, 앞에 비트로 바꾸었을때 뒤에서 6번째와 7번째가 다르다는 뜻이다. 따라서 &31 연산을 통해 뒤에서 6번째와 7번째를 0으로 고정시키면 뒤의 5자리는 모두 같게 된다.

 

4. 앞의 알파벳에 26을 곱한뒤 뒤의 알파벳을 더한다 (앞뒤 구분을 위함)

예) az인 경우

1*26 + 26 = 52

 

5. 해당 숫자의 자리에 +1을 한다.  (str1일경우 C배열에, str2일경우 D배열에)

예) C[52] = 1; <- az 문자열이 하나 있다는 뜻

 

6. 모든 str을 돌며 배열을 채운 후 C, D 배열을 비교하며 수를 더한다. 6-1. 교집합은 비교 후 작은 수를 더한다.6-2. 합집합은 비교 후 큰 수를 더한다. 

 

예) C[52] = 2, D[52] = 1일때 C는 배열은 az 문자열이 2개 있다는 뜻이며 D 배열은 az문자열이 1개 있다는 뜻 이므로C ={'az', 'az'}; D = {'az'}라는 뜻.

 

즉 교집합은 +1 {'az'}합집합은 +2 {'az' , 'az'}를 해준다. 

 

7. 마지막 계산 = 교집합 / 합집합 *65536 을 해준다. 

 

정말 갓벽한 풀이.... 너무 존경스러워서 아이디를 구글링해봤는데 정말 많은 백준 문제를 푸신 분이었다. 나도 노력해야지!!

 

---