정규표현식 ( regex )

프로그래머스 2018 KAKAO BLIND RECRUITMENT Level 2 문제 뉴스 클러스터링을 Java를 이용해 풀어보았다.
정규 표현식을 처음 사용해보는데 아주 기본적인 형태라서 바로 적용이 가능했다. 사실 이 문제를 풀기 직전에 2019 KAKAO BLIND RECRUITMENT 매칭 점수를 풀고 있었는데 정규 표현식이 처음이라 포기하고 넘어왔더니 또 정규 표현식 문제라 좀 웃겼다. 그래도 아주 기본적인 것만 사용하면 되는 문제라 연습 삼아 만난 것인가 하고 감사한 마음으로 풀었다.

문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/17677

---

영문자로만 이루어진 문자열 판별

단 두 글자만 영문자로, 대소 문자 상관없이 이루어져있는지 판별하면 됐다.
이 경우에는 Pattern을 작성하는 것이 비교적 간단하다.

Pattern p = Pattern.compile("^[a-zA-Z]*$");
Matcher m = p.matcher(대상 문자열);

위와 같이 작성하면 된다.

문제에서 요구하는 것은 주어진 문자열 하나를 두 글자씩 잘라냈을 때 영문자로만 이루어졌으면 하나의 원소로 인정하는 것이었다.
이는 다음과 같이 코드로 표현할 수 있다. 나는 다중 집합을 ArrayList를 이용해 표현했다.

ArrayList<String> set = new ArrayList<>();
Pattern p = Pattern.compile("^[a-zA-Z]*$");

for(int i=0; i<str.length()-1; i++){
      StringBuilder sb = new StringBuilder();
      sb.append(str.charAt(i)); // 연달아 두 글자 붙여주고
      sb.append(str.charAt(i+1));
      Matcher m = p.matcher(sb.toString()); // 영문자인지 판별해주고
      if(m.find())   set.add(sb.toString()); // 맞으면 추가
      sb.append("");
}

---

교집합 원소 개수 구하기

위에서 본 것과 같이 두 문자열에 대해 각각 다중 집합 생성을 완료했으면 두 다중 집합의 교집합 원소 개수를 구해줘야 한다.

이는 다음과 같은 방식으로 구해줬다.
boolean[] 배열을 하나 선언해서 마지막에 true 값의 개수가 곧 교집합 원소 개수다.

어떤 방식으로 true로 만드는지 살펴보자.

두 다중 집합 중 한 녀석을 바깥 for문으로 위치시키고, 안쪽에 나머지 다중 집합을 for문으로 순회하며

1. 두 집합의 원소가 서로 일치하며
2. 방문한 적이 없다면
3. true로 갱신

이를 코드로 표현하면 다음과 같다.

static Integer getIntersection(){
        int res = 0;
        boolean[] visited = new boolean[str2Set.size()];

        L1:
        for(String s1: str1Set){
            for(int i=0; i<str2Set.size(); i++){
                if(visited[i])  continue;
                String s2 = str2Set.get(i);
                boolean flag = s1.equalsIgnoreCase(s2);
                if(flag) {
                    visited[i] = true;
                    continue L1; // 같은 원소를 찾았으면 바로 바깥 for문을 넘겨버린다
                }
            }
        }

        for(boolean flag: visited)
            if(flag)    res++;

        return res;
    }

위 코드에서 continue L1;이 왜 필요한지 한 번 보자.

(1,2,2)와 (1,1,2)가 두 다중 집합일 경우를 가정해보자.

집합 1의 첫 번째 원소인 1은 집합 2의 첫 번째 원소에서도 일치하지만 두 번째 원소와도 일치하기 때문에 1에 대해서만 두 번의 true가 찍히게 될 것이다. 하지만 교집합의 원소로서 1은 한 번만 나와야 하기 때문에, 바깥 집합 1의 첫 번째 원소인 1이 집합 2의 원소 중 동일한 녀석을 하나 찾았으면 바로 넘겨야 한다.

---

65536을 곱한 값 구해주기

이제 교집합 원소 개수까지 구했으면 최종 값을 구해주면 된다. 이를 표현한 코드는 아래와 같다.

int intersec = getIntersection();
double tmpAnswer = (double)intersec/(str1Set.size()+ str2Set.size()-intersec);
double answer = Math.floor(tmpAnswer*65536);

return (int)answer;

분자는 그대로 교집합 원소의 개수를 사용하면 되고, 합집합의 개수인 분모는 다중 집합 두 개의 원소수를 다 더해준 후 겹친 개수인 교집합 원소의 개수를 빼주면 된다.

소수점을 버리는 작업은 Math.floor() 메소드를 사용했다.

아래는 내가 제출한 전체 코드다.

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class NewClustering {
    static ArrayList<String> str1Set = new ArrayList<>();
    static ArrayList<String> str2Set = new ArrayList<>();

    static int solution(String str1, String str2) {
        makeStrSet(1, str1);
        makeStrSet(2, str2);
        if(str1Set.size()==0 && str2Set.size()==0)  return 65536;

        int intersec = getIntersection();
        double tmpAnswer = (double)intersec/(str1Set.size()+ str2Set.size()-intersec);
        double answer = Math.floor(tmpAnswer*65536);

        return (int)answer;
    }

    static void makeStrSet(int num, String str){
        ArrayList<String> set = new ArrayList<>();
        Pattern p = Pattern.compile("^[a-zA-Z]*$");

        for(int i=0; i<str.length()-1; i++){
            StringBuilder sb = new StringBuilder();
            sb.append(str.charAt(i));
            sb.append(str.charAt(i+1));
            Matcher m = p.matcher(sb.toString());
            if(m.find())   set.add(sb.toString());
            sb.append("");
        }

        if(num==1) {
            str1Set = new ArrayList<>(set);
            Collections.copy(str1Set, set);
        }
        else {
            str2Set = new ArrayList<>(set);
            Collections.copy(str2Set, set);
        }
    }

    static Integer getIntersection(){
        int res = 0;
        boolean[] visited = new boolean[str2Set.size()];

        L1:
        for(String s1: str1Set){
            for(int i=0; i<str2Set.size(); i++){
                if(visited[i])  continue;
                String s2 = str2Set.get(i);
                boolean flag = s1.equalsIgnoreCase(s2);
                if(flag) {
                    visited[i] = true;
                    continue L1;
                }
            }
        }

        for(boolean flag: visited)
            if(flag)    res++;

        return res;
    }

    public static void main(String args[]) throws IOException {
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str1 = "aa1+aa2";
        String str2 = "AAAA12";
        int result = solution(str1,str2);
        bfw.write(result + "");
        bfw.close();
    }
}