[ํ๋ก๊ทธ๋๋จธ์ค/python] 2020 ์นด์นด์ค ์ธํด์ญ : ์์ ์ต๋ํ
๋ฌธ์ ์ค๋ช
IT ๋ฒค์ฒ ํ์ฌ๋ฅผ ์ด์ํ๊ณ ์๋ ๋ผ์ด์ธ์ ๋งค๋
์ฌ๋ด ํด์ปคํค ๋ํ๋ฅผ ๊ฐ์ตํ์ฌ ์ฐ์น์์๊ฒ ์๊ธ์ ์ง๊ธํ๊ณ ์์ต๋๋ค.
์ด๋ฒ ๋ํ์์๋ ์ฐ์น์์๊ฒ ์ง๊ธ๋๋ ์๊ธ์ ์ด์ ๋ํ์๋ ๋ค๋ฅด๊ฒ ๋ค์๊ณผ ๊ฐ์ ๋ฐฉ์์ผ๋ก ๊ฒฐ์ ํ๋ ค๊ณ ํฉ๋๋ค.
ํด์ปคํค ๋ํ์ ์ฐธ๊ฐํ๋ ๋ชจ๋ ์ฐธ๊ฐ์๋ค์๊ฒ๋ ์ซ์๋ค๊ณผ 3๊ฐ์ง์ ์ฐ์ฐ๋ฌธ์(+, -, *) ๋ง์ผ๋ก ์ด๋ฃจ์ด์ง ์ฐ์ฐ ์์์ด ์ ๋ฌ๋๋ฉฐ, ์ฐธ๊ฐ์์ ๋ฏธ์
์ ์ ๋ฌ๋ฐ์ ์์์ ํฌํจ๋ ์ฐ์ฐ์์ ์ฐ์ ์์๋ฅผ ์์ ๋กญ๊ฒ ์ฌ์ ์ํ์ฌ ๋ง๋ค ์ ์๋ ๊ฐ์ฅ ํฐ ์ซ์๋ฅผ ์ ์ถํ๋ ๊ฒ์
๋๋ค.
๋จ, ์ฐ์ฐ์์ ์ฐ์ ์์๋ฅผ ์๋ก ์ ์ํ ๋, ๊ฐ์ ์์์ ์ฐ์ฐ์๋ ์์ด์ผ ํฉ๋๋ค. ์ฆ, + > - > * ๋๋ - > * > + ๋ฑ๊ณผ ๊ฐ์ด ์ฐ์ฐ์ ์ฐ์ ์์๋ฅผ ์ ์ํ ์ ์์ผ๋ +,* > - ๋๋ * > +,-์ฒ๋ผ 2๊ฐ ์ด์์ ์ฐ์ฐ์๊ฐ ๋์ผํ ์์๋ฅผ ๊ฐ์ง๋๋ก ์ฐ์ฐ์ ์ฐ์ ์์๋ฅผ ์ ์ํ ์๋ ์์ต๋๋ค. ์์์ ํฌํจ๋ ์ฐ์ฐ์๊ฐ 2๊ฐ๋ผ๋ฉด ์ ์ํ ์ ์๋ ์ฐ์ฐ์ ์ฐ์ ์์ ์กฐํฉ์ 2! = 2๊ฐ์ง์ด๋ฉฐ, ์ฐ์ฐ์๊ฐ 3๊ฐ๋ผ๋ฉด 3! = 6๊ฐ์ง ์กฐํฉ์ด ๊ฐ๋ฅํฉ๋๋ค.
๋ง์ฝ ๊ณ์ฐ๋ ๊ฒฐ๊ณผ๊ฐ ์์๋ผ๋ฉด ํด๋น ์ซ์์ ์ ๋๊ฐ์ผ๋ก ๋ณํํ์ฌ ์ ์ถํ๋ฉฐ ์ ์ถํ ์ซ์๊ฐ ๊ฐ์ฅ ํฐ ์ฐธ๊ฐ์๋ฅผ ์ฐ์น์๋ก ์ ์ ํ๋ฉฐ, ์ฐ์น์๊ฐ ์ ์ถํ ์ซ์๋ฅผ ์ฐ์น์๊ธ์ผ๋ก ์ง๊ธํ๊ฒ ๋ฉ๋๋ค.
์๋ฅผ ๋ค์ด, ์ฐธ๊ฐ์ ์ค ๋ค์ค๊ฐ ์๋์ ๊ฐ์ ์์์ ์ ๋ฌ๋ฐ์๋ค๊ณ ๊ฐ์ ํฉ๋๋ค.
"100-200*300-500+20"
์ผ๋ฐ์ ์ผ๋ก ์ํ ๋ฐ ์ ์ฐํ์์ ์ฝ์๋ ์ฐ์ฐ์ ์ฐ์ ์์์ ๋ฐ๋ฅด๋ฉด ๋ํ๊ธฐ์ ๋นผ๊ธฐ๋ ์๋ก ๋๋ฑํ๋ฉฐ ๊ณฑํ๊ธฐ๋ ๋ํ๊ธฐ, ๋นผ๊ธฐ์ ๋นํด ์ฐ์ ์์๊ฐ ๋์ * > +,- ๋ก ์ฐ์ ์์๊ฐ ์ ์๋์ด ์์ต๋๋ค.
๋ํ ๊ท์น์ ๋ฐ๋ผ + > - > * ๋๋ - > * > + ๋ฑ๊ณผ ๊ฐ์ด ์ฐ์ฐ์ ์ฐ์ ์์๋ฅผ ์ ์ํ ์ ์์ผ๋ +,* > - ๋๋ * > +,- ์ฒ๋ผ 2๊ฐ ์ด์์ ์ฐ์ฐ์๊ฐ ๋์ผํ ์์๋ฅผ ๊ฐ์ง๋๋ก ์ฐ์ฐ์ ์ฐ์ ์์๋ฅผ ์ ์ํ ์๋ ์์ต๋๋ค.
์์์ ์ฐ์ฐ์๊ฐ 3๊ฐ ์ฃผ์ด์ก์ผ๋ฏ๋ก ๊ฐ๋ฅํ ์ฐ์ฐ์ ์ฐ์ ์์ ์กฐํฉ์ 3! = 6๊ฐ์ง์ด๋ฉฐ, ๊ทธ ์ค + > - > * ๋ก ์ฐ์ฐ์ ์ฐ์ ์์๋ฅผ ์ ํ๋ค๋ฉด ๊ฒฐ๊ด๊ฐ์ 22,000์์ด ๋ฉ๋๋ค.
๋ฐ๋ฉด์ * > + > - ๋ก ์ฐ์ฐ์ ์ฐ์ ์์๋ฅผ ์ ํ๋ค๋ฉด ์์์ ๊ฒฐ๊ด๊ฐ์ -60,420 ์ด์ง๋ง, ๊ท์น์ ๋ฐ๋ผ ์ฐ์น ์ ์๊ธ์ ์ ๋๊ฐ์ธ 60,420์์ด ๋ฉ๋๋ค.
์ฐธ๊ฐ์์๊ฒ ์ฃผ์ด์ง ์ฐ์ฐ ์์์ด ๋ด๊ธด ๋ฌธ์์ด expression์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ฐ์น ์ ๋ฐ์ ์ ์๋ ๊ฐ์ฅ ํฐ ์๊ธ ๊ธ์ก์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ ์ฌํญ
- expression์ ๊ธธ์ด๊ฐ 3 ์ด์ 100 ์ดํ์ธ ๋ฌธ์์ด์ ๋๋ค.
- expression์ ๊ณต๋ฐฑ๋ฌธ์, ๊ดํธ๋ฌธ์ ์์ด ์ค๋ก์ง ์ซ์์ 3๊ฐ์ง์ ์ฐ์ฐ์(+, -, *) ๋ง์ผ๋ก ์ด๋ฃจ์ด์ง ์ฌ๋ฐ๋ฅธ ์ค์ํ๊ธฐ๋ฒ(์ฐ์ฐ์ ๋ ๋์ ์ฌ์ด์ ์ฐ์ฐ๊ธฐํธ๋ฅผ ์ฌ์ฉํ๋ ๋ฐฉ์)์ผ๋ก ํํ๋ ์ฐ์ฐ์์
๋๋ค. ์๋ชป๋ ์ฐ์ฐ์์ ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง์ง ์์ต๋๋ค.
- ์ฆ, "402+-561*"์ฒ๋ผ ์๋ชป๋ ์์์ ์ฌ๋ฐ๋ฅธ ์ค์ํ๊ธฐ๋ฒ์ด ์๋๋ฏ๋ก ์ฃผ์ด์ง์ง ์์ต๋๋ค.
- expression์ ํผ์ฐ์ฐ์(operand)๋ 0 ์ด์ 999 ์ดํ์ ์ซ์์
๋๋ค.
- ์ฆ, "100-2145*458+12"์ฒ๋ผ 999๋ฅผ ์ด๊ณผํ๋ ํผ์ฐ์ฐ์๊ฐ ํฌํจ๋ ์์์ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง์ง ์์ต๋๋ค.
- "-56+100"์ฒ๋ผ ํผ์ฐ์ฐ์๊ฐ ์์์ธ ์์๋ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง์ง ์์ต๋๋ค.
- expression์ ์ ์ด๋ 1๊ฐ ์ด์์ ์ฐ์ฐ์๋ฅผ ํฌํจํ๊ณ ์์ต๋๋ค.
- ์ฐ์ฐ์ ์ฐ์ ์์๋ฅผ ์ด๋ป๊ฒ ์ ์ฉํ๋๋ผ๋, expression์ ์ค๊ฐ ๊ณ์ฐ๊ฐ๊ณผ ์ต์ข ๊ฒฐ๊ด๊ฐ์ ์ ๋๊ฐ์ด 263 - 1 ์ดํ๊ฐ ๋๋๋ก ์ ๋ ฅ์ด ์ฃผ์ด์ง๋๋ค.
- ๊ฐ์ ์ฐ์ฐ์๋ผ๋ฆฌ๋ ์์ ์๋ ๊ฒ์ ์ฐ์ ์์๊ฐ ๋ ๋์ต๋๋ค.
์ ๋ต
from itertools import permutations
def solution(expression):
answer = 0
expression = expression.replace("-", " - ").replace("+", " + ").replace("*", " * ").split()
operator = [i for i in ['*', '+', '-'] if i in expression]
for op in permutations(operator, len(operator)):
calcul = expression.copy()
for o in op:
while o in calcul:
i = calcul.index(o)
calcul = calcul[:i-1] + [str(eval(''.join(calcul[i-1:i+2])))] + calcul[i+2:]
answer = max(answer, (abs(int(calcul[0]))))
return answer
expression์ ๊ฐ์ " "๋ฅผ ๊ธฐ์ค์ผ๋ก split ํ๊ธฐ ์ํด expression์ ์ฐ์ฐ์๋ฅผ ์๋ค ๋์ด์ฐ๊ธฐ๋ฅผ ๋ฃ์ด replaceํ๋ค.
operator์๋ expression์ ์ฌ์ฉ๋ ์ฐ์ฐ์๋ฅผ ๋ฃ์ด์ค๋ค.
permutations๋ฅผ ์ด์ฉํ์ฌ ์ฐ์ฐ์์ ์์ด์ ๊ตฌํ๊ณ
expression์ copyํ calcul์ ์์ ํ๋ฉด์ ๊ณ์ฐํ๋ค.
์ฐ์ ์์ ์ฒซ ๋ฒ์งธ๊ฐ *์ผ ๊ฒฝ์ฐ๋ฅผ ์๋ฅผ ๋ค๋ฉด,
calcul์์ *์ ์์น๋ฅผ ์ฐพ์ i์ ์ ์ฅํ๋ฉด i-1์ ์ ์ซ์, i+1์ ๋ท ์ซ์๊ฐ ๋ ๊ฒ์ด๋ค.
calcul์ ์ธ๋ฑ์ค i-1๋ถํฐ i+1๊น์ง์ ๊ฐ์ joinํ์ฌ eval ํจ์๋ฅผ ํตํด ๊ณ์ฐ ํ
๊ณ์ฐ์ ์ฐ์ธ 3๊ฐ์ ๊ฐ ์๋ฆฌ์ ๋ฃ์ด ์ด์ด๋ถ์ธ๋ค.
๐ฅ calcul = expression์ ํํ๋ก ๋ณต์ฌํ๋ฉด calcul์ ์์ ํ ๋ expression๋ ํจ๊ป ๋ฐ๋๋ฏ๋ก copyํด์ผํ๋ค.
๐ฅ eval์ ๋ฌธ์์ด ํํ์ ์์์ ๊ณ์ฐํด์ฃผ๋ ํจ์์ด๋ค.
์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ฉด์ ๋ชจ๋ ์ฐ์ฐ์๋ฅผ ๊ณ์ฐํ์ ๋ calcul์๋ ์ซ์ ํ๋๋ง ๋จ์์์ผ๋ฏ๋ก calcul[0]๊ณผ answer์ ๋น๊ตํ์ฌ ์ต๋๊ฐ์ answer์ ๊ฐฑ์ ํ๋ค.
permutations์ ์์ธํ ์ค๋ช ์ ์๋์ ํฌ์คํ ์ ์ฐธ๊ณ ํ๋ฉด ๋๋ค.
[ํ์ด์ฌ/python] ์์ด๊ณผ ์กฐํฉ : itertools ์ด์ฉํ๊ธฐ (permutations, combinations)
itertools๋ฅผ ์ด์ฉํ์ฌ ์์ด๊ณผ ์กฐํฉ์ ๊ตฌํํ๋ฉด ๋์ฑ ๋น ๋ฅด๊ฒ ์ฒ๋ฆฌํ ์ ์๋ค. 1. ์์ด : permutations(N, r) N์์ ์ค๋ณต์ ํ์ฉํ์ง ์๊ณ , r๊ฐ๋ฅผ ๋ฝ์ ์์๋๋ก ๋์ดํ๋ค. ์ค๋ณต์ ํ์ฉํ์ง ์๊ธฐ ๋๋ฌธ์, ๋ฝ
ye333.tistory.com