뉴스 클러스터링
풀이1
function makeDajung(str){
const result = []
for(let i=0;i<str.length-1;i++){
const target = str.slice(i,i+2).match(/([a-zA-Z])/gi);
if(target && target.length === 2){
result.push(target.join(""))
}
}
return result;
}
function getIntersectionNum(first,second){
let result = [];
[...new Set(first)].forEach((element)=>{
if(second.includes(element)){
// is Intersection Element
const firstEl = first.filter((temp)=>temp === element)
const secondEl = second.filter((temp)=>temp === element)
if(firstEl.length < secondEl.length){
result = result.concat(firstEl);
}else{
result = result.concat(secondEl);
}
}
})
return result;
}
function getUnionNum(first,second){
let result = [];
const firstSet = [...new Set(first)];
const secondSet = [...new Set(second)]
firstSet.forEach((element)=>{
if(second.includes(element)){
const firstEl = first.filter((temp)=>temp === element)
const secondEl = second.filter((temp)=>temp === element)
if(firstEl.length < secondEl.length){
result = result.concat(secondEl);
}else{
result = result.concat(firstEl);
}
}else{
const firstEl = first.filter(temp=>temp===element);
result = result.concat(firstEl);
}
})
secondSet.forEach((element)=>{
if(first.includes(element)){
// isIntersect
}else{
const secondEl = second.filter(temp=>temp===element);
result = result.concat(secondEl);
}
})
return result;
}
function solution(str1,str2){
// 다중집합을 구하고
const first = makeDajung(str1.toLowerCase());
const second = makeDajung(str2.toLowerCase());
// 둘다 공집합이면 65536
if(first.length === 0 && second.length === 0){
return 65536;
}
// 다중집합들의 교집합과 합집합을 구한다.
const inter = getIntersectionNum(first,second);
const union = getUnionNum(first,second);
return Math.floor((inter.length/union.length) * 65536)
}풀이2
풀이1의 방식엔 너무 불필요한 코드가 많아 삭제하고 다음과 같이 리팩토링하였다.
function makeDajung(str){
const result = [];
for(let i=0;i<str.length-1;i++){
const tar = str.slice(i,i+2).match(/[a-zA-Z]/gi);
if(tar && tar.length === 2) result.push(tar.join(""));
}
return result;
}
function getInterUnionNum(bothAB,A,B,onlyA,onlyB){
let gyo = []
let hap = []
bothAB.forEach(el => {
const interA = A.filter(ael => ael === el);
const interB = B.filter(bel => bel === el);
if(interA.length < interB.length){
gyo = gyo.concat(interA);
hap = hap.concat(interB);
}else{
gyo = gyo.concat(interB);
hap = hap.concat(interA);
}
})
return [gyo,[...onlyA,...hap,...onlyB]]
}
function solution(str1,str2){
// 자신만의 원소 - 공통원소를 구하면 더 쉽게할 수 있을것같다.
const A = makeDajung(str1.toLowerCase());
const B = makeDajung(str2.toLowerCase());
if(A.length === 0 && B.length === 0) return 65536;
// 자신만의 원소와 공통 원소들을 구한다. 이 때 자신만의 원소는 중복이 되어서는 안됨. 공통 원소는 이들을 순회하며 각 집합에 몇개씩있는지 판별해야하므로 중복을 제거해주어야 더 수월하다.
const onlyA = A.filter(el=>!B.includes(el))
const onlyB = B.filter(el=>!A.includes(el))
const bothAB = [...new Set(A.filter(el=>B.includes(el)))]
// 교집합과 합집합을 구했으므로
const [inter,union] = getInterUnionNum(bothAB,A,B,onlyA,onlyB);
// 자카드 유사도 도출가능
return Math.floor((inter.length/union.length)*65536)
}- 설명은 주석에 있다.
풀이3
굳이 교집합 합집합을 구할 필요는 없다. 우리는 갯수만 알면 되므로 다음과 같이 풀수도있다.
function solution(str1,str2){
const A = makeDajung(str1.toLowerCase());
const B = makeDajung(str2.toLowerCase());
if(A.length === 0 && B.length === 0) return 65536;
let inter = 0;
let union = 0;
const AB = [...new Set([...A,...B])];
AB.forEach(el=>{
// 중복이 제거된 모든 요소 집합을 돈다.
const a = A.filter(ael => ael === el).length;
const b = B.filter(bel => bel === el).length;
if(a===0 || b===0){
// 한쪽에만 포함된 요소이므로 union에 값을 더해준다.
union += a + b;
}else{
// 양쪽에 포함된 요소이므로 다중집합의 교집합 합집합의미에 맞게 값을 더해준다.
inter += Math.min(a,b);
union += Math.max(a,b);
}
})
return Math.floor((inter/union) * 65536)
}거리두기
- 참고 사진 1
function isValidate(place){
// 맨해튼 거리가 1인 경우
const mht_1_x = [0,0,-1,1]
const mht_1_y = [-1,1,0,0]
// 맨해튼 거리가 2인 경우
const mht_2_x = [0,2,-2,0,-1,1,1,-1]
const mht_2_y = [2,0,0,-2,-1,1,-1,1]
for(let i=0;i<place.length;i++){
for(let j=0;j<place[i].length;j++){
if(place[i][j] === 'P'){
// 사람이 등장하면 맨해튼거리1 , 맨해튼거리2 위치에 사람이 있는지를 점검한다.
// 맨해튼 거리 1인 경우
for(let k=0;k<mht_1_x.length;k++){
const cx = i+mht_1_x[k];
const cy = j+mht_1_y[k];
// 1인 경우에 사람이 있으면 무조건 false 이다.
if(place[cx] && place[cx][cy] && place[cx][cy] === 'P') return false;
}
// 맨해튼 거리 2인 경우
for(let k=0;k<mht_2_x.length;k++){
const cx = i+mht_2_x[k];
const cy = j+mht_2_y[k];
// 2인 자리에 사람이 있다면 ?
if(place[cx] && place[cx][cy] === 'P'){
// 로우가 같다면 사이에 좌석이 비었는지를 점검 -> 비어있으면 false;
if(cx === i ){
if(cy > j && place[cx][cy - 1] === 'O'){
return false;
}
if(cy < j && place[cx][cy + 1] === 'O' ){
return false;
}
}
// 컬럼이 같다면 사이에 좌석이 비었는지를 점검 -> 비어있으면 false;
if(cy === j){
if(cx > i && place[cx-1][cy] === 'O') return false;
if(cx < i && place[cx+1][cy] === 'O') return false;
}
if(cx !== i && cy !== j){
// 로우와 컬럼 모두 다른 경우는 대각의 경우이다.
// 대각의 경우 참고사진 1과 같은지를 점검한다.
if(place[i+mht_2_x[k]][j] === 'O' || place[i][j+mht_2_y[k]] === 'O') return false;
}
}
}
}
}
}
위 과정이 모두 통과되면 true
return true;
}
function solution(places){
return places.map(place => {
// 대기실
return isValidate(place) ? 1 : 0;
})
}수식최대화
풀이1 using array
const priorityCase = ["*-+","*+-","+*-","+-*","-+*","+-*"]
function compute(first,second,exp){
if(exp === '*'){
return `${+first * +second}`;
}
if(exp === '-'){
return `${+first - +second}`;
}
if(exp === '+'){
return `${+first + +second}`;
}
}
function getPrize(exp,pri){
pri.forEach(op=>{
for(let i = 0;i<exp.length;i++){
if(exp[i] === op){
const value = compute(exp[i-1],exp[i+1],exp[i]);
exp.splice(i-1,3,value);
i = i - 1;
}
}
})
return Math.abs(+exp[0]);
}
function solution(expression){
let answer = 0;
const exp = expression.split(/([-*+])/gi)
priorityCase.forEach(priority=>{
const result = getPrize([...exp],priority.split(""));
answer = Math.max(answer,result);
})
return answer;
}풀이2 using stack
const priorityCase = ["*-+","*+-","+*-","+-*","-+*","+-*"]
function compute(first,second,exp){
if(exp === '*'){
return `${+first * +second}`;
}
if(exp === '-'){
return `${+first - +second}`;
}
if(exp === '+'){
return `${+first + +second}`;
}
}
function getPrize(exp,pri){
pri.forEach(op=>{
const stack = [];
let i = 0;
while(i<exp.length){
if(exp[i] === op){
stack.push(compute(stack.pop(),exp[i+1],op));
i = i + 2;
}else{
stack.push(exp[i]);
i = i + 1;
}
}
// 스택에 넣어놓은 걸 다음에 순회한다.
exp = [...stack];
})
return Math.abs(+exp[0]);
}
function solution(expression){
let answer = 0;
const exp = expression.split(/([-*+])/gi)
priorityCase.forEach(priority=>{
const result = getPrize([...exp],priority.split(""));
answer = Math.max(answer,result);
})
return answer;
}
Frontend Ninja