당최 어떻게 풀어야 할지 감이 오지 않았던 문제이다.
풀이
나는 위 문제를 풀기 위해 아래와 같은 연산을 생각했다.(문제 속 예제로 가정)
맨 왼쪽 위의 막대기부터 오른쪽으로 몇 개로 분리되는지 세어야 한다고 판단했다.
그래서, 3 + 2 + 5 + 5 + 2라는 연산이 나타나도록 코드를 설계해야 한다고 보았다.
이렇게 계산하는 것 말고는 정확한 계산을 할 수 없을 거라고 생각했기 때문이다.
그러나 이 아이디어를 구현하는 게 쉬운 일이 아니었다.
O($n^2$) 연산, 재귀 함수를 활용해야 하나라는 생각이 많이 들었다.
그래도 어떻게든 아래와 같은 코드를 작성했다.
import sys
input = sys.stdin.readline
system = input().rstrip()
systems = []
left = []
res = 0
for i, s in enumerate(system):
systems.append(s)
# 레이저가 아닌 막대를 가리키는 왼쪽 괄호를 만났을 때
if s == "(" and system[i + 1] == "(":
left.append(len(systems) - 1)
# 레이저가 아닌 막대를 가리키는 오른쪽 괄호를 만났을 때
elif s == ")" and systems[-2] == ")":
idx = len(systems) - 1
res += int((idx - left[-1]) / 2) + 1
systems.pop(left.pop())
systems.pop()
print(res)결과적으로는 3 + 2 + 5 + 5 + 2와 같은 연산을 하도록 작성했다.
연산 과정은 아래와 같다.
* 현재 부호가 왼쪽 막대 부분을 가리키는 왼쪽 괄호일 경우
1. left list에 그 왼쪽 괄호의 index 번호를 삽입한다. (그 index 번호는 현재 들어온 왼쪽 괄호가 연산을 위한 stack인 systems에 몇 번째로 들어온 element인지 가르쳐준다.)
* 현재 부호가 오른쪽 막대 부분을 가리키는 오른쪽 괄호일 경우
1. 현재 systems의 맨 마지막 element에 오른쪽 괄호가 들어와있기 때문에 그 index를 idx 변수에 저장한다.
2. 오른쪽 막대 부분을 가리키는 오른쪽 괄호가 들어왔다는 것은 막대 하나가 현재까지 만났던 레이저들에 의해서 분리가 된다는 의미이므로 현재 막대가 현재까지 만난 레이저들에 의해 몇 개로 분리되는지 res에 저장한다.
(엄밀히 말하자면, 막대 한 개는 왼쪽 막대 부분부터 그에 대응하는 오른쪽 막대 부분이 나올 때까지 그 사이에 존재했던 레이저들에 의해서 분리된다. 레이저는 "()" 2개의 괄호로 이루어져 있으므로 2로 나누면 1개의 레이저라고 표현할 수 있게 된다. 그리고 레이저 한 개에 의해서 막대는 2개로, 레이저 두 개에 의해서 막대는 3개로 즉, 레이저 개수 + 1개의 개수만큼 막대가 분리되기 때문에 1을 더해준다.)
3. 분리된 막대기를 제거한다.
다른 풀이
나의 풀이는 문제 풀이 사이트 상에서 시간이 오래 걸리는 풀이에 속했다.
그래서 뭔가 아쉬워서 다른 사람들의 풀이를 살펴보았다.
나와 같은 아이디어로 풀지 않고 다른 시선으로 이 문제를 바라보고 푼 분들이 존재했고, 그 분들의 풀이가 훨씬 시간복잡도도 낮고 코드도 간결했다.
나의 아이디어는 막대 하나에 집중해서 그 막대가 몇 개로 분리되는지 그리고 그것들의 총합이 어떻게 되는지 계산하는 식이었다.
다른 아이디어는 아래와 같았다.
import sys
input = sys.stdin.readline
system = input().rstrip().replace("()", "*")
systems = []
res = 0
for s in system:
if s == "(":
systems.append(s)
res += 1
elif s == ")":
systems.pop()
else:
res += len(systems)
print(res)레이저를 이루는 괄호를 따로 처리해줄 필요가 없게끔 아예 레이저를 "*"로 변환시켜주었다.
그리고 메인 아이디어는, 레이저를 만나게 될 때마다 그 레이저를 만나는 막대들이 모두 몇 개로 분리가 되는지 바로 연산을 하는 것이다.
결국은 막대 개수 + 막대 개수(레이저를 만났을 때)를 통해서 레이저를 만났을 때 레이저 개수 + 1개로 분리가 되는 것을 나처럼 막대 한 개씩 계산한 게 아니라, 여러 개의 막대를 한 번에 계산해낸 것이다.
굉장히 간결해서 좋았다.
