[boj10799] Stack을 활용한 괄호 문제 (시간 복잡도에 대한 고민)

Jonas M·2021년 8월 7일

Coding Test

목록 보기

21/33

Time Complexity

어떤 코드가 실행될 때 걸리는 시간을 표기하는 방법이다. Big O notation이라는 표기 방식을 사용하는데, 이는 최고차항을 따온다고 생각하면 편하다. 최고차항에 의해 연산의 총 시간이 결졍된다고 보기 때문이다.

이때의 n은 프로그램이 돌아가는 1회 연산의 횟수로 생각할 수 있다. 아래와 같은 코드가 있다고 하자. 첫줄의 for loop은 n 만큼 돌아간다. 즉, 연산이 n회 일어난다. 보통 while이나 for loop이 어떤 데이터 길이(n) 만큼 돈다면 O(n)이라 할 수 있다. for loop 아래에 또 다른 비슷한 길이의 for loop이 들어간다면 (이중 loop) O(n^2)이 되는 것이다.

다만, 아래 코드에서 주의해야할 점이 하나 더 있다. data가 set이나 dict라면? 이 코드는 O(n)이 된다. list라면? O(n^2)에 가까워진다. 특정 인자가 원소로 있는지 확인하는 'in' function은 list에 적용될 때는 O(n)의 시간복잡도를, dict나 set에 적용될 때는 O(1)의 시간복잡도를 갖는다. 이건 자료구조의 특성에서 기인한 차이이다. 다른 문제에서 설명한 적이 있어서 참고하면 좋겠다. link

for i in range(n):
	if i in data:
    		ans += 1

또 다른 특성은 worst case가 전체 알고리즘의 시간복잡도를 결정한다는 점이다. 아래 코드가 돌아갈 때, 어떤 케이스에서는 두세번만에 loop이 break되어 O(n)이 아닌 O(c:상수)에 가까운 시간만 소요될 것이다. 하지만 알고리즘의 복잡도를 테스트할 때는 최악의 케이스(10 초과가 하나도 없을 때)를 기준으로 계산한다.

for i in range(n):
	if i > 10: break
    	else: ans += 1

마지막으로 시간복잡도는 알고리즘 내의 최장 시간 loop를 기준으로 한다. 아래처럼 O(n)의 loop과 O(n^2)의 loop이 함께 있다면 이 알고리즘의 복잡도는 O(n^2 + n)이 아니라 O(n^2)이 된다. 낮은 차항의 수는 전체적인 크기를 결정하는 데 큰 영향을 주지 않는다고 보기 때문이다.

for loop ...

for loop ...
	for loop ...

https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis

Question

괄호 str이 주어졌을 때 laser와 bar의 위치를 찾아서 몇 개의 bar로 쪼개지는지 파악하는 문제이다. 해결은 어렵지 않은데, time complexity 문제로 고민이 필요했다.

Solution

괄호 문제는 stack을 활용해서 접근하는 경우가 많다. 닫힘이 나오면 최근에 열린 괄호를 닫아야 하기 때문이다.

Solution 1

laser의 위치와 bar의 위치([3, 5])를 각각 list에 담은 후, 각 bar에 대해 담고 있는 laser의 개수를 세서 답을 구한다. 전체 input 길이에 대한 이중 loop이 돌진 않지만, 결국 마지막에 bar와 laser에 대한 이중 loop이 포함되어있긴 하다. 최악의 경우(bar와 laser가 n 수준으로 등장한다면) O(n^2)에서 크게 다르지 않은 시간이 소요될 수 있다.

ans = 0
for b in bar:
	temp = 1
        for l in laser:
            if l in range(b[0], b[1]):
                temp += 1
        ans += temp

Solution 2

시간 초과 문제로 이중 loop을 줄여보았다. laser의 위치를 나타내는 list를 하나 만들어놓고 laser의 위치에 1을 할당하였다. 그리고 bar에만 loop을 돌면서 laser list를 bar idx로 잘라서, 그 안의 1의 개수를 세어주었다. 위에서 괄호 길이만큼 loop을 돌면서 laser list를 완성해주고, 아래에서는 이와 같이 bar에 대해서만 loop을 돌게 된다.

ans = 0
for b in bar:
	ans += (sum(laser[b[0]:b[1]]) + 1)

Solution 3

한번 loop을 돌면서 답까지 계산하는 방법이다. 괄호가 닫힐 때 '()'이라면 레이져이기 때문에 그 이전에 열린 괄호들(막대)은 모두 잘리게 된다. '()'이 아니라면 막대이기 때문에 답을 1씩 더해주면 된다. (막대가 2개의 레이져로 잘린다면 3개로 잘리는 걸 생각해보자)

def sol_3(s:str) -> int:
    stack = list()
    ans = 0
    for idx in range(len(s)):
        if s[idx] == '(': stack.append(idx)
        else:
            stack.pop()
            if s[idx-1] == '(': ans += len(stack)
            else: ans += 1
    return ans