[프로그래머스] 뉴스 클러스터링 (2018 카카오 신입 기출) (C++)

Key

문자열 문제이기 때문에 문자열 관련 내장 함수를 어느정도 알고 있어야한다.

 

 

Idea

문제 조건을 따라 구현하면 끝이다. 내가 푼 방식은 다음과 같다.

 

1. for문으로 str[i]값과 str[i+1] 값이 알파벳인지 검사한 후 둘 다 알파벳이 맞다면 대문자로 변경 후 벡터에 넣기

- 만약 둘 중 하나라도 알파벳이 아니라면 해당 쌍은 버린다 & 대소문자를 신경쓰지 않는다는 조건에 부합

- toupper 함수 사용 (char형식을 대문자로 변경해줌)

 

2. 이렇게 만들어진 v1(str1 문자들이 담긴 벡터)와 v2(str2 문자들이 담긴 벡터)를 비교해서 같은 원소가 있는지 찾아낸다.

- 이 때 주의해야할 점은 중복값이 허용된다는 것이다. 만약 v1에 "AA"가 있고 v2에 "AA", "AA"가 있다면 교집합 원소 개수는 2개이다. 이 조건을 놓치면 4, 7, 9, 10, 11 케이스를 통과하지 못한다.

 

3. v1, v2가 공집합인지 아닌지 확인

 

3-1. 두 벡터의 합이 0이면 공집합이다. 공집합일 시 답은 65536

- 문제에서 공집합일시 답은 1이라고 했지만 마지막에 65536를 곱하라고 했으니 65536가 맞다.

 

3-2. 공집합이 아닐 시 교집합 / 합집합 * 65536 결과 출력

- 합집합은 전체 개수에서 교집합을 뺀 값이므로 따로 구할 필요 없다.

- 이 때 교집합 개수를 담는 변수를 int형으로 선언했다면 반드시 double로 형변환 해야한다. 그렇지 않으면 정수형 나눗셈이 되어서 1/3같은 경우엔 답이 0이 나온다. 

- 소수점을 제외하고 정수 부분만 출력하기 위해 trunc 함수 사용

 

실수했던 부분

C++에서 find함수는 찾으려는 원소를 발견하면 거기서 iterator을 반환하고 끝낸다. 즉, 중복값을 찾지는 못한다.

 

교집합에 중복 원소도 포함된다는 조건을 생각하지 못하고 냅다 find만 써서 보이는 테스트 케이스는 다 통과했지만 4,7,9,10,11은 통과하지 못했다.

결국 기존 v2를 복사한 v2_copy를 만들어서 원소를 찾으면 erase로 삭제하여 중복값까지 찾아냈다.

뭔가 더 쉽게 풀 수 있는데 돌아온 느낌이라 아쉽다. 다른 사람 코드를 참고해서 리팩토링 해야겠다.

 

Code

#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;

vector<pair<char, char>>v1;
vector<pair<char, char>>v2;

bool isABC(char ch) {
    if (ch >= 'A' && ch <= 'Z') return true;
    return false;
}

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

    for (int i = 0; i < str1.length() - 1; i++) {
        char upper1 = toupper(str1[i]);
        char upper2 = toupper(str1[i + 1]);
        if (isABC(upper1) && isABC(upper2)) {
            v1.push_back({ upper1, upper2 });
        }
    }

    for (int i = 0; i < str2.length() - 1; i++) {
        char upper1 = toupper(str2[i]);
        char upper2 = toupper(str2[i + 1]);
        if (isABC(upper1) && isABC(upper2)) {
            v2.push_back({ upper1, upper2 });
        }
    }

    vector<pair<char, char>>v2_copy = v2;

    for (const auto& v : v1) {
        auto it = find(v2_copy.begin(), v2_copy.end(), v);
        if (it != v2_copy.end()) {
            same++;
            v2_copy.erase(it);
        }
    }

    total = v1.size() + v2.size();

    if (total == 0) {
        answer = 65536;
    }
    else {
        // answer=trunc((same/(total-same))*65536); 이건 틀렸음
        answer = (int)trunc((double)same / (total - same) * 65536);
    }


    return answer;
}