[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค/python] 2020 ์นด์นด์˜ค ์ธํ„ด์‹ญ : ์ˆ˜์‹ ์ตœ๋Œ€ํ™”

2021. 9. 10. 16:06

๋ฌธ์ œ ์„ค๋ช…

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์˜ ์ž์„ธํ•œ ์„ค๋ช…์€ ์•„๋ž˜์˜ ํฌ์ŠคํŒ…์„ ์ฐธ๊ณ ํ•˜๋ฉด ๋œ๋‹ค.

2021.04.01 - [๐Ÿ”์•Œ๊ณ ๋ฆฌ์ฆ˜/๐Ÿ”…๊ฐœ๋…์ •๋ฆฌ] - [ํŒŒ์ด์ฌ/python] ์ˆœ์—ด๊ณผ ์กฐํ•ฉ : itertools ์ด์šฉํ•˜๊ธฐ (permutations, combinations)

 

[ํŒŒ์ด์ฌ/python] ์ˆœ์—ด๊ณผ ์กฐํ•ฉ : itertools ์ด์šฉํ•˜๊ธฐ (permutations, combinations)

itertools๋ฅผ ์ด์šฉํ•˜์—ฌ ์ˆœ์—ด๊ณผ ์กฐํ•ฉ์„ ๊ตฌํ˜„ํ•˜๋ฉด ๋”์šฑ ๋น ๋ฅด๊ฒŒ ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ๋‹ค. 1. ์ˆœ์—ด : permutations(N, r) N์—์„œ ์ค‘๋ณต์„ ํ—ˆ์šฉํ•˜์ง€ ์•Š๊ณ , r๊ฐœ๋ฅผ ๋ฝ‘์•„ ์ˆœ์„œ๋Œ€๋กœ ๋‚˜์—ดํ•œ๋‹ค. ์ค‘๋ณต์„ ํ—ˆ์šฉํ•˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์—, ๋ฝ‘

ye333.tistory.com

 

BELATED ARTICLES

more