(2018카카오) 뉴스 클러스터링 Java

a-z

소문자

일반적인 중복이 없는 교집합/합집합 문제였으면 쉽게 풀렸을텐데(HashMap,Set이용)

 

까다로운 조건이 추가되어 애매한 교집합/합집합 문제였다.

 

기획안

/*
​​​​​​​​0. 대문자=>소문자로 일괄 변환해버린다.
​​​​​​​​1. str 2개씩 쪼개기
​​​​​​​​2. 쪼개면서 영문자가 아닌 문자들은 제외.
​​​​​​​​3. 쪼갠건 Queue에 넣어놓는다.(x) -> q1,q2로 카운팅으로 대체
​​​​​​​​4. 2개의 Map에 key, 중복포함개수(value) 저장
​​​​​​​​5. Map의 key에 따라서 중복된 key값이 있으면 value값을 비교.
​​​​​​​​=> 두 map에 같은 key값이 있는경우, 각 중복원소에따른 value카운트값을 queue에 넣는다.
​​​​​​​​7.1 (A+B) - (AnB) = AuB 값
​​​​​​​​7.2 (AnB) / (AuB) * 65536 = answer
*/

1. toLowercase()메소드를 이용해서 소문자로 변환한다.

2. charAt을 이용해서 Ascii 코드의 범위를 이용해서 해당 소문자 구간이 아니면 버린다.

 

필자의 코드는 아래와 같다.

import java.util.*;

class Solution {
​​​​int q1=0, q2=0;
​​​​HashMap<String, Integer> map1 = new HashMap<>();//합집합용AUB
​​​​HashMap<String, Integer> map2 = new HashMap<>();//합집합용AUB

​​​​public void fun(String str) {
​​​​​​​​for (int i = 0; i < str.length() - 1; i++) {//i+1 오버플로우 안남.
​​​​​​​​​​​​char front = str.charAt(i);
​​​​​​​​​​​​char rear = str.charAt(i + 1);

​​​​​​​​​​​​if (front >= 97 && front <= 122 && rear >= 97 && rear <= 122) {
​​​​​​​​​​​​​​​​String s = front + "" + rear;
​​​​​​​​​​​​​​​​q2++;
​​​​​​​​​​​​​​​​map2.put(s, map2.getOrDefault(s, 0) + 1);
​​​​​​​​​​​​} else {
​​​​​​​​​​​​​​​​//버려
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}

​​​​public int solution(String str1, String str2) {
​​​​​​​​str1 = str1.toLowerCase();
​​​​​​​​str2 = str2.toLowerCase();
​​​​​​​​Queue<Integer> n = new LinkedList<>();//교집합 각 원소 개수 넣는것
​​​​​​​​int mult = 0;
​​​​​​​​fun(str1);
​​​​​​​​q1=q2;
​​​​​​​​q2=0;
​​​​​​​​map1=map2;//대입 전달이안돼서,,
​​​​​​​​map2=new HashMap<>();//초기화
​​​​​​​​fun(str2);

​​​​​​​​int answer = 0;
​​​​​​​​int plus = q1+ q2;

​​​​​​​​for (Map.Entry<String, Integer> entry : map1.entrySet()) {
​​​​​​​​​​​​​​​​int val1 = entry.getValue();
​​​​​​​​​​​​​​​​String s = entry.getKey();
​​​​​​​​​​​​​​​​int val2 = map2.getOrDefault(s,0);
​​​​​​​​​​​​​​​​if(val2==0) continue;
​​​​​​​​​​​​​​​​else{
​​​​​​​​​​​​​​​​​​​​n.offer(val1>val2 ? val2 : val1);//교집합인것중 min
​​​​​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​while(!n.isEmpty()){
​​​​​​​​​​​​mult+=n.poll();
​​​​​​​​}

​​​​​​​​if (q1 == 0 && q2 == 0) return 65536;//둘다 공집합인경우 리턴1
​​​​​​​​answer = (int) (
​​​​​​​​​​​​​​​​(float)  mult / (plus -mult) * 65536
​​​​​​​​);

​​​​​​​​return answer;
​​​​}
}

 

 

성능이 더 좋은 다른 코드이다.

 

Java의 패턴(Pattern, Matcher) 정규표현식 활용한 코드이다.

 

정규 표현식	설명
^[0-9]*$	숫자
^[a-zA-Z]*$	영문자
^[가-힣]*$	한글
\\w+@\\w+\\.\\w+(\\.\\w+)?	E-Mail
^\d{2,3}-\d{3,4}-\d{4}$	전화번호
^01(?:0|1|[6-9])-(?:\d{3}|\d{4})-\d{4}$	휴대전화번호
\d{6} \- [1-4]\d{6}	주민등록번호
^\d{3}-\d{2}$	우편번호

 

coding-factory.tistory.com/529

[Java] 자바 정규 표현식 (Pattern, Matcher) 사용법 & 예제

1. 아래의코드에서는 정규식이 " ^[a-z]+$ "이다.

즉, a-z이므로 소문자인경우에만 List에 add한다.

 

2. 여기서도 교집합을 먼저 만드는 방식이다.

교집합의 원소를 하나씩 이중for문으로 찾고, conList(교집합리스트)에 더해주면 나머지 집합에서 remove한다.

import java.util.ArrayList;

class Solution {
​​public int solution(String str1, String str2) {
​​​​​​​​ArrayList<String> str1List = new ArrayList<>();
​​​​​​​​ArrayList<String> str2List = new ArrayList<>();
​​​​​​​​ArrayList<String> conList = new ArrayList<>();
​​​​​​​​ArrayList<String> finalSumList = new ArrayList<>();

​​​​​​​​String tempStr = "";
​​​​​​​​for(int i = 0; i < str1.length()-1; i++) {
​​​​​​​​​​​​tempStr = str1.substring(i, i+2).toLowerCase();
​​​​​​​​​​​​if(tempStr.matches("^[a-z]+$")) {
​​​​​​​​​​​​​​​​str1List.add(tempStr);
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​for(int i = 0; i < str2.length()-1; i++) {
​​​​​​​​​​​​tempStr = str2.substring(i, i+2).toLowerCase();
​​​​​​​​​​​​if(tempStr.matches("^[a-z]+$")) {
​​​​​​​​​​​​​​​​str2List.add(tempStr);
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​boolean bullshit = false;

​​​​​​​​if(str1List.size() == 0 & str2List.size() == 0) {
​​​​​​​​​​​​bullshit = true;
​​​​​​​​}

​​​​​​​​//교집합 만들기
​​​​​​​​for(int i = 0; i < str1List.size(); i++) {
​​​​​​​​​​​​for(int j = 0; j < str2List.size(); j++) {
​​​​​​​​​​​​​​​​if(str1List.get(i).equals(str2List.get(j))) {
​​​​​​​​​​​​​​​​​​​​conList.add(str2List.get(j));
​​​​​​​​​​​​​​​​​​​​str1List.remove(i);
​​​​​​​​​​​​​​​​​​​​str2List.remove(j);
​​​​​​​​​​​​​​​​​​​​i--;
​​​​​​​​​​​​​​​​​​​​j = -1;

​​​​​​​​​​​​​​​​​​​​break;
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​//합집합 만들기
​​​​​​​​finalSumList.addAll(str1List);
​​​​​​​​finalSumList.addAll(str2List);
​​​​​​​​finalSumList.addAll(conList);



​​​​​​​​float zacquard = 1;
​​​​​​​​if(bullshit == false) {
​​​​​​​​​​​​float con = (float) conList.size();
​​​​​​​​​​​​float sum = (float) finalSumList.size();
​​​​​​​​​​​​zacquard = (con / sum) * 65536;
​​​​​​​​}
​​​​​​​​else {
​​​​​​​​​​​​zacquard = zacquard * 65536;
​​​​​​​​}

​​​​​​​​int result = (int) zacquard;
​​​​​​​​return result;
​​}
}