-
[Algo Rhythm๐บ๐] 2020 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ๋ฆฌํฌ๋ฃจํ ๊ดํธ ๋ณํAlgo Rhythm๐บ๐/others 2020. 7. 3. 00:58
๋ฌธ์ ์ค๋ช
์นด์นด์ค์ ์ ์ ๊ฐ๋ฐ์๋ก ์ ์ฌํ ์ฝ์ ์ ๋ฐฐ ๊ฐ๋ฐ์๋ก๋ถํฐ ๊ฐ๋ฐ์ญ๋ ๊ฐํ๋ฅผ ์ํด ๋ค๋ฅธ ๊ฐ๋ฐ์๊ฐ ์์ฑํ ์์ค ์ฝ๋๋ฅผ ๋ถ์ํ์ฌ ๋ฌธ์ ์ ์ ๋ฐ๊ฒฌํ๊ณ ์์ ํ๋ผ๋ ์ ๋ฌด ๊ณผ์ ๋ฅผ ๋ฐ์์ต๋๋ค. ์์ค๋ฅผ ์ปดํ์ผํ์ฌ ๋ก๊ทธ๋ฅผ ๋ณด๋ ๋๋ถ๋ถ ์์ค ์ฝ๋ ๋ด ์์ฑ๋ ๊ดํธ๊ฐ ๊ฐ์๋ ๋ง์ง๋ง ์ง์ด ๋ง์ง ์์ ํํ๋ก ์์ฑ๋์ด ์ค๋ฅ๊ฐ ๋๋ ๊ฒ์ ์๊ฒ ๋์์ต๋๋ค.
์์ ํด์ผ ํ ์์ค ํ์ผ์ด ๋๋ฌด ๋ง์์ ๊ณ ๋ฏผํ๋ ์ฝ์ ์์ค ์ฝ๋์ ์์ฑ๋ ๋ชจ๋ ๊ดํธ๋ฅผ ๋ฝ์์ ์ฌ๋ฐ๋ฅธ ์์๋๋ก ๋ฐฐ์น๋ ๊ดํธ ๋ฌธ์์ด์ ์๋ ค์ฃผ๋ ํ๋ก๊ทธ๋จ์ ๋ค์๊ณผ ๊ฐ์ด ๊ฐ๋ฐํ๋ ค๊ณ ํฉ๋๋ค.
์ฉ์ด์ ์ ์
'(' ์ ')' ๋ก๋ง ์ด๋ฃจ์ด์ง ๋ฌธ์์ด์ด ์์ ๊ฒฝ์ฐ, '(' ์ ๊ฐ์์ ')' ์ ๊ฐ์๊ฐ ๊ฐ๋ค๋ฉด ์ด๋ฅผ ๊ท ํ์กํ ๊ดํธ ๋ฌธ์์ด์ด๋ผ๊ณ ๋ถ๋ฆ ๋๋ค.
๊ทธ๋ฆฌ๊ณ ์ฌ๊ธฐ์ '('์ ')'์ ๊ดํธ์ ์ง๋ ๋ชจ๋ ๋ง์ ๊ฒฝ์ฐ์๋ ์ด๋ฅผ ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด์ด๋ผ๊ณ ๋ถ๋ฆ ๋๋ค.
์๋ฅผ ๋ค์ด, "(()))("์ ๊ฐ์ ๋ฌธ์์ด์ ๊ท ํ์กํ ๊ดํธ ๋ฌธ์์ด ์ด์ง๋ง ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด์ ์๋๋๋ค.
๋ฐ๋ฉด์ "(())()"์ ๊ฐ์ ๋ฌธ์์ด์ ๊ท ํ์กํ ๊ดํธ ๋ฌธ์์ด ์ด๋ฉด์ ๋์์ ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด ์ ๋๋ค.
'(' ์ ')' ๋ก๋ง ์ด๋ฃจ์ด์ง ๋ฌธ์์ด w๊ฐ ๊ท ํ์กํ ๊ดํธ ๋ฌธ์์ด ์ด๋ผ๋ฉด ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ ํตํด ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด๋ก ๋ณํํ ์ ์์ต๋๋ค.
1. ์ ๋ ฅ์ด ๋น ๋ฌธ์์ด์ธ ๊ฒฝ์ฐ, ๋น ๋ฌธ์์ด์ ๋ฐํํฉ๋๋ค.
2. ๋ฌธ์์ด w๋ฅผ ๋ "๊ท ํ์กํ ๊ดํธ ๋ฌธ์์ด" u, v๋ก ๋ถ๋ฆฌํฉ๋๋ค. ๋จ, u๋ "๊ท ํ์กํ ๊ดํธ ๋ฌธ์์ด"๋ก ๋ ์ด์ ๋ถ๋ฆฌํ ์ ์์ด์ผ ํ๋ฉฐ, v๋ ๋น ๋ฌธ์์ด์ด ๋ ์ ์์ต๋๋ค.
3. ๋ฌธ์์ด u๊ฐ "์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด" ์ด๋ผ๋ฉด ๋ฌธ์์ด v์ ๋ํด 1๋จ๊ณ๋ถํฐ ๋ค์ ์ํํฉ๋๋ค.
3-1. ์ํํ ๊ฒฐ๊ณผ ๋ฌธ์์ด์ u์ ์ด์ด ๋ถ์ธ ํ ๋ฐํํฉ๋๋ค.
4. ๋ฌธ์์ด u๊ฐ "์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด"์ด ์๋๋ผ๋ฉด ์๋ ๊ณผ์ ์ ์ํํฉ๋๋ค.
4-1. ๋น ๋ฌธ์์ด์ ์ฒซ ๋ฒ์งธ ๋ฌธ์๋ก '('๋ฅผ ๋ถ์ ๋๋ค.
4-2. ๋ฌธ์์ด v์ ๋ํด 1๋จ๊ณ๋ถํฐ ์ฌ๊ท์ ์ผ๋ก ์ํํ ๊ฒฐ๊ณผ ๋ฌธ์์ด์ ์ด์ด ๋ถ์ ๋๋ค.
4-3. ')'๋ฅผ ๋ค์ ๋ถ์ ๋๋ค.
4-4. u์ ์ฒซ ๋ฒ์งธ์ ๋ง์ง๋ง ๋ฌธ์๋ฅผ ์ ๊ฑฐํ๊ณ , ๋๋จธ์ง ๋ฌธ์์ด์ ๊ดํธ ๋ฐฉํฅ์ ๋ค์ง์ด์ ๋ค์ ๋ถ์ ๋๋ค.
4-5. ์์ฑ๋ ๋ฌธ์์ด์ ๋ฐํํฉ๋๋ค.๊ท ํ์กํ ๊ดํธ ๋ฌธ์์ด p๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ฃผ์ด์ง ์๊ณ ๋ฆฌ์ฆ์ ์ํํด ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด๋ก ๋ณํํ ๊ฒฐ๊ณผ๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์.
๋งค๊ฐ๋ณ์ ์ค๋ช
-
p๋ '(' ์ ')' ๋ก๋ง ์ด๋ฃจ์ด์ง ๋ฌธ์์ด์ด๋ฉฐ ๊ธธ์ด๋ 2 ์ด์ 1,000 ์ดํ์ธ ์ง์์ ๋๋ค.
-
๋ฌธ์์ด p๋ฅผ ์ด๋ฃจ๋ '(' ์ ')' ์ ๊ฐ์๋ ํญ์ ๊ฐ์ต๋๋ค.
-
๋ง์ฝ p๊ฐ ์ด๋ฏธ ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด์ด๋ผ๋ฉด ๊ทธ๋๋ก return ํ๋ฉด ๋ฉ๋๋ค.
๋๋ ์ด๋ป๊ฒ ํ์๋
import java.util.Stack; import java.lang.StringBuilder; class Solution { public String solution(String p) { String answer = p; if(!isCorrectParen(p)) { answer = toCorrectParen(p); } return answer; } public String toCorrectParen(String w) { String u, v = ""; String correctParen = ""; if(w.equals("")) return ""; // split u and v String[] wArr = w.split(""); int mark = 0, balanceIndicator = 0; while(mark < wArr.length) { if(wArr[mark].equals("(")) balanceIndicator++; if(wArr[mark].equals(")")) balanceIndicator--; mark++; if(balanceIndicator == 0) break; } u = w.substring(0, mark); v = w.substring(mark); if(isCorrectParen(u)) { // phase 3 return u + toCorrectParen(v); } else { //phase 4 StringBuilder sbd = new StringBuilder(); sbd.append("("); sbd.append(toCorrectParen(v)); sbd.append(")"); String[] uArr = u.split(""); for(int i = 1; i < uArr.length - 1; i++) { switch(uArr[i]) { case "(": sbd.append(")"); break; case ")": sbd.append("("); break; } } correctParen += sbd.toString(); } return correctParen; } public boolean isCorrectParen(String p) { String[] parenArr = p.split(""); Stack<String> parens = new Stack<>(); for(String paren : parenArr) { if(paren.equals("(")) parens.push(paren); if(paren.equals(")")) { if(parens.isEmpty()) return false; parens.pop(); } } return parens.isEmpty(); } }
๋๋ ์ ์ ๋ ๊ฒ ํ์๋
๋งจ ์ฒ์ '๊ท ํ์กํ ๊ดํธ ๋ฌธ์์ด'์ธ์ง ํ์ ํด์ผ ํ๋๋ฐ DS์๊ฐ์ ๋ฐฐ์ด ์คํ์ ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ์ด ์๊ฐ๋ ๊ทธ ๋ฐฉ๋ฒ์ ๊ทธ๋๋ก ์ฌ์ฉํ๋ค. ๊ทธ ๋ค์๋ถํฐ๋ ๋ฌธ์ ์์ ์๋ ค์ค ์๊ณ ๋ฆฌ์ฆ์ ๋ฐ๋ผ ์ฝ๋๋ฅผ ์์ฑํ๋ค.
๊ทธ ์ค u์ v๋ฅผ ๋๋๋ ๋ถ๋ถ์ด ์ด๋ ค์ ๊ธฐ ๋๋ฌธ์ ์ด ๋ถ๋ถ๋ง ๊ฐ๋จํ ์ค๋ช ํด๋ณด๊ฒ ๋ค.
u๋ ๋ ์ด์ ๋ถ๋ฆฌํ ์ ์๋ '๊ท ํ์กํ ๊ดํธ ๋ฌธ์์ด'์ด๊ธฐ ๋๋ฌธ์ ๊ท ํ์กํ ๊ดํธ ๋ฌธ์์ด์ด ์์ฑ๋๋ฉด ์๋ ค์ค ๋ฌด์ธ๊ฐ๊ฐ ํ์ํ๋ค. ๊ทธ๋์ ๋๋ balanceIndicator๋ผ๋ intํ ๋ณ์๋ฅผ 0์ผ๋ก ์ด๊ธฐํํ๋ค. ๋ฌธ์์ด์ ์ํํ๋ฉด์ (๊ฐ ๋์ค๋ฉด increment๋ฅผ, )๊ฐ ๋์ค๋ฉด decrement๋ฅผ ํ๋ค. ๊ทธ๋ฆฌ๊ณ balanceIndicator๊ฐ 0์ด ๋๋ฉด ๊ทธ๊ฒ์ ๊ท ํ์กํ ๊ดํธ ๋ฌธ์์ด์ด ์์ฑ๋์๋ค๋ ๋ป์ด๊ธฐ ๋๋ฌธ์ ๋ฐ๋ณต๋ฌธ์ ๋๊ฐ ๋ค ๋๊ฐ ๊ทธ index๋ฅผ ๊ธฐ์ค์ผ๋ก u์ v๋ฅผ ๋๋ด๋ค.
์ฒ์์ u์ v๋ฅผ ๋๋๋ ๋ถ๋ถ์ ์๋ชป ์ดํดํด์ ํ์ฐธ ํค๋งธ๋๋ฐ ์ ๋๋ก ๋ฌธ์ ๋ฅผ ์ดํด์์ผ์ค ๊ฐ์ ์ง์๊ฒ ์ ๋ง์ ๋ง ๊ฐ์ฌํ๋ค.๐ญ
๋๋ ๋ฌด์์ ๋ฐฐ์ ๋
๋ฌธ์ ๋ฅผ ๊ผผ๊ผผ์ด ์ฝ์ด๋ณด์ ์ ๋ฐ ใ ใ
๊ทธ๋ฆฌ๊ณ ์ฒ์์ผ๋ก StringBuilder๋ฅผ ์ฌ์ฉํ๋๋ฐ ์ฝ๋๊ฐ ํจ์ฌ ๋ณด๊ธฐ ์ข๋ค. ์์ผ๋ก ์ ์ฉํด์ผ๊ฒ ๋ค.
'Algo Rhythm๐บ๐ > others' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
-