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

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

[Javascript] ๋ฌธ์ž์—ด ์••์ถ• (60057)

๋ฌธ์ œ๋งํฌ

 

์ ‘๊ทผ ๋ฐฉ๋ฒ•

๋ฌธ์ž์—ด์„ 1๊ฐœ๋ถ€ํ„ฐ ๋ฌธ์ž์—ด/2๊ฐœ๊นŒ์ง€ ๋ฐ˜๋ณตํ•˜์—ฌ ์ž˜๋ผ ๋น„๊ตํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•˜์˜€๋‹ค.

"ababcdcdababcdcd"
a b a b c d c d a b a b c d c d
ab ab cd cd ab ab cd cd => 2ab 2cd 2ab 2cd๋ฅผ ์šฐ์„  ์ €์žฅ
aba bcd cda bab cdc d
abab cdcd abab cdcd
ababc dcdab abcdc d
ababcd cdabab cdcd
ababcdc dababcd cd
ababcdcd ababcdcd => s.length / 2 ๊นŒ์ง€๋งŒ ๊ฒ€์‚ฌ, 2ab 2cd 2ab 2cd๋ฅผ 2ababcdcd๋กœ ๋Œ€์ฒด

์ฒซ for๋ฌธ์—์„œ ๋ช‡๊ฐœ์”ฉ ์ž๋ฅผ์ง€ ํŒ๋‹จํ•˜๊ณ 
2๋ฒˆ์งธ for๋ฌธ์—์„œ ๋ฌธ์ž์—ด ์ „์ฒด๋ฅผ ๋น„๊ตํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•˜์˜€๋‹ค.
let answer = s.length;
    
for (let i = 1; i <= s.length / 2; i++){
    let compressedStr = "";
    let count = 1;
    for( let j = i; j <= s.length; j += i){
    	console.log(`i : ${i}, j : ${j}`)
        if(s.slice(j-i,j) === s.slice(j,j+i))
            count += 1; 
        else{
            compressedStr += (count > 1 ? count : "") + s.slice(j-i, j)
            count = 1;
        }
    }
    console.log(compressedStr)
    answer = Math.min(answer, compressedStr.length);
}โ€‹

์ฒ˜์Œ ์ž‘์„ฑํ•œ ์ฝ”๋“œ์ธ๋ฐ console.log(compressedStr)์„ ์ถœ๋ ฅํ•ด๋ณด๋ฉด ์œ„์—์„œ ์—ฐํ•œ ๋ถ‰์€ ๋ฐฐ๊ฒฝ์œผ๋กœ ํ‘œ์‹œํ•œ ๋ฌธ์ž์—ด
(์ฆ‰ ๋”ฑ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€์ง€ ์•Š๋Š” ๋ถ€๋ถ„)์„ ๋ฐ›์•„์˜ค์ง€ ๋ชปํ–ˆ๋‹ค.

์ด๋ฅผ ๋ฐ›์•„์˜ค๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋‘๋ฒˆ์งธ for๋ฌธ์—์„œ s.slice(j+i, s.length)์„ ๋ฌธ์ž์—ด ๋์— ์ถ”๊ฐ€ํ•ด์•ผํ•˜๋Š”๋ฐ 
๋‘๋ฒˆ์งธ for๋ฌธ์—์„œ๋Š” j๊ฐ€ ๋์—†์ด ๋ณ€ํ™”ํ•˜๊ธฐ ๋•Œ๋ฌธ์—
๋‘๋ฒˆ์งธ for๋ฌธ ๋ฐ–์—์„œ ๋ณ€์ˆ˜ prev๋ฅผ ๋งŒ๋“ค์–ด ์ ‘๊ทผํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ํ’€์ด๋ฅผ ์ง„ํ–‰ํ•˜์˜€๋‹ค. 



function solution(s) {
    let answer = s.length;

    for (let i = 1; i <= s.length / 2; i++){
        
        let prev = s.slice(0, i);
        let compressedStr = "";
        let count = 1;
        
        for( let j = i; j <= s.length; j += i){
            
            let next = s.slice(j, j+i);
            
            if (prev === next) 
                count += 1; 
            else{
                compressedStr += (count > 1 ? count : "") + s.slice(j-i, j)
                count = 1;
                prev = next;
            }
        }
        
        compressedStr += (count > 1 ? count : "") + prev
        answer = Math.min(answer, compressedStr.length);
        
    }
    
    return answer;
}