uncategorized

Data Structure(Deque)

자료구조2. Deque

자료구조 중에서 stack과 queue를 합쳐 놓은 자료구조 방식으로, data를 넣고 빼는 곳이 두 곳으로 두 군데에서 모두 push / pop 이 가능한 자료 구조입니다.

deque 을 이용한 알고리즘 문제 (1)

비교 대상이 되는 문장 base_sentence와 비교하는 문장 compare_sentence가 주어집니다.

compare_sentence 속에있는 단어는 모두 base_sentence 속에 있어야 하며, 단어의 순서 또한 같아야 합니다.

example

1
2
3
4
5
6
# 입력값
base_sentence = "give me one grand today night"
compare_sentence = "give one grand today"

# 반환값
True
1
2
3
4
5
6
# 입력값
base_sentence = "I am student"
compare_sentence = "I am singer"

# 반환값
False
1
2
3
4
5
6
# 입력값
base_sentence = "one two three four"
compare_sentence = "one three two"

# 반환값
False

풀이 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def check_duplicate(base_sentence, compare_sentence):

    '''
    base_sentence : string type sentence
    compare_sentence = string type sentence
    '''
    base_sentence_list = base_sentence.split(' ')
    # make deque data Structure
    compare_deque = compare_sentence.split(' ')

    for word in base_sentence_list:
        # exception for index error
        try:
            # if base_sentence word and compare_deque word are same
            # then pop the word from compare_deque
            if word == compare_deque[0]:
                compare_deque.pop(0)
        # if compare_deque is empty then return True
        except:
            return True

    # if compare_deque is not empty then return False
    return False if len(ransome_deque) != 0 else True

복잡도 Big-O

시간 복잡도

  • O(N)
    • N : number of base_sentence words
    • 최악의 경우 base_sentence 총 단어의 갯수가 됩니다.

공간 복잡도

  • O(N)
    • N : Max(base_sentence 단어 갯수, compare_sentence 단어 갯수)
Share