문제

자카드 유사도를 이해하고 구현하는 문제

1. 문자열의 길이 (0 <= strLength <=1000)

2. 자카드 유사도
   1) 정의
   자카드 유사도 = 두 문자열의 교집합 / 두 문자열의 합집합

   2) 예시
   A = {1, 1, 2, 2, 3}, B = {1, 2, 2, 4, 5}
   A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}
   자카드 유사도 = 3/7 = 0.42

   3) 반환법
   실수인 자카드 유사도에 65536을 곱합 결과를 반환합니다.

   4) 예외 사항
   두 문자열이 모두 공집합인 경우 65536을 반환합니다.

문제 링크

---

1. 첫인상

자카드 유사도는 잘 모르지만

문제는 쉬워 보인다. 진짜로 쉬운 문제였다.

2. 문제 쪼개기

1. 입력
2. 문자열에서 영문자만 뽑아내기
3. 문자열모두 대문자로 바꾸기
4. 자카드 유사도 계산하기
5. 반환

1, 5번은 일반적이기 때문에 2, 3, 4번을 집중해서 보겠습니다.

3. 문자열에서 영문자만 뽑아내기

프로그래밍에서 문자형 자료는 정수의 아스키 코드 값을 가집니다.

• 대문자 아스키 코드 범위 65~90
• 소문자 아스키 코드 범위 97~122

만약 특정 문자 ch가 (ch >= 65 && ch <=90) || (ch>=97 && ch<=122) 조건에 맞는다면 영문자임을 알 수 있습니다.

// 영문자 여부를 검사하는 함수
bool is_character(char ch){
    
    bool result = false;
    
    // 대문자 아스키 코드 범위 65~90
    // 소문자 아스키 코드 범위 97~122
    if((ch >= 65 && ch <=90) || (ch>=97 && ch<=122)) result = true;
    
    return result;
}

4. 문자열모두 대문자로 바꾸기

이것도 아스키코드를 이용합니다.

• 대문자 아스키 코드 범위 65~90
• 소문자 아스키 코드 범위 97~122

소문자의 아스키코드 값에서 32를 빼주면 대문자가 됩니다.

// 대문자로 바꿔주는 함수
char to_uppercase(char ch){
    char result = 'a';
    
    // 만약 소문자라면 32를 빼서 대문자로 만들어줍니다.
    if(ch >= 97) result = ch - 32;
    else result = ch;

    return result;
}

5. 자카드 유사도 계산하기

1) 문자 저장 자료구조

AA, AZ, BD 와 같은 문자열이 몇번 나왔는지 저장할 자료구조가 필요합니다.

저는 int 배열을 사용했습니다.

만약, 주어진 문자열이 "AB"인 경우

아스키코드 값: A - 65, B - 66 입니다.
첫번째 문자 A에 100을 곱하고, 두번째 문자 B를 더해주면

유니크한 4자리 정수가 만들어집니다.(범위: 6565 ~ 9090)

이를 최대 길이 9091 int 배열에 개수를 저장합니다.

// 2) 만약 2개의 문자가 모두 영문자일 경우
if(is_character(first_ch) && is_character(second_ch)){

    // 3) 영문자를 모두 대문자로 만들어줍니다.
    first_ch = to_uppercase(first_ch);
    second_ch = to_uppercase(second_ch);

    // 4) 첫번째 문자에 100을 곱하고 두번째 문자랑 더해서 유니크한 숫자를 만들어줍니다.
    // 대문자의 아스키코드 범위는 65 ~ 90
    // 예) AB -> 6566
    int num = to_uppercase(first_ch) * 100 + to_uppercase(second_ch);

    // 유니크한 숫자의 개수를 1증가시켜줍니다.
    check[i][num]++;
}

2) 합집합, 교집합 계산하기

A = {1, 1, 2, 2, 3}, B = {1, 2, 2, 4, 5}
A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}

문제의 설명에 따르면 다음 규칙이 보입니다.

합집합 - 각 숫자의 최대개수

교집합 - 각 숫자의 최소개수 (0개는 제외)

for(int i=min_int; i<=max_int; i++){
    // 1) 합집합은 각 숫자의 최대값
    total_cnt += max(check[0][i], check[1][i]);

    // 2) 교집합은 각 숫자의 최소값
    duple_cnt += min(check[0][i], check[1][i]);
}

3) 자카드 유사도 계산

두개의 집합이 모두 공집합인 경우는 합집합이 0입니다.

1) 두 집합이 모두 공집합이 아닌 경우
교집합 / 합집합을 통해 자카드 유사도를 계산하고, 655636을 곱해줍니다.

2) 두 집합이 모두 공집합인 경우
655636을 반환합니다.

// 4. 자카드 유사도를 계산합니다.
// 두 집합이 모두 공집합인 경우 total_cnt == 0 입니다.

// 1) 두 집합이 모두 공집합이 아닌 경우
if(total_cnt != 0){
    // 실수 계산을 하고
    jaccard = duple_cnt / total_cnt;
    answer = (int)(base_num * jaccard);
}
// 2) 두 집합이 모두 공집합인 경우
else{
    // 규칙에 따라 656636을 넣어줍니다.
    answer = base_num;
}

6. 시간 복잡도 계산

문자열의 길이 n (1000)

최대 2n = O(2n) = O(n) 상수생략,

1억에 1초걸리기 때문에 시간안에 충분히 풀 수 있습니다.

7. 전체 코드

1) c++

#include <string>
#include <vector>
#define min_int 6565
#define max_int 9090
#define base_num 65536
using namespace std;

/*
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 알고리즘: 반복문
    사용한 자료구조: 배열
 */

int check[2][max_int + 1];
double duple_cnt=0, total_cnt=0, jaccard=0;

int min(int a, int b){
    return a < b ? a: b;
}

int max(int a, int b){
    return a > b ? a : b;
}

// 영문자 여부를 검사하는 함수
bool is_character(char ch){
    
    bool result = false;
    
    // 대문자 아스키 코드 범위 65~90
    // 소문자 아스키 코드 범위 97~122
    if((ch >= 65 && ch <=90) || (ch>=97 && ch<=122)) result = true;
    
    return result;
}

// 대문자로 바꿔주는 함수
char to_uppercase(char ch){
    char result = 'a';
    
    // 만약 소문자라면 32를 빼서 대문자로 만들어줍니다.
    if(ch >= 97) result = ch - 32;
    else result = ch;

    return result;
}

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

    // 1. 문자열 2개를 배열에 넣는다.
    vector<string> v;
    v.push_back(str1);
    v.push_back(str2);
    
    // 2. 문자열 배열을 순회합니다.
    for(int i=0; i<(int)v.size(); i++){
        
        string word = v[i];
        
        for(int j=0; j<(int)word.size() - 1; j++){
            
            // 1) 문자를 2개씩 검사합니다.
            char first_ch = word[j];
            char second_ch = word[j+1];
            
            // 2) 만약 2개의 문자가 모두 영문자일 경우
            if(is_character(first_ch) && is_character(second_ch)){
                
                // 3) 영문자를 모두 대문자로 만들어줍니다.
                first_ch = to_uppercase(first_ch);
                second_ch = to_uppercase(second_ch);

                // 4) 첫번째 문자에 100을 곱하고 두번째 문자랑 더해서 유니크한 숫자를 만들어줍니다.
                // 대문자의 아스키코드 범위는 65 ~ 90
                // 예) AB -> 6566
                int num = first_ch * 100 + second_ch;
                
                // 유니크한 숫자의 개수를 1증가시켜줍니다.
                check[i][num]++;
            }
        }
    }
    
    /*
        3. 전체 문자를 검사합니다.
        숫자의 최소값은 6565 -> AA
        숫자의 최대값은 9090 -> ZZ
        즉, AA에서 ZZ까지 검사합니다.
     */
    for(int i=min_int; i<=max_int; i++){
        // 1) 합집합은 각 숫자의 최대개수
        total_cnt += max(check[0][i], check[1][i]);
        
        // 2) 교집합은 각 숫자의 최소개수
        duple_cnt += min(check[0][i], check[1][i]);
    }
    
    // 4. 자카드 유사도를 계산합니다.
    // 두 집합이 모두 공집합인 경우 total_cnt == 0 입니다.
    
    // 1) 두 집합이 모두 공집합이 아닌 경우
    if(total_cnt != 0){
        // 실수 계산을 하고
        jaccard = duple_cnt / total_cnt;
        answer = (int)(base_num * jaccard);
    }
    // 2) 두 집합이 모두 공집합인 경우
    else{
        // 규칙에 따라 656636을 넣어줍니다.
        answer = base_num;
    }
    
    return answer;
}

2) java

import java.util.ArrayList;
import java.util.List;

/*
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 알고리즘: 반복문
    사용한 자료구조: 배열
*/
class Solution {

    public int min(int a, int b){
        return a < b ? a: b;
    }

    public int max(int a, int b){
        return a > b ? a : b;
    }

    // 영문자 여부를 검사하는 함수
    public Boolean is_character(char ch){

        Boolean result = false;

        // 대문자 아스키 코드 범위 65~90
        // 소문자 아스키 코드 범위 97~122
        if((ch >= 65 && ch <=90) || (ch>=97 && ch<=122)) result = true;

        return result;
    }

    // 대문자로 바꿔주는 함수
    public char to_uppercase(char ch){
        char result = 65;

        // 만약 소문자라면 32를 빼서 대문자로 만들어줍니다.
        if(ch >= 97) result = (char) (ch - 32);
        else result = ch;

        return result;
    }

    public static int min_int = 6565, max_int = 9090, base_num = 65536;
    public static int check[][] = new int[2][max_int + 1];
    public static double duple_cnt=0, total_cnt=0, jaccard=0;

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

        // 1. 문자열 2개를 배열에 넣는다.
        List<String> v = new ArrayList<String>();
        v.add(str1);
        v.add(str2);

        // 2. 문자열 배열을 순회합니다.
        for(int i=0; i<(int)v.size(); i++){

            String word = v.get(i);

            for(int j=0; j<(int)word.length() - 1; j++){

                // 1) 문자를 2개씩 검사합니다.
                char first_ch = word.charAt(j);
                char second_ch = word.charAt(j+1);

                // 2) 만약 2개의 문자가 모두 영문자일 경우
                if(is_character(first_ch) && is_character(second_ch)){

                    // 3) 영문자를 모두 대문자로 만들어줍니다.
                    first_ch = to_uppercase(first_ch);
                    second_ch = to_uppercase(second_ch);

                    // 4) 첫번째 문자에 100을 곱하고 두번째 문자랑 더해서 유니크한 숫자를 만들어줍니다.
                    // 대문자의 아스키코드 범위는 65 ~ 90
                    // 예) AB -> 6566
                    int num = first_ch * 100 + second_ch;

                    // 유니크한 숫자의 개수를 1증가시켜줍니다.
                    check[i][num]++;
                }
            }
        }

        /*
            3. 전체 문자를 검사합니다.
            숫자의 최소값은 6565 -> AA
            숫자의 최대값은 9090 -> ZZ
            즉, AA에서 ZZ까지 검사합니다.
         */
        for(int i=min_int; i<=max_int; i++){
            // 1) 합집합은 각 숫자의 최대개수
            total_cnt += max(check[0][i], check[1][i]);

            // 2) 교집합은 각 숫자의 최소개수
            duple_cnt += min(check[0][i], check[1][i]);
        }

        // 4. 자카드 유사도를 계산합니다.
        // 두 집합이 모두 공집합인 경우 total_cnt == 0 입니다.

        // 1) 두 집합이 모두 공집합이 아닌 경우
        if(total_cnt != 0){
            // 실수 계산을 하고
            jaccard = duple_cnt / total_cnt;
            answer = (int)(base_num * jaccard);
        }
        // 2) 두 집합이 모두 공집합인 경우
        else{
            // 규칙에 따라 656636을 넣어줍니다.
            answer = base_num;
        }

        return answer;
    }
}

3) python

import math

'''
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 알고리즘: 반복문
    사용한 자료구조: 배열
'''

min_int = 6565
max_int = 9090 
base_num = 65536

check = [[0 for _ in range(max_int+1)] for _ in range(2)]

def min(a, b):
    if a > b: return b
    else: return a

def max(a, b):
    if a < b: return b
    else: return a

# 영문자 여부를 검사하는 함수
def is_character(ch):

    result = False

    # 대문자 아스키 코드 범위 65~90
    # 소문자 아스키 코드 범위 97~122
    c = ord(ch)
    if (c >= 65 and c <=90) or (c>=97 and c<=122): result = True

    return result


# 대문자로 바꿔주는 함수
def to_uppercase(ch):
    result = 65

    # 만약 소문자라면 32를 빼서 대문자로 만들어줍니다.
    c = ord(ch)
    if c >= 97: result = c - 32
    else: result = c

    return result

def solution(str1, str2):
    answer = 0

    # 1. 문자열 2개를 배열에 넣는다.
    v = []
    v.append(str1)
    v.append(str2)
    
    # 2. 문자열 배열을 순회합니다.
    for i in range(len(v)):
        
        word = v[i]

        for j in range(len(word) - 1):

            # 1) 문자를 2개씩 검사합니다.
            first_ch = word[j]
            second_ch = word[j+1]
            
            # 2) 만약 2개의 문자가 모두 영문자일 경우
            if is_character(first_ch) and is_character(second_ch):
                
                # 3) 영문자를 모두 대문자로 만들어줍니다.
                first_ch = to_uppercase(first_ch)
                second_ch = to_uppercase(second_ch)

                # 4) 첫번째 문자에 100을 곱하고 두번째 문자랑 더해서 유니크한 숫자를 만들어줍니다.
                # 대문자의 아스키코드 범위는 65 ~ 90
                # 예) AB -> 6566
                num = first_ch * 100 + second_ch
                
                # 유니크한 숫자의 개수를 1증가시켜줍니다.
                check[i][num] += 1
    
    '''
        3. 전체 문자를 검사합니다.
        숫자의 최소값은 6565 -> AA
        숫자의 최대값은 9090 -> ZZ
        즉, AA에서 ZZ까지 검사합니다.
    '''
    total_cnt = 0
    duple_cnt = 0
    jaccard = 0

    for i in range(max_int + 1):
        # 1) 합집합은 각 숫자의 최대개수
        total_cnt += max(check[0][i], check[1][i])
        
        # 2) 교집합은 각 숫자의 최소개수
        duple_cnt += min(check[0][i], check[1][i])
    
    # 4. 자카드 유사도를 계산합니다.
    # 두 집합이 모두 공집합인 경우 total_cnt == 0 입니다.
    
    # 1) 두 집합이 모두 공집합이 아닌 경우
    if total_cnt != 0:
        # 실수 계산을 하고
        jaccard = duple_cnt / total_cnt
        answer = base_num * jaccard

    # 2) 두 집합이 모두 공집합인 경우
    else: 
        # 규칙에 따라 656636을 넣어줍니다.
        answer = base_num

    return math.trunc(answer)

4) javascript

/*
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 알고리즘: 반복문
    사용한 자료구조: 배열
*/

var min_int = 6565
var max_int = 9090
var base_num = 65536

function min(a, b){
    return a < b ? a : b
}

function max(a, b){
    return a > b ? a : b
}

// 영문자 여부를 검사하는 함수
function is_character(ch){
    
    let result = false;
    
    // 대문자 아스키 코드 범위 65~90
    // 소문자 아스키 코드 범위 97~122
    let c = ch.charCodeAt(0)
    if((c >= 65 && c <=90) || (c>=97 && c<=122)) result = true;
    
    return result;
}

// 대문자로 바꿔주는 함수
function to_uppercase(ch){
    let result = 65;
    
    // 만약 소문자라면 32를 빼서 대문자로 만들어줍니다.
    let c = ch.charCodeAt(0)
    if(c >= 97) result = c - 32;
    else result = c;

    return result;
}


function solution(str1, str2) {
    var answer = 0;
    
    // 1. 문자열 2개를 배열에 넣는다.
    let v = []
    v.push(str1)
    v.push(str2)

    var check = [[], []]
    for(let i=0; i<2; i++){
        for(let j=0; j<max_int+1; j++){
            check[i][j] = 0
        }
    }

    // 2. 문자열 배열을 순회합니다.
    for(let i=0; i<v.length; i++){
        
        let word = v[i];
        
        for(let j=0; j<word.length - 1; j++){
            
            // 1) 문자를 2개씩 검사합니다.
            let first_ch = word[j];
            let second_ch = word[j+1];
            
            // 2) 만약 2개의 문자가 모두 영문자일 경우
            if(is_character(first_ch) && is_character(second_ch)){
                
                // 3) 영문자를 모두 대문자로 만들어줍니다.
                first_ch = to_uppercase(first_ch);
                second_ch = to_uppercase(second_ch);
                
                // 4) 첫번째 문자에 100을 곱하고 두번째 문자랑 더해서 유니크한 숫자를 만들어줍니다.
                // 대문자의 아스키코드 범위는 65 ~ 90
                // 예) AB -> 6566
                let num = first_ch * 100 + second_ch;
                
                // 유니크한 숫자의 개수를 1증가시켜줍니다.
                check[i][num]++;
            }
        }
    }
    
    /*
        3. 전체 문자를 검사합니다.
        숫자의 최소값은 6565 -> AA
        숫자의 최대값은 9090 -> ZZ
        즉, AA에서 ZZ까지 검사합니다.
     */
    let duple_cnt=0, total_cnt=0, jaccard=0
    for(let i=min_int; i<=max_int; i++){
        // 1) 합집합은 각 숫자의 최대개수
        total_cnt += max(check[0][i], check[1][i]);
        
        // 2) 교집합은 각 숫자의 최소개수
        duple_cnt += min(check[0][i], check[1][i]);
    }
    
    // 4. 자카드 유사도를 계산합니다.
    // 두 집합이 모두 공집합인 경우 total_cnt == 0 입니다.
    
    // 1) 두 집합이 모두 공집합이 아닌 경우
    if(total_cnt != 0){
        // 실수 계산을 하고
        jaccard = duple_cnt / total_cnt;
        answer = base_num * jaccard;
    }
    // 2) 두 집합이 모두 공집합인 경우
    else{
        // 규칙에 따라 656636을 넣어줍니다.
        answer = base_num;
    }
    
    return Math.floor(answer);
}