728x90
programmers.co.kr/learn/courses/30/lessons/17677
코딩테스트 연습 - [1차] 뉴스 클러스터링
뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브
programmers.co.kr
#include <string>
#include <map>
#include <iostream>
using namespace std;
int solution(string str1, string str2) {
int answer = 0;
map<string,int>m;
map<string,int>m2;
/* for(int i=0; i<str1.size(); i++){
if(!isalpha(str1[i])){
str1.erase(i,1);
if(i>0)--i;
}
}
for(int i=0; i<str2.size(); i++){
if(!isalpha(str2[i])){
str2.erase(i,1);
if(i>0)--i;
}
}*/
for(int i=0; i<str1.size(); i++){
string elem = str1.substr(i,2);
if(elem.size()==1){break;}
int toggle = false;
for(int j=0; j<2; j++){
if(!isalpha(elem[j])){
toggle = true;
break;
}
}
if(toggle == true){continue;}
for(int j=0; j<2; j++){
if(isupper(elem[j])){
elem[j]=tolower(elem[j]);
} }
++m[elem];
}
for(int i=0; i<str2.size(); i++){
string elem = str2.substr(i,2);
if(elem.size()==1){break;}
int toggle = false;
for(int j=0; j<2; j++){
if(!isalpha(elem[j])){
toggle = true;
break;
}
}
if(toggle == true){continue;}
for(int j=0; j<2; j++){
if(isupper(elem[j])){
elem[j]=tolower(elem[j]);
}
}
// cout<<elem<<endl;
++m2[elem];
}
map<string,int>::iterator it;
int sum=0;
int same=0;
for(auto it = m.begin(); it!=m.end(); it++){
if(m2.find(it->first)!=m2.end()){
same+=min(it->second,m2[it->first]);
sum+= max(it->second,m2[it->first]);
}
else{
sum+=it->second;
}
}
// cout<<sum<<endl;
for(auto it = m2.begin(); it!=m2.end(); it++){
if(m.find(it->first)==m.end()){
sum+=it->second;
}
}
// cout<<same<<endl;
// cout<<sum<<endl;
if(same==0 && sum ==0){return 65536;}
double a =same/((double)sum);
answer = a * 65536;
return answer;
}어떤 알고리즘 어떤 논리로?
- 그냥 모든 문자열을 탐색하고 자르면서 조건에 맞는 값을 구하는 것이다.
어려웠던 점
- 처음에 문제를 잘 못 읽어서 알파벳이 아닌 문자는 먼저 다 지우고 난다음에 2개씩 잘랐다. 근데 문제의 의도는 2개씩 자른다음에 알파벳이 아닌 문자가 나오면 해당 문자열은 없애는 것이었다.
<Java>
import java.util.regex.*;
import java.util.*;
class Solution {
public int solution(String str1, String str2) {
int answer = 0;
StringBuilder s1; //str1에서 두개씩 자른 문자열
StringBuilder s2; //str2에서 두개씩 자른 문자열
HashMap<String,Integer> hs1 = new HashMap<>(); //str1에서 두개씩 자른 문자열의 집합
HashMap<String,Integer> hs2 = new HashMap<>(); //str2에서 두개씩 자른 문자열의 집합
HashMap<String,Boolean> check = new HashMap<>(); // hs1과 hs2에모두 들어가 있는 문자열일 경우
str1=str1.toLowerCase(); //스트링을 소문자로 바꾸어주기
str2=str2.toLowerCase();
//str1을 두개 문자 씩 쪼개서 해시맵인hs1에 넣어준다.
for(int i=0; i<str1.length(); i++){
if(i==str1.length()-1){ //만약 마지막 문자일 경우
s1=new StringBuilder(str1.substring(i));
}
else{
s1=new StringBuilder(str1.substring(i,i+2)); //두개씩 자를 수 있는 경우
}
boolean toggle =true;
for(int j=0; j<s1.length(); j++){ //자른 두개의 문자열에서 알파벳이 아닌 경우가 있으면 집합에 포함을 하지 않는다.
if(s1.charAt(j)<'a'||s1.charAt(j)>'z'){
toggle =false;
break;
}
}
if(toggle==false){continue;}
if(s1.length()==2){
if(hs1.containsKey(s1.toString())){ // 이미 해쉬에 저장했을 경우
hs1.put(s1.toString(),hs1.get(s1.toString())+1); //기존 value에서 1을 더해줌, hash key 가 String 형이기때문에 s1.toString()을 key값으로 여겨야함!!
}
else{
hs1.put(s1.toString(),1); //해쉬에 저장이 안되어 있다면 value값은 1로 정한다.
}
}
}
//str2을 두개 문자 씩 쪼개서 해시맵인hs2에 넣어준다.
for(int i=0; i<str2.length(); i++){
if(i==str2.length()-1){
s2=new StringBuilder(str2.substring(i));
}
else{
s2=new StringBuilder(str2.substring(i,i+2));
}
boolean toggle =true;
for(int j=0; j<s2.length(); j++){
if(s2.charAt(j)<'a'||s2.charAt(j)>'z'){
toggle = false;
break;
}
}
if(toggle==false){continue;}
if(s2.length()==2){
// System.out.println(s2);
if(hs2.containsKey(s2.toString())){
hs2.put(s2.toString(),hs2.get(s2.toString())+1);
}
else{
hs2.put(s2.toString(),1);
}
// System.out.println(hs2.get(s2.toString()));
}
}
double min=0;
double max=0;
Set key = hs1.keySet();//hashmap의 key를 set으로 받은 후 iterator로 접근한다.
for(Iterator iterator = key.iterator(); iterator.hasNext();){
String keyValue = (String) iterator.next();
int value = hs1.get(keyValue);
if(hs2.containsKey(keyValue)){
min+=Math.min(value,hs2.get(keyValue));
check.put(keyValue,true);
}
else{
max+=value;
}
}
key = hs2.keySet();//hashmap의 key를 set으로 받은 후 iterator로 접근한다.
for(Iterator iterator = key.iterator(); iterator.hasNext();){
String keyValue =(String)iterator.next();
if(!check.containsKey(keyValue)){
max+=hs2.get(keyValue);
}
else{
max+=Math.max(hs2.get(keyValue),hs1.get(keyValue));
}
}
if(max==0 && min==0){return 65536;}
double c = min/max;
c = c*65536;
answer=(int)c;
return answer;
}
}1.hashmap 두개를 이용해서 풀었다
2.문자열1을 두개씩 잘라서 맵에 기록한다. : 맵1(hs1)
3.문자열2를 두개씩 잘라서 맵에 기록한다 : 맵2(hs2)
4.hs1을 iterator로 돌면서 특정 key 값이 hs2의 map에도 존재하는지 확인
-> 있으면 hs1과 hs2중 최소값을 min(교집합 개수) 에 더해준다. 그리고 두 맵의 공통키인지를 기록하는 check 맵에 true로 체크해준다.
-> 없으면 max에 해당 key 에 대한 value를 넣어준다
5.hs2을 iterator로 돌면서 특정 key 값이 hs1의 map에도 존재하는지 확인
-> 있으면 hs1과 hs2중 최대값을 max(합집합 개수) 에 더해준다.
-> 없으면 max에 해당 key에 대한 value를 넣어준다.
너무 복잡하게 푼것 같다. 좀더 쉬운 방법을 생각할 필요도 있다.