-
[Algo Rhythm๐บ๐] 2020 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ๋ฆฌํฌ๋ฃจํ ๋ฌธ์์ด ์์ถAlgo Rhythm๐บ๐/others 2020. 7. 3. 01:14
๋ฌธ์ ์ค๋ช
๋ฐ์ดํฐ ์ฒ๋ฆฌ ์ ๋ฌธ๊ฐ๊ฐ ๋๊ณ ์ถ์ ์ดํผ์น๋ ๋ฌธ์์ด์ ์์ถํ๋ ๋ฐฉ๋ฒ์ ๋ํด ๊ณต๋ถ๋ฅผ ํ๊ณ ์์ต๋๋ค. ์ต๊ทผ์ ๋๋์ ๋ฐ์ดํฐ ์ฒ๋ฆฌ๋ฅผ ์ํ ๊ฐ๋จํ ๋น์์ค ์์ถ ๋ฐฉ๋ฒ์ ๋ํด ๊ณต๋ถ๋ฅผ ํ๊ณ ์๋๋ฐ, ๋ฌธ์์ด์์ ๊ฐ์ ๊ฐ์ด ์ฐ์ํด์ ๋ํ๋๋ ๊ฒ์ ๊ทธ ๋ฌธ์์ ๊ฐ์์ ๋ฐ๋ณต๋๋ ๊ฐ์ผ๋ก ํํํ์ฌ ๋ ์งง์ ๋ฌธ์์ด๋ก ์ค์ฌ์ ํํํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๊ณต๋ถํ๊ณ ์์ต๋๋ค.
๊ฐ๋จํ ์๋ก aabbaccc์ ๊ฒฝ์ฐ 2a2ba3c(๋ฌธ์๊ฐ ๋ฐ๋ณต๋์ง ์์ ํ๋ฒ๋ง ๋ํ๋ ๊ฒฝ์ฐ 1์ ์๋ตํจ)์ ๊ฐ์ด ํํํ ์ ์๋๋ฐ, ์ด๋ฌํ ๋ฐฉ์์ ๋ฐ๋ณต๋๋ ๋ฌธ์๊ฐ ์ ์ ๊ฒฝ์ฐ ์์ถ๋ฅ ์ด ๋ฎ๋ค๋ ๋จ์ ์ด ์์ต๋๋ค. ์๋ฅผ ๋ค๋ฉด, abcabcdede์ ๊ฐ์ ๋ฌธ์์ด์ ์ ํ ์์ถ๋์ง ์์ต๋๋ค. ์ดํผ์น๋ ์ด๋ฌํ ๋จ์ ์ ํด๊ฒฐํ๊ธฐ ์ํด ๋ฌธ์์ด์ 1๊ฐ ์ด์์ ๋จ์๋ก ์๋ผ์ ์์ถํ์ฌ ๋ ์งง์ ๋ฌธ์์ด๋ก ํํํ ์ ์๋์ง ๋ฐฉ๋ฒ์ ์ฐพ์๋ณด๋ ค๊ณ ํฉ๋๋ค.
์๋ฅผ ๋ค์ด, ababcdcdababcdcd์ ๊ฒฝ์ฐ ๋ฌธ์๋ฅผ 1๊ฐ ๋จ์๋ก ์๋ฅด๋ฉด ์ ํ ์์ถ๋์ง ์์ง๋ง, 2๊ฐ ๋จ์๋ก ์๋ผ์ ์์ถํ๋ค๋ฉด 2ab2cd2ab2cd๋ก ํํํ ์ ์์ต๋๋ค. ๋ค๋ฅธ ๋ฐฉ๋ฒ์ผ๋ก 8๊ฐ ๋จ์๋ก ์๋ผ์ ์์ถํ๋ค๋ฉด 2ababcdcd๋ก ํํํ ์ ์์ผ๋ฉฐ, ์ด๋๊ฐ ๊ฐ์ฅ ์งง๊ฒ ์์ถํ์ฌ ํํํ ์ ์๋ ๋ฐฉ๋ฒ์ ๋๋ค.
๋ค๋ฅธ ์๋ก, abcabcdede์ ๊ฐ์ ๊ฒฝ์ฐ, ๋ฌธ์๋ฅผ 2๊ฐ ๋จ์๋ก ์๋ผ์ ์์ถํ๋ฉด abcabc2de๊ฐ ๋์ง๋ง, 3๊ฐ ๋จ์๋ก ์๋ฅธ๋ค๋ฉด 2abcdede๊ฐ ๋์ด 3๊ฐ ๋จ์๊ฐ ๊ฐ์ฅ ์งง์ ์์ถ ๋ฐฉ๋ฒ์ด ๋ฉ๋๋ค. ์ด๋ 3๊ฐ ๋จ์๋ก ์๋ฅด๊ณ ๋ง์ง๋ง์ ๋จ๋ ๋ฌธ์์ด์ ๊ทธ๋๋ก ๋ถ์ฌ์ฃผ๋ฉด ๋ฉ๋๋ค.
์์ถํ ๋ฌธ์์ด s๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์์ ์ค๋ช ํ ๋ฐฉ๋ฒ์ผ๋ก 1๊ฐ ์ด์ ๋จ์๋ก ๋ฌธ์์ด์ ์๋ผ ์์ถํ์ฌ ํํํ ๋ฌธ์์ด ์ค ๊ฐ์ฅ ์งง์ ๊ฒ์ ๊ธธ์ด๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
-
s์ ๊ธธ์ด๋ 1 ์ด์ 1,000 ์ดํ์ ๋๋ค.
-
s๋ ์ํ๋ฒณ ์๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
๋๋ ์ด๋ป๊ฒ ํ์๋
public class Solution { public int solution(String s) { int len = s.length(); int minLen = (len == 1) ? len : Integer.MAX_VALUE; for(int unit = 1; unit <= len / 2; unit++) { String compStr = ""; String targetStr = s.substring(0, unit); int numContinuous = 1; int remainMark = 0; boolean isLeftToComp = false; for(int i = unit; i <= len; i+= unit) { if(i + unit > len) break; String otherStr = s.substring(i, i + unit); if(targetStr.equals(otherStr)) { numContinuous++; isLeftToComp = true; } else { compStr += (numContinuous > 1) ? numContinuous + targetStr : targetStr; if((i + unit) + unit > len) compStr += otherStr; // ๋ง์ง๋ง์ ๋ถ์ฌ์ผ ํ ๊ฒ ์ฒ๋ฆฌ isLeftToComp = false; targetStr = otherStr; numContinuous = 1; } remainMark = i + unit; } // ์์ถํด์ผ ํ ๋๋จธ์ง ์ฒ๋ฆฌ if(isLeftToComp) { compStr += (numContinuous > 1) ? numContinuous + targetStr : targetStr; } // ๋๋จธ์ง ์ฒ๋ฆฌ if(remainMark < len) { compStr += s.substring(remainMark); } minLen = (compStr.length() > minLen) ? minLen : compStr.length(); } return minLen; } }
๋๋ ์ ์ ๋ ๊ฒ ํ์๋
์ฌ์ค ์ด ๋ฌธ์ ๋ ์ฝ๋๊ฐ ์ข ๋๋ฝ๋ค. ๊ทธ๋์ ํต์ฌ๋ง ์ค๋ช ํ๋ ค๊ณ ํ๋ค! ํน์ ๋๊ตฐ๊ฐ ์ด ๊ธ์ ์ฝ๊ณ ๊ณ์๋ค๋ฉด ์ค์ค๋ก ์์ฉํด๋ณด์๊ธธ!
๋ ๊ฐ์ธ์ ์ผ๋ก ์ด ๋ฌธ์ ์ ํต์ฌ์ด ๊ฐ๋ฅํ ๋จ์์ ๋ฒ์๋ฅผ ์๊ณ ์๋๊ฐ ๋ผ๊ณ ์๊ฐํ๋ค. ์ฒ์์๋ ๊ฐ๋ฅํ ๋จ์์ ๋ฒ์๊ฐ 1์ด์ ๋ฌธ์์ด์ ๊ธธ์ด ์ดํ์ธ ์ค ์์๋ค. ํ์ง๋ง ๊ทธ๋ ๊ฒ ์ฝ๋๋ฅผ ์์ฑํ๋ฉด ๋ฐฐ์ด์ ๋ฒ์๋ฅผ ๋์ด๊ฐ๋ ๊ฒฝ์ฐ๊ฐ ์๊ฒจ์ ์ฝ๋๋ฅผ ์์ฑํ๊ธฐ ๊ณค๋ํ๋ค.
๋์ค์ ์ ์ง์ด๊ฐ ์๋ ค์คฌ๋๋ฐ ๋จ์๊ฐ ๋ฌธ์์ด ๊ธธ์ด์ ์ ๋ฐ ์ด์์ผ ๊ฒฝ์ฐ๋ ์์ถ๋ ๊ฒ๋ค์ด ๋๊ฐ๊ธฐ ๋๋ฌธ์ ๋ณผ ํ์์๋ค๋ ๊ฒ์ ์๋ ค์คฌ๋ค! ๋-๋ฐ ๐คฉ ์ญ์ ๊ฐ์ ์ง์ด๋ค… ์ด์จ๋ ๊ทธ ์ฌ์ค์ ๊ธฐ์ตํ ๋ค ์ฝ๋๋ฅผ ๊ตฌํํ๋ ์ ๋ ๊ฒ ๋์๋ค.
๋๋ ๋ฌด์์ ๋ฐฐ์ ๋
์์ ํ์ ๋ฌธ์ ๊ฐ ์ด๋ ๊ฒ ์ด๋ ค์ธ์๋ ์๊ตฌ๋๋ผ๋ ๊ฒ์ ๋ฐฐ์ ๋ค.
๋ถ๋ช ํ ์ด ์ฝ๋๋ฅผ ํด๋ฆญํ๊ฒ ์ง ์ฌ๋์ด ์์ํ ๋ฐ ์์ง๊น์ง๋ ํ์ธํ์ง ๋ชป ํ๋ค. ํด๋ฆฐ ์ฝ๋๋ฅผ ๋ณด๊ณ ๋ฐฐ์ฐ๊ณ ์ถ๋ค.
'Algo Rhythm๐บ๐ > others' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
-