๋ฌธ์ ๋งํฌ
์ฝ๋ฉํ ์คํธ ์ฐ์ต - [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);
}
}
}
'์ฝ๋ฉํ ์คํธ > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Javascript] n^2 ๋ฐฐ์ด ์๋ฅด๊ธฐ (87390) (0) | 2022.06.23 |
---|---|
[Javascript] 2๊ฐ ์ดํ๋ก ๋ค๋ฅธ ๋นํธ (77885) (0) | 2022.06.23 |
[Javascript] k์ง์์์ ์์ ๊ฐ์ ๊ตฌํ๊ธฐ (92335) (0) | 2022.06.23 |
[Javascript] ๋ ๋ฐ๋จน๊ธฐ (12913) (0) | 2022.06.23 |
[Javascript] ํผ๋ก๋ (87946) (0) | 2022.06.23 |