프로그래머스 뉴스 클러스터링 Java - 2018 카카오 블라인드 채용

05 April 2020 - 3 mins read time
Tags: 알고리즘 프로그래머스

문제

주어진 2개의 문자열을 2글자의 이어진 영문자로 자른 뒤 두 집합 사이의 교집합과 합집합을 바탕으로 계산하면 되는 문제이다.

A = {1, 2, 3} B = {2, 3, 4} 이면 합집합은 {1,2,3,4} 교집합은 {2,3} 이므로 2/4 * 65536 의 정수형은 반환하면 된다.

접근

두 문자열을 2글자의 이어진 영문자로 나누는 작업을 하여 집합을 만든다.
만들어진 두 집합 사이의 문자열을 비교하면서 교집합과 합집합의 수를 구한다.
제한사항(둘다 공집합이면 1 * 65536, 대소문자의 구분이 없음(aa = Aa), )

풀이

1번

int answer = 1; //65536

str1 = str1.toLowerCase();
str2 = str2.toLowerCase();

int or = 0;
int and = 0;

ArrayList<String> list = new ArrayList<>();
for(int i=1 ; i<str1.length() ; i++) {
    char c1 = str1.charAt(i-1);
    char c2 = str1.charAt(i);
    
    if(c1 >= 'a' && c1 <= 'z' && c2 >= 'a' && c2 <= 'z') {
        list.add(c1 + "" + c2);
    }
}

or = list.size();

for(int i=1 ; i<str2.length() ; i++) {
    char c1 = str2.charAt(i-1);
    char c2 = str2.charAt(i);
    
    if(c1 >= 'a' && c1 <= 'z' && c2 >= 'a' && c2 <= 'z') {
        String temp = c1 + "" + c2;
        
        if(list.contains(temp)) {
            and++;
            list.remove(temp);
        } else {
            or++;
        }
    }
}

if(or == 0 && and == 0) return answer * 65536;
else {			
    return (int) (65536 * (and/(double)or));
}

문자열을 분리하는 작업을 두 번하고 교집합과 합집합의 수를 구한것이 아니라 첫 번째 문자열을 이어진 2글자의 영문자로 만들어진 집합을 만들고 그 집합을 기준으로 삼았습니다.
문자열 집합을 만들기 전에 .toLowwerCase()를 통해 모두 소문자로 변경(숫자나 특수문자가 있더라도 영문자만 바뀌므로 상관이 없음)
기준 집합이 만들어지면 두 번째 문자열에서 2글자로 이어진 영문자를 만들고 기준 집합에 포함되어 있는지 판단하고 있으면 교집합의 수(and)를 1 증가 시키고 아니라면 합집합의 수(or)를 1 증가
교집합의 수를 구할 때 (aa, aa) & (aa, aa, aa) 의 경우 기준 집합에 넣을 때 있는 값은 제거해줘야 정확한 교집합의 수를 체크할 수 있음

이 문제에서 String 메소드인 toLowerCase(), charAt()에 대한 학습할 수 있다. 2개의 문자열의 집합을 모두 구한뒤에 교집합/합집합의 수를 구해도 되지만 집합을 하나 만드는 과정을 줄일 수있으므로 위의 풀이 방법은 실행시간을 조금이나마 단축시킬 수 있다.