[프로그래머스] Lv.2 : [1차] 뉴스 클러스터링

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

입력으로 들어온 각 문자열에 대해 두 글자씩 끊어서 Map에 (글자쌍, 글자쌍이 현재 문자열에서 등장한 횟수)를 저장한다.

똑같은 문자열이 두 번 이상 등장할 수 있는데, 이후 교집합이나 합집합을 구할 때 두 문자열에서 공통적으로 등장하는 글자쌍인 경우, 각 문자열의 해당 글자쌍이 등장한 횟수가 필요하기 때문에 Map을 사용하여 글자쌍이 현재 문자열에서 등장한 횟수도 저장해야 한다.

그 다음 교집합 원소의 개수와 합집합 원소의 개수를 구해 답을 반환한다.

로직

1. convertStrToPair() 메서드를 호출하여 첫번째 문자열에 대해 (글자 쌍, 글자쌍이 문자열에서 등장한 횟수)를 저장하는 Map을 구한다.

2. convertStrToPair() 메서드를 호출하여 두번째 문자열에 대해 (글자 쌍, 글자쌍이 문자열에서 등장한 횟수)를 저장하는 Map을 구한다.

3. 두 Map과 getIntersectionNumber() 메서드를 호출하여 두 문자열의 교집합의 개수를 구한다.

4. 두 Map과 getUnionNumber() 메서드를 호출하여 두 문자열의 합집합의 개수를 구한다.

5. 합집합의 개수가 0이라면 65536을 바로 리턴한다.

6. (교집합의 개수/합집합의 개수 * 65536)에서 소수점을 버린 정수값을 리턴한다.

Map<String, Integer> convertStrToPair(String str) : str 문자열을 두 글자씩 끊어서 생성한 (글자 쌍, 글자 쌍이 현재 문자열에서 등장한 횟수)를 저장한 Map을 리턴한다.

    static Map<String, Integer> convertStrToPair(String str) {
        Map<String, Integer> strPair = new HashMap<>();
        
        for (int i = 0; i < str.length() - 1; i++) {
            String subStr = str.substring(i, i+2);
            
            if (!Character.isAlphabetic(subStr.charAt(0)) || !Character.isAlphabetic(subStr.charAt(1)))
                continue;
            
            subStr = subStr.toUpperCase();
            
            strPair.put(subStr, strPair.getOrDefault(subStr, 0) + 1);
        }
        return strPair;
    }

문자열을 두글자씩 끊어서 글자 쌍을 구할 때, 영문자가 아닌 다른 문자가 있으면 그 글자 쌍은 무시한다.
대소문자를 구분하지 않으므로 글자 쌍을 모두 대문자로 변환한 뒤 Map에 저장한다.

int getIntersectionNumber(Map<String, Integer> firstStrPair, Map<String, Integer> secondStrPair) : 두 Map을 사용하여 교집합 원소의 개수를 리턴한다.

    static int getIntersectionNumber(Map<String, Integer> firstStrPair, Map<String, Integer> secondStrPair) {
        Map<String, Integer> intersection = new HashMap<>();

        firstStrPair.forEach((key, value) -> {
            if (secondStrPair.containsKey(key)) {
                intersection.put(key, Math.min(firstStrPair.get(key), secondStrPair.get(key)));
            }
        });
        
        return intersection.values().stream().mapToInt(e -> e).sum();
    }

새로운 Map intersection을 생성한다.
firstStrPair, secondStrPair에서 공통적으로 가지고 있는 글자 쌍에 대해 (글자 쌍, 교집합에서 글자쌍 원소의 개수)를 intersection에 저장한다.
intersection의 value 값을 모두 더한 값을 반환한다.

int getUnionNumber(Map<String, Integer> firstStrPair, Map<String, Integer> secondStrPair) : 두 Map을 사용하여 합집합 원소의 개수를 리턴한다.

    static int getUnionNumber(Map<String, Integer> firstStrPair, Map<String, Integer> secondStrPair) {
        Map<String, Integer> union = new HashMap<>();

        firstStrPair.forEach((key, value) -> {
            if (secondStrPair.containsKey(key)) {
                union.put(key, Math.max(value, secondStrPair.get(key)));
            }
            else {
                union.put(key, value);
            }
        });
        
        secondStrPair.forEach((key, value) -> {
            if (!firstStrPair.containsKey(key)) {
                union.put(key, secondStrPair.get(key));
            }
        });
        
        return union.values().stream().mapToInt(e -> e).sum();
    }

새로운 Map union을 생성한다.
스트림을 사용하여, firstStrPair, secondStrPair에서 공통적으로 가지고 있는 글자 쌍에 대해 (글자 쌍, 합집합에서 글자쌍 원소의 개수)를 union에 저장한다.
firstStrPair, secondStrPair 각각 자신만 가지고 있는 글자 쌍에 대해 (글자 쌍, 합집합에서 글자쌍 원소의 개수)를 union에 저장한다.
union의 value 값을 모두 더한 값을 반환한다.

전체 코드

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        Map<String, Integer> firstStrPair = convertStrToPair(str1);
        Map<String, Integer> secondStrPair = convertStrToPair(str2);
        
        int intersectionNumber = getIntersectionNumber(firstStrPair, secondStrPair);
        int unionNumber = getUnionNumber(firstStrPair, secondStrPair);
        
        if (unionNumber == 0) return 65536;
        return (int)Math.floor((double)intersectionNumber/unionNumber * 65536);
    }
    
    static Map<String, Integer> convertStrToPair(String str) {
        Map<String, Integer> strPair = new HashMap<>();
        
        for (int i = 0; i < str.length() - 1; i++) {
            String subStr = str.substring(i, i+2);
            
            if (!Character.isAlphabetic(subStr.charAt(0)) || !Character.isAlphabetic(subStr.charAt(1)))
                continue;
            
            subStr = subStr.toUpperCase();
            
            strPair.put(subStr, strPair.getOrDefault(subStr, 0) + 1);
        }
        return strPair;
    }
    
    static int getIntersectionNumber(Map<String, Integer> firstStrPair, Map<String, Integer> secondStrPair) {
        Map<String, Integer> intersection = new HashMap<>();

        firstStrPair.forEach((key, value) -> {
            if (secondStrPair.containsKey(key)) {
                intersection.put(key, Math.min(firstStrPair.get(key), secondStrPair.get(key)));
            }
        });
        
        return intersection.values().stream().mapToInt(e -> e).sum();
    }
    
    static int getUnionNumber(Map<String, Integer> firstStrPair, Map<String, Integer> secondStrPair) {
        Map<String, Integer> union = new HashMap<>();

        firstStrPair.forEach((key, value) -> {
            if (secondStrPair.containsKey(key)) {
                union.put(key, value, secondStrPair.get(key)));
            }
            else {
                union.put(key, value);
            }
        });
        
        secondStrPair.forEach((key, value) -> {
            if (!firstStrPair.containsKey(key)) {
                union.put(key, secondStrPair.get(key));
            }
        });
        
        return union.values().stream().mapToInt(e -> e).sum();
    }
}

수정한 코드

convertStrToPair() 메서드를 호출하기 전 두 문자열을 미리 모두 대문자로 변환한다.
getIntersectionNumber() 메서드를 stream을 사용하여 return 한 줄로 작성한다.
getIntersectionNumber() 메서드에서 처음 Map을 생성할 때 생성자 인자로 secondStrPair를 전달한다.
두 문자열의 유사도를 출력할 때 Math.floor()를 사용할 필요없이 (int)를 사용하면 정수부만 반환한다.

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        
        Map<String, Integer> firstStrPair = convertStrToPair(str1);
        Map<String, Integer> secondStrPair = convertStrToPair(str2);
        
        int intersectionNumber = getIntersectionNumber(firstStrPair, secondStrPair);
        int unionNumber = getUnionNumber(firstStrPair, secondStrPair);
        
        if (unionNumber == 0) return 65536;
        return (int)((double)intersectionNumber/unionNumber * 65536);
    }
    
    static Map<String, Integer> convertStrToPair(String str) {
        Map<String, Integer> strPair = new HashMap<>();
        
        for (int i = 0; i < str.length() - 1; i++) {
            String subStr = str.substring(i, i+2);
            
            if (!Character.isAlphabetic(subStr.charAt(0)) || !Character.isAlphabetic(subStr.charAt(1)))
                continue;
            
            strPair.put(subStr, strPair.getOrDefault(subStr, 0) + 1);
        }
        return strPair;
    }
    
    static int getIntersectionNumber(Map<String, Integer> firstStrPair, Map<String, Integer> secondStrPair) {

        return firstStrPair.entrySet()
            .stream()
            .filter(entry -> secondStrPair.containsKey(entry.getKey()))
            .map(entry -> Math.min(firstStrPair.get(entry.getKey()), secondStrPair.get(entry.getKey())))
            .mapToInt(e -> e)
            .sum();
        
    }
    
    static int getUnionNumber(Map<String, Integer> firstStrPair, Map<String, Integer> secondStrPair) {
        Map<String, Integer> union = new HashMap<>(secondStrPair);
        firstStrPair.forEach((key, value) -> {
            if (secondStrPair.containsKey(key)) {
                union.put(key, Math.max(value, secondStrPair.get(key)));
            }
            else {
                union.put(key, value);
            }
        });
        
        return union.values().stream().mapToInt(e -> e).sum();
    }
}

스트림을 사용하지 않은 풀이

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        
        Map<String, Integer> map1 = convertStrToPair(str1);
        Map<String, Integer> map2 = convertStrToPair(str2);
        
        int intersectNum = getIntersectionNumber(map1, map2);
        int unionNum = getUnionNumber(map1, map2);
        
        if (unionNum == 0) return 65536;
        return (int)((double)intersectNum / unionNum * 65536);
    }
    
    static Map<String, Integer> convertStrToPair(String str) {
        Map<String, Integer> map = new HashMap<>();
        
        for (int i = 0; i < str.length() - 1; i++) {
            String subStr = str.substring(i, i+2);
            
            if (!Character.isAlphabetic(subStr.charAt(0)) || !Character.isAlphabetic(subStr.charAt(1))) continue;
            
            map.put(subStr, map.getOrDefault(subStr, 0) + 1);
        }
        
        return map;
    }
    
    static int getIntersectionNumber(Map<String, Integer> firstStrPair, Map<String, Integer> secondStrPair) {
        int cnt = 0;
        for (String key: firstStrPair.keySet()) {
            if (secondStrPair.containsKey(key)) {
                cnt += Math.min(firstStrPair.get(key), secondStrPair.get(key));
            }
        }
        
        return cnt;
    }
    
    static int getUnionNumber(Map<String, Integer> firstStrPair, Map<String, Integer> secondStrPair) {
        int cnt = 0;
        for (String key: firstStrPair.keySet()) {
            if (secondStrPair.containsKey(key)) {
                cnt += Math.max(firstStrPair.get(key), secondStrPair.get(key));
            }
            else cnt += firstStrPair.get(key);
        }
        
        for (String key: secondStrPair.keySet()) {
            if (firstStrPair.containsKey(key)) continue;
            
            cnt += secondStrPair.get(key);
        }
        
        return cnt;
    }
}

728x90

'Algorithm 문제 풀이 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] Lv.1 : 완주하지 못한 선수 - 자바[Java] (0)	2023.04.11
[프로그래머스] Lv.1 : 숫자 문자열과 영단어 - 자바[Java] (0)	2022.11.15
[프로그래머스] Lv.2 : 튜플 - 자바[Java] (0)	2022.11.09
[프로그래머스] Lv.2 : 배달 (그래프 최단 경로 알고리즘) - 자바[Java] (0)	2022.11.08
[프로그래머스] Lv.2 : 방문 길이 - 자바[Java] (0)	2022.11.06

풀이

로직

전체 코드

수정한 코드

스트림을 사용하지 않은 풀이

'Algorithm 문제 풀이 > 프로그래머스' 카테고리의 다른 글

검색 태그

티스토리툴바