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

 이 문제는 맵을 이용해서 풀었다. 상당히 복잡한데, 특히 교집합과 합집합을 계산해내는 것이 복잡했다. 일단 특수 케이스로 입력 스트링을 파싱한 두 배열이 모두 공집합이면 65536이 나와야 하고, 둘 중 하나라도 공집합이면 0이 리턴된다. 

 

 입력 스트링에 대한 집합을 만들 때, 그 안에 중복된 것도 들어가게 하는 대신 각 요소마다 카운트를 저장하고 집합 안에는 하나만 들어가도록 구현했다. 또한 교집합과 합집합을 구하는 수도코드를 다음과 같이 짜서 구현했다.

- 교집합 찾는 수도코드

visited 맵 생성
inter = 0

A 집합 반복문
	현재 원소 : temp
	
    B 집합 반복문
		만약 같으면
			inter += min(cntA, cntB)
			visited[temp] = true;
			break;
	만약 break로 끝나지 않았으면 (같은게 없었으면)
		visited[temp] = true;

B 집합 반복문
	현재 원소 : temp
	
	만약 !visited[temp] 이면
		A 집합 반복문
			만약 같으면
				inter += min(cntA, cntB)
				visited[temp] = true;
				break;
	만약 break로 끝나지 않았으면 (같은게 없었으면)
		visited[temp] = true;

- 합집합 찾는 수도코드

visited 맵 생성
uni = 0

A 집합 반복문
	현재 원소 : temp
	
    B 집합 반복문
		만약 같으면
			uni += max(cntA, cntB)
			visited[temp] = true;
			break;
	만약 break로 끝나지 않았으면 (같은게 없었으면)
		uni += cnt[temp]
		visited[temp] = true;

B 집합 반복문
	현재 원소 : temp
	
	만약 !visited[temp] 이면
		A 집합 반복문
			만약 같으면
				uni += max(cntA, cntB)
				visited[temp] = true;
				break;
	만약 break로 끝나지 않았으면 (같은게 없었으면)
		uni += cnt[temp]
		visited[temp] = true;

 여기서 하나 착각했던 것이 합집합을 구하는 수도코드에서 같은게 없었을 경우에 uni += 1을 하도록 만들었었는데, 이는 완전히 잘못되었었다. 같은게 없을 시 해당 요소와 중복되는 모든 요소가 같이 들어가야 하므로 cnt[temp] 가 더해져야하는데, 집합을 구현할 때 중복이 없게 한 대신 cnt 맵을 따로 만든 사실을 까먹고 1을 더해버린 것이다. 그래서 처음에는 틀린 답이 나왔다.

 

 

 

 

 전체 코드는 다음과 같다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

bool isAlpha(char c) {
    if (('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z')) {
        return true;
    }
    return false;
}

char toLower(char c) {
    if ('A' <= c && c <= 'Z') {
        c += ('a' - 'A');
    }
    return c;
}

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

    // 문자열 쪼개기
    vector<string> a;
    map<string, int> cntA;
    for (int i = 0; i < str1.size() - 1; i++) {
        if (isAlpha(str1[i]) && isAlpha(str1[i + 1])) {
            string temp = "";
            temp += toLower(str1[i]);
            temp += toLower(str1[i + 1]);

            if (cntA[temp] == 0) {
                a.push_back(temp);   
            }
            cntA[temp]++;
        }
    }
    
    vector<string> b;
    map<string, int> cntB;
    for (int i = 0; i < str2.size() - 1; i++) {
        if (isAlpha(str2[i]) && isAlpha(str2[i + 1])) {
            string temp = "";
            temp += toLower(str2[i]);
            temp += toLower(str2[i + 1]);

            if (cntB[temp] == 0) {
                b.push_back(temp);   
            }
            cntB[temp]++;
        }
    }
    
    if (a.empty() && b.empty()) {
        return 65536;
    }
    
    if (a.empty() || b.empty()) {
        return 0;
    }
    
    map<string, bool> visited;
    int inter = 0;
    for (string& tempA : a) {
        bool flag = true;
        for (string& tempB : b) {
            if (tempA == tempB) {
                inter += min(cntA[tempA], cntB[tempA]);
                visited[tempA] = true;
                flag = false;
                break;
            }
        }
        if (flag) {
            visited[tempA] = true;
        }
    }
    for (string& tempB : b) {
        if (!visited[tempB]) {
            bool flag = true;
            for (string& tempA : a) {
                if (tempA == tempB) {
                    inter += min(cntA[tempA], cntB[tempA]);
                    visited[tempA] = true;
                    flag = false;
                    break;
                }
            }
            if (flag) {
                visited[tempB] = true;
            }
        }
    }
    
    visited.clear();
    int uni = 0;
    for (string& tempA : a) {
        bool flag = true;
        for (string& tempB : b) {
            if (tempA == tempB) {
                uni += max(cntA[tempA], cntB[tempA]);
                visited[tempA] = true;
                flag = false;
                break;
            }
        }
        if (flag) {
            uni += cntA[tempA];
            visited[tempA] = true;
        }
    }
    for (string& tempB : b) {
        if (!visited[tempB]) {
            bool flag = true;
            for (string& tempA : a) {
                if (tempA == tempB) {
                    uni += max(cntA[tempA], cntB[tempA]);
                    visited[tempA] = true;
                    flag = false;
                    break;
                }
            }
            if (flag) {
                uni += cntB[tempB];
                visited[tempB] = true;
            }
        }
    }
    
    double sim = (double)inter / uni;
    sim *= 65536;
    answer = (int)sim;
    
    return answer;
}