uncategorized

Data Structure(Stack)

자료구조1. Stack

자료구조 중에서 가장 많이 알려진 stack 구조는 data를 넣고 빼는 곳이 한곳으로 가장 먼저 넣은 data는 가장 나중에 나오는 구조 (FILO) First In Last Out 입니다.

stack 을 이용한 알고리즘 문제

Balanced Brackets

opening bracket = '(', '[', '{'
closing bracket = ')', ']', '}'
pair 쌍 = (), [], {}

example

1
2
3
4
5
입력값
(({}))[]()

반환값
True
1
2
3
4
5
입력값
(({}))[)(]

반환값
False
1
2
3
4
5
입력값
[[[]]

반환값
False

풀이 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def is_matched(expression):
    '''
    expression : string type input -> "()()))"
    '''

    # {open bracket : close bracket} -> pair dictionary
    pair = {
        '{': '}',
        '(': ')',
        '[': ']',
    }

    # stack list that will be stacked by opening bracket
    stack = list()

    # if first bracket is closing bracket then return False
    if expression[0] not in pair.keys():
        return False

    # foor loop in string input
    for bracket in expression:
        # if bracket is opening bracket then push bracket
        if bracket in pair.keys():
            stack.append(bracket)
        # if bracket is closing bracket
        else:
            # exception case for out of index
            try:
                # if closing bracket and opening bracket are not pair
                # then return False
                if pair[stack.pop()] != bracket:
                    return False
                # if closing bracket and opening bracket are pair
                # then pop opening bracket from stack
                else:
                    continue
            # if stack is empty and bracket is closing bracket
            # then return False
            except:
                return False

    # if final stack is empty then return True
    if len(stack) == 0:
        return True
    # if there is opening bracket then return False
    else:
        return False

코드 설명

stack을 활용한 알고리즘입니다. stack에는 opening bracket만 쌓습니다. 계속 쌓다가 만약 가장 나중에 쌓인 opening bracket과 비교하려는 closing bracket의 pair가 맞지 않으면 False를 반환하는 알고리즘입니다.

복잡도 Big-O

  1. 시간 복잡도
  • O(N)
    • N : length of input string
    • 최악의 경우 input 값의 길이가 됩니다.
  1. 공간 복잡도
  • O(N)
    • N : number of opening bracket
    • 최악의 경우 input string이 전부 opening bracket인 경우
Share