[๋ฐฑ์ค€] 2800. ๊ด„ํ˜ธ ์ œ๊ฑฐ/Python - Gold4

2025. 3. 18. 16:32ยทCoding Test/Algorithms

โ“๋ฌธ์ œ

https://www.acmicpc.net/problem/2800

์„ฑ๋Šฅ ์š”์•ฝ

 

๋ฉ”๋ชจ๋ฆฌ: 32412 KB, ์‹œ๊ฐ„: 36 ms

๋ถ„๋ฅ˜

๋น„ํŠธ๋งˆ์Šคํ‚น, ๋ธŒ๋ฃจํŠธํฌ์Šค ์•Œ๊ณ ๋ฆฌ์ฆ˜, ์ž๋ฃŒ ๊ตฌ์กฐ, ์Šคํƒ, ๋ฌธ์ž์—ด

 

๋ฌธ์ œ ์„ค๋ช…

์–ด๋–ค ์ˆ˜์‹์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ด„ํ˜ธ๋ฅผ ์ œ๊ฑฐํ•ด์„œ ๋‚˜์˜ฌ ์ˆ˜ ์žˆ๋Š” ์„œ๋กœ ๋‹ค๋ฅธ ์‹์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ด ์ˆ˜์‹์€ ๊ด„ํ˜ธ๊ฐ€ ์˜ฌ๋ฐ”๋ฅด๊ฒŒ ์ณ์ ธ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค๋ฉด, 1+2, (3+4), (3+4*(5+6))์™€ ๊ฐ™์€ ์‹์€ ๊ด„ํ˜ธ๊ฐ€ ์„œ๋กœ ์Œ์ด ๋งž์œผ๋ฏ€๋กœ ์˜ฌ๋ฐ”๋ฅธ ์‹์ด๋‹ค.

ํ•˜์ง€๋งŒ, 1+(2*3, ((2+3)*4 ์™€ ๊ฐ™์€ ์‹์€ ์Œ์ด ๋งž์ง€ ์•Š๋Š” ๊ด„ํ˜ธ๊ฐ€ ์žˆ์œผ๋ฏ€๋กœ ์˜ฌ๋ฐ”๋ฅธ ์‹์ด ์•„๋‹ˆ๋‹ค.

๊ด„ํ˜ธ๋ฅผ ์ œ๊ฑฐํ•  ๋•Œ๋Š”, ํ•ญ์ƒ ์Œ์ด ๋˜๋Š” ๊ด„ํ˜ธ๋ผ๋ฆฌ ์ œ๊ฑฐํ•ด์•ผ ํ•œ๋‹ค.

์˜ˆ๋ฅผ๋“ค์–ด (2+(2*2)+2)์—์„œ ๊ด„ํ˜ธ๋ฅผ ์ œ๊ฑฐํ•˜๋ฉด, (2+2*2+2), 2+(2*2)+2, 2+2*2+2๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ, (2+2*2)+2์™€ 2+(2*2+2)๋Š” ๋งŒ๋“ค ์ˆ˜ ์—†๋‹ค. ๊ทธ ์ด์œ ๋Š” ์Œ์ด ๋˜์ง€ ์•Š๋Š” ๊ด„ํ˜ธ๋ฅผ ์ œ๊ฑฐํ–ˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

์–ด๋–ค ์‹์„ ์—ฌ๋Ÿฌ ์Œ์˜ ๊ด„ํ˜ธ๊ฐ€ ๊ฐ์Œ€ ์ˆ˜ ์žˆ๋‹ค.

โœ๐Ÿปํ’€์ด

์šฐ๋ฆฌ๋Š” ํ•ญ์ƒ ์Œ์ด ๋˜๋Š” ๊ด„ํ˜ธ๋ผ๋ฆฌ ์ œ๊ฑฐํ•ด์•ผ ํ•œ๋‹ค. ๊ทธ๋Ÿฌ๋ฏ€๋กœ ๋จผ์ € ๊ด„ํ˜ธ์˜ ์Œ์„ ์ฐพ์•„์•ผ ํ•œ๋‹ค. '('์ด ๋‚˜์˜ค๋ฉด ์Šคํƒ์— '('์˜ ์œ„์น˜๋ฅผ ๋„ฃ๋Š”๋‹ค. ๊ทธ๋ฆฌ๊ณ  ')'์ด ๋‚˜์˜ค๋ฉด ์Œ์„ ์ฐพ์•˜์œผ๋ฏ€๋กœ ์Šคํƒ ๊ฐ€์žฅ ์œ„์˜ '('์˜ ์œ„์น˜์™€ ')'์˜ ์œ„์น˜๋ฅผ ๋‹ค๋ฅธ ๋ฆฌ์ŠคํŠธ์— ๋„ฃ๋Š”๋‹ค. ์ด๋Ÿฌํ•œ ๋ฐฉ์‹์œผ๋กœ ์Œ์„ ์ฐพ์œผ๋ฉด ๋œ๋‹ค.

์Œ์„ ์ฐพ์•˜์œผ๋ฉด ๊ด„ํ˜ธ๋ฅผ ์ œ๊ฑฐํ•˜์—ฌ ๋‚˜์˜ฌ ์ˆ˜ ์žˆ๋Š” ์‹์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•ด์•ผ ํ•œ๋‹ค. ๋งŒ์•ฝ ๊ด„ํ˜ธ์˜ ์œ„์น˜๊ฐ€ (0, 10), (3, 7)์ด ์žˆ๋‹ค๊ณ  ํ•ด๋ณด์ž. ๊ทธ๋Ÿผ ์šฐ๋ฆฌ๋Š” (0, 10)๋งŒ ์ œ๊ฑฐํ•ด๋„ ๋˜๊ณ , (3, 7)์— ์žˆ๋Š” ๊ด„ํ˜ธ๋งŒ ์ œ๊ฑฐํ•ด๋„ ๋œ๋‹ค. ํ˜น์€ ๋‘˜ ๋‹ค ์ง€์šธ ์ˆ˜๋„ ์žˆ๋‹ค. ์ด๋Š” ์กฐํ•ฉ์œผ๋กœ combinations ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•ด์„œ ๊ตฌํ•˜๋ฉด ๋œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ด๋ ‡๊ฒŒ ๋‚˜์˜จ ์กฐํ•ฉ์„ ์ด์šฉํ•˜์—ฌ ์ง€์šฐ๊ณ ์ž ํ•˜๋Š” ์œ„์น˜๋ฅผ ๋นˆ์นธ์œผ๋กœ ๋ฐ”๊พธ๋ฉด ๊ด„ํ˜ธ๊ฐ€ ์ œ๊ฑฐ๋œ ์‹์ด ๋‚˜์˜จ๋‹ค. ๋งˆ์ง€๋ง‰์œผ๋กœ ๋‚˜์˜จ ์‹๋“ค์„ ์ •๋ ฌํ•ด์„œ ์ถœ๋ ฅํ•˜๋ฉด ๋œ๋‹ค.

๐Ÿ’ป์ฝ”๋“œ

import sys
from itertools import combinations

input = sys.stdin.readline

S = list(input().strip())
st = []
indices = []

res = set()
for i in range(len(S)):
    if S[i] == '(':
        st.append(i)
    elif S[i] == ')':
        indices.append((st.pop(), i))

for i in range(len(indices)):
    for comb in combinations(indices, i+1):
        temp = S[:]
        for c in comb:
            temp[c[0]] = temp[c[1]] = ""
        res.add("".join(temp))

for s in sorted(list(res)):
    print(s)

๐Ÿ“ํ›„๊ธฐ

๋จธ๋ฆฌ๋กœ ์ดํ•ดํ•ด๋„ ์ฝ”๋“œ๋กœ ๋งŒ๋“œ๋Š” ๊ฒƒ์€ ์–ด๋ ต๋‹ค...

์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'Coding Test > Algorithms' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[๋ฐฑ์ค€] 1068. ํŠธ๋ฆฌ/Python - Gold5  (0) 2025.03.19
[๋ฐฑ์ค€] 1966. ํ”„๋ฆฐํ„ฐ ํ/Python - Silver3  (0) 2025.03.18
[๋ฐฑ์ค€]14940. ์‰ฌ์šด ์ตœ๋‹จ๊ฑฐ๋ฆฌ/Python - Silver1  (0) 2025.03.10
[๋ฐฑ์ค€] 17298.์˜คํฐ์ˆ˜/Python - Gold4  (0) 2025.03.07
[๋ฐฑ์ค€] 2493. ํƒ‘/Python - Gold5  (0) 2025.03.01
'Coding Test/Algorithms' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [๋ฐฑ์ค€] 1068. ํŠธ๋ฆฌ/Python - Gold5
  • [๋ฐฑ์ค€] 1966. ํ”„๋ฆฐํ„ฐ ํ/Python - Silver3
  • [๋ฐฑ์ค€]14940. ์‰ฌ์šด ์ตœ๋‹จ๊ฑฐ๋ฆฌ/Python - Silver1
  • [๋ฐฑ์ค€] 17298.์˜คํฐ์ˆ˜/Python - Gold4
The Engineer, Lucy
The Engineer, Lucy
  • The Engineer, Lucy
    Growing up for My Future๐Ÿ’•
    The Engineer, Lucy
    • Instagram
    • GitHub
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (148) N
      • Computer Science (17)
        • Data Structure (0)
        • Algorithms (1)
        • Operating System (3)
        • Network (11)
        • Database System (2)
      • Coding Test (69) N
        • Algorithms (61) N
        • SQL (7)
      • Infra (6)
      • Cloud (20)
        • AWS (2)
        • GCP (3)
        • Docker (4)
        • Kubernetes (11)
      • Linux (26)
      • NGINX (1)
      • CICD (3)
      • IaC (1)
      • ETC (5)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ํ™ˆ
    • ํƒœ๊ทธ
    • ๋ฐฉ๋ช…๋ก
  • ๊ณต์ง€์‚ฌํ•ญ

  • ๋งํฌ

    • Lucy's Instagram
    • Lucy's GitHub
  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

    ๋„คํŠธ์›Œํฌ
    ๋„คํŠธ์›Œํฌ ๊ธฐ์ดˆ ์ง€์‹
    ๋„์ปค
    ๋ฆฌ๋ˆ…์Šค๋งˆ์Šคํ„ฐ
    ๋ฆฌ๋ˆ…์Šค๋งˆ์Šคํ„ฐ 2๊ธ‰
    cs ๊ธฐ์ดˆ ์ง€์‹ ์ •๋ฆฌ
    ์ž๋ฐ”
    Shell Script
    ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๊ณต๋ถ€
    ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค
    Linux
    Baekjoon
    ์˜ค๋ธ”์™„
    ์‰˜ ์Šคํฌ๋ฆฝํŠธ
    ํ‹ฐ์Šคํ† ๋ฆฌ์ฑŒ๋ฆฐ์ง€
    Java
    ์ฟ ๋ฒ„๋„คํ‹ฐ์Šค
    dfs
    programmers
    docker
    network
    K8s
    ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰
    ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ
    ๋ฐฑ์ค€
    ๋ฆฌ๋ˆ…์Šค
    ์…ธ ์Šคํฌ๋ฆฝํŠธ
    Shell
    bfs
    Kubernetes
  • ์ตœ๊ทผ ๋Œ“๊ธ€

  • ์ตœ๊ทผ ๊ธ€

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
The Engineer, Lucy
[๋ฐฑ์ค€] 2800. ๊ด„ํ˜ธ ์ œ๊ฑฐ/Python - Gold4
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”