๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

[Javascript] 1์ฐจ ๋‰ด์Šค ํด๋Ÿฌ์ŠคํŠธ๋ง (17677)

๋ฌธ์ œ๋งํฌ

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - [1์ฐจ] ๋‰ด์Šค ํด๋Ÿฌ์Šคํ„ฐ๋ง

๋‰ด์Šค ํด๋Ÿฌ์Šคํ„ฐ๋ง ์—ฌ๋Ÿฌ ์–ธ๋ก ์‚ฌ์—์„œ ์Ÿ์•„์ง€๋Š” ๋‰ด์Šค, ํŠนํžˆ ์†๋ณด์„ฑ ๋‰ด์Šค๋ฅผ ๋ณด๋ฉด ๋น„์Šท๋น„์Šทํ•œ ์ œ๋ชฉ์˜ ๊ธฐ์‚ฌ๊ฐ€ ๋งŽ์•„ ์ •์ž‘ ํ•„์š”ํ•œ ๊ธฐ์‚ฌ๋ฅผ ์ฐพ๊ธฐ๊ฐ€ ์–ด๋ ต๋‹ค. Daum ๋‰ด์Šค์˜ ๊ฐœ๋ฐœ ์—…๋ฌด๋ฅผ ๋งก๊ฒŒ ๋œ ์‹ ์ž…์‚ฌ์› ํŠœ๋ธŒ

programmers.co.kr

 

์ ‘๊ทผ ๋ฐฉ๋ฒ•

๋ฐฐ์—ด์ด ์•„๋‹Œ Hash Table์„ ์‚ฌ์šฉํ•ด๋ณด๊ธฐ ์œ„ํ•ด Map ๊ฐ์ฒด๋ฅผ ์ ์šฉํ•ด๋ณด์•˜๋‹ค.

๋จผ์ € ์ฃผ์–ด์ง„ ๋ฌธ์ž์—ด str1, str2์„ ๋Œ€๋ฌธ์ž๋กœ ๋ณ€ํ™˜ํ•˜๊ณ  2๊ธ€์ž์”ฉ ์ž๋ฅธ ๋ฌธ์ž๋ฅผ ๋‹ด์„ Map ๊ฐ์ฒด๋ฅผ ๋งŒ๋“ค์—ˆ๋‹ค.

const sliceStr = (str, strMap) => {
    const regChar = /[A-Z]/;
    for(let i = 0; i<str.length-1; i++){
        if(regChar.test(str[i]) && regChar.test(str[i+1])){
            const subStr = str.substr(i,2);
            strMap.has(subStr) ? strMap.set(subStr, strMap.get(subStr)+1) : strMap.set(subStr, 1);   
        }
    } 
}โ€‹

์ฃผ์–ด์ง„ ๋ฌธ์ž์—ด์„ ๋Œ€๋ฌธ์ž์ผ ๊ฒฝ์šฐ๋งŒ 2๊ธ€์ž์”ฉ ์ž๋ฅด๋Š” ํ•จ์ˆ˜์ด๋‹ค.
์ •๊ทœ์‹์ด true(test ์‚ฌ์šฉ)์ผ ๋•Œ๋งŒ str์˜ substr(index, ๊ฐœ์ˆ˜)๋ฅผ ์ž˜๋ผ Map์— ๋‹ด๋Š”๋‹ค.

(3ํ•ญ ์—ฐ์‚ฐ์ž๋ฅผ ์ด์šฉํ•œ Map ๊ฐ์ฒด์— key์™€ value๋ฅผ ๋„ฃ๋Š” ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•˜์˜€๋‹ค.)


๋‹ค์Œ์œผ๋กœ ํ•ฉ์ง‘ํ•ฉ์˜ ์›์†Œ ์ˆ˜์™€ ๊ต์ง‘ํ•ฉ์˜ ์›์†Œ ์ˆ˜๋ฅผ ๋‹ด์„ ๋ณ€์ˆ˜๋ฅผ ์„ ์–ธํ•˜๊ณ  str2Map์„ ๊ธฐ์ค€์œผ๋กœ ์ง‘ํ•ฉ์„ ์ฑ„์› ๋‹ค.

for(let s2Cnt of str2Map.values()) unionCnt += s2Cnt;

str2Map์˜ values์˜ ๋ชจ๋“  ๊ฐ’์„ ์šฐ์„  ํ•ฉ์ง‘ํ•ฉ์— ๋”ํ•จ.

for(let s1 of str1Map){
    const [str, cnt] = s1;
    if(str2Map.has(str) && str2Map.get(str) >= str1Map.get(str)) intersectionCnt += cnt;
    else if(str2Map.has(str) && str2Map.get(str) < str1Map.get(str)) {
        intersectionCnt += str2Map.get(str);
        unionCnt += (str1Map.get(str) - str2Map.get(str))
    }
    else unionCnt += cnt;
}

 ๋‹ค์Œ์œผ๋กœ str1Map์˜ ๊ฐ’๋“ค์„ ํ†ตํ•ด ๋‚˜๋จธ์ง€ ์ง‘ํ•ฉ์„ ์ฑ„์› ๋‹ค.

if(str2Map.has(str) && str2Map.get(str) >= str1Map.get(str)) intersectionCnt += cnt;


1. ๋งŒ์•ฝ str1Map์˜ str์ด str2Map์— ์žˆ๊ณ  str2Map์˜ str ์ˆ˜๊ฐ€ str1Map์˜ str ์ˆ˜๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์„ ๋•Œ.
์ฆ‰, "AB"๋ž€ ๋ฌธ์ž๊ฐ€ str2Map์—๋Š” 2๊ฐœ, str1Map์—๋Š” 1๊ฐœ๊ฐ€ ์žˆ์„ ๋•Œ 1๊ฐœ๋งŒํผ ๋”ํ•œ๋‹ค.

else if(str2Map.has(str) && str2Map.get(str) < str1Map.get(str)) {
    intersectionCnt += str2Map.get(str);
    unionCnt += (str1Map.get(str) - str2Map.get(str))
}

 2. ๋งŒ์•ฝ str1Map์˜ str์ด str2Map์— ์žˆ๊ณ  str1Map์˜ str ์ˆ˜๊ฐ€ str2Map์˜ str ์ˆ˜๋ณด๋‹ค ์ž‘์„ ๋•Œ.
์ฆ‰, "AB"๋ž€ ๋ฌธ์ž๊ฐ€ str2Map์—๋Š” 1๊ฐœ, str1Map์—๋Š” 2๊ฐœ๊ฐ€ ์žˆ์„๋•Œ 
 2.1 ๊ต์ง‘ํ•ฉ์—๋Š” ๋” ์ž‘์€ ๊ฐ’์ธ str2Map.get(str)์˜ ์ˆ˜ ๋งŒํผ ๋”ํ•œ๋‹ค.
 2.2 ํ•ฉ์ง‘ํ•ฉ์—๋Š” ์•„๊นŒ str2Map์˜ "AB"์ธ 1์ด ๋“ค์–ด๊ฐ”๋Š”๋ฐ, str1Map์— 2๊ฐœ๊ฐ€ ์žˆ์œผ๋ฏ€๋กœ
        str1Map.get(str) (2๊ฐœ) - str2Map.get(str) (1๊ฐœ) ๋งŒํผ ์ถ”๊ฐ€ ํ•ด์ค€๋‹ค.

else unionCnt += cnt;

3. ๋งŒ์•ฝ str1Map์˜ str์ด str2Map์—๋Š” ์—†์„ ๋•Œ,
ํ•ฉ์ง‘ํ•ฉ์— str1Map์˜ cnt๋งŒํผ ์ถ”๊ฐ€ํ•ด์ค€๋‹ค.

์ด๋ ‡๊ฒŒ ํ•ฉ์ง‘ํ•ฉ(union)๊ณผ ๊ต์ง‘ํ•ฉ(intersection)์˜ ์ˆ˜๋ฅผ ๊ตฌํ–ˆ์œผ๋ฏ€๋กœ ๋‘˜์„ ๋‚˜๋ˆ„๊ณ  65536์„ ๊ณฑํ•˜์—ฌ ์†Œ์ˆ˜์ ์„ ์ œ๊ฑฐํ•˜๋ฉด ๋œ๋‹ค.

(์˜ˆ์™ธ์ฒ˜๋ฆฌ => ํ•ฉ์ง‘ํ•ฉ, ๊ต์ง‘ํ•ฉ์˜ ์ˆ˜๊ฐ€ ๋ชจ๋‘ 0์ผ ๊ฒฝ์šฐ 65536์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค.)

function solution(str1, str2) {
    var answer = 0;
    let str1Map = new Map();
    let str2Map = new Map();
    str1 = str1.toUpperCase()
    str2 = str2.toUpperCase()

    sliceStr(str1, str1Map);
    sliceStr(str2, str2Map);
    
    let intersectionCnt = 0;
    let unionCnt = 0;
    for(let s2Cnt of str2Map.values()) unionCnt += s2Cnt;
    for(let s1 of str1Map){
        const [str, cnt] = s1;
        if(str2Map.has(str) && str2Map.get(str) >= str1Map.get(str)) intersectionCnt += cnt;
        else if(str2Map.has(str) && str2Map.get(str) < str1Map.get(str)) {
            intersectionCnt += str2Map.get(str);
            unionCnt += (str1Map.get(str) - str2Map.get(str))
        }
        else unionCnt += cnt;
    }
    
    
    if(unionCnt === 0) return 65536;
    
    answer = Math.floor((intersectionCnt / unionCnt) * 65536)
    
    return answer;
}

const sliceStr = (str, strMap) => {
    const regChar = /[A-Z]/;
    for(let i = 0; i<str.length-1; i++){
        if(regChar.test(str[i]) && regChar.test(str[i+1])){
            const subStr = str.substr(i,2);
            strMap.has(subStr) ? strMap.set(subStr, strMap.get(subStr)+1) : strMap.set(subStr, 1);   
        }
    } 
}