챕터2-1. 자료구조 | 스택(Stack)

스택의 개념

# 스택이란

- 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조

- 마지막으로 넣은 것이 가장 먼저 나오기 때문에 LIFO(Last In First Out) 라고도 한다.

- 가장 가까이에 있는 원소끼리 연산을 push, pop하여 해결되는 것은 O(1)이 걸린다는 특징이 있다. 이것이 스택의 특징.

 

# 직접 구현하기 위해 필요한 요소

- 데이터를 저장할 '배열'

- 다음에 삽입될 index의 위치, 혹은 들어있는 원소의 개수를 가리키는 'size 변수'

 

# 스택의 연산

- push() : 스택의 맨 위에 자료를 넣음

- pop() : 스택의 맨 위에서 자료를 뺌

- top() : 스택의 맨 위에 위치한 자료를 읽어옴

- empty() : 스택이 비어있는지 아닌지를 알아봄

- size() : 스택에 저장되어있는 지료의 개수를 반환함(다음에 자료가 삽입될 index위치를 가리키기도함)

 

@ push연산 예시

<첫 번째 push>

stack[size] = 1    // 현재 size의 위치에 자료삽입
size += 1          // size는 0->1 (삽입하였으므로 size를 1증가시킴)

<두 번째 push>

stack[size] = 3    // 현재 size의 위치에 자료삽입
size += 1          // size는 1->2 (삽입하였으므로 size를 1증가시킴)

초기상태 -> push(1) -> push(3)

@ pop연산 예시

<첫 번째 pop>

stack[size-1] = 0  // size-1 번째에 들어있는 값을 지워버린다(생략가능, size만 바꿔주면 덮여씌어지므로)
size -= 1          // size는 2->1 (제거하였으므로 size를 1감소시킴)

<두 번째 pop>

stack[size-1] = 0  // size-1 번째에 들어있는 값을 지워버린다(생략가능, size만 바꿔주면 덮여씌어지므로)
size -= 1          // size는 1->0 (제거하였으므로 size를 1감소시킴)

 

초기상태 -> pop() -> pop()

스택을 적용한 문제풀이

# 스택을 구현하는 문제

- https://www.acmicpc.net/problem/10828

@ 직접구현(C++) : 배열이용

@ C++ : STL의 stack 이용

@ Java : java.util.Stack 이용

@ Python : List 이용

 

# 괄호의 쌍이 올바른지 확인하는 문제

- https://www.acmicpc.net/problem/9012

- '(' 와 ')' 로만 이루어진 문자열에서 괄호의 쌍이 올바른지 판단하는 문제이다.

@ 시간복잡도가 O(N^2)인 해결방법 (비효율적)

- 어떤 닫는 괄호가 있을 때, 자기랑 짝이 맞는 여는 괄호는 아래의 3가지 조건을 충족해야 한다.

   1. 닫는 괄호보다 왼쪽에 있어야 한다.

   2. 아직 짝을 맞추지 않았어야 한다.

   3. 1번과 2번에 해당하는 문자중에서 가장 오른쪽에 있는 괄호이어야 한다.

- 위의 내용을 토대로 주어진 문자열에서 괄호의 쌍이 올바른지 판단하는 알고리즘

   1. 왼쪽에서 오른쪽으로 탐색을 하며 여는 괄호는 그냥 지나간다.

   2. 닫는 괄호를 만나면 닫는 괄호가 있는 위치로부터 왼쪽방향으로 이동하며 아직 짝을 맞추지 않은 여는 괄호를 찾는다.

   3. 찾았다면 여는 괄호를 짝을 맞춘 상태라고 표시해준다.

   4. 이를 문자열의 끝까지 진행하여 닫는 괄호에 대해 모두 짝이 맞는지 확인하여 결과를 출력한다.

- 이 알고리즘이 O(N^2)의 시간복잡도를 가지는 이유는 다음과 같다.

   길이가 N인 문자열에 대해서 왼쪽->오른쪽 방향으로 순차적인 탐색을 수행하는데

   여는 괄호에 대해서는 아무것도 수행하지 않고 그냥 지나치므로 O(1)이며, 

   닫는 괄호에 대해서는 현재 위치를 기준으로 왼쪽방향으로 한번씩 이동하며 앞에 오는 모든 괄호를 검사해야한다.

   이는 최상의 경우, 한 번만에 짝이 맞는 괄호를 찾아내겠지만, 최악의 경우 N번이 소요되므로 이에대한 시간복잡도는 O(N)이다.

   따라서, 문자열의 길이가 N이므로 대략적으로 O(N^2)의 시간복잡도가 나오게 된다. 위의 방법에 비해 엄청 비효율적임.

 

@ 시간복잡도가 O(N)인 해결방법 (더 효율적)

- 여는 괄호가 나오면 스택에 넣고 닫는괄호가 나오면 스택에서 꺼내어 여는괄호인지 확인하는 방식.

- 이 방식은 여는괄호, 닫는괄호 모두 각각 O(1)의 복잡도를 가지고 이를 길이가 N인 문자열에 적용하므로 O(N)의 시간복잡도를 가진다.

- 문제가 있는 문자열인 경우

   case 1) 닫는 괄호가 나왔는데 스택에 여는괄호가 없는 경우.

   case 2) 탐색이 끝났는데 스택이 비어있지 않은경우.

- 정상인 문자열인 경우

   case 1) 위 2가지 이외의 경우 즉, 탐색이 끝났을때 스택이 비어있는 경우

 

@ 시간복잡도가 O(N)인 해결방법 (가장 효율적)

- 스택에 들어가는게 여는괄호밖에 없으므로 스택에 뭐가 들어있는지는 중요하지 않고 몇 개가 들어있는지가 중요하다.

- 여는괄호면 cnt +=1, 닫는괄호면 cnt -=1 을 해주면서

   중간에 cnt가 0보다 작아지거나 다 끝났는데 cnt가 0이 아니거나 하면 비정상으로 끝내고
   다 끝났는데 0이면 정상으로 끝낸다.

- 스택을 이용하지 않고 개수만 카운트 하는 것으로도 문제를 해결할 수 있다.

- cnt 변수 이용

 

# 쇠막대기 문제

- https://www.acmicpc.net/problem/10799

- 여는 괄호와 닫는 괄호의 인접한 쌍 "( )"을 레이저로 인식해야 하므로 각 문자열의 index를 스택에 넣는 방식으로 해결해야 한다.

- 알고리즘

   1. 문자열에서 한 문자씩 읽어들이는 것을 문자의 끝까지 계속한다.

   2. case1) 여는 괄호이면 그 위치의 인덱스를 스택에 push한다.
       case2) 닫는 괄호이면 그 위치의 인덱스와 스택의 top에 있는 값을 비교한다. 
                   case2-1) 차이가 1인경우 레이저로 인식하여 pop하고 스택에 남아있는 원소의 개수를 정답에 더해준다.

                   case2-2) 차이가 1이 아닌경우 pop하고 1을 정답에 더해준다.(이전의 레이저에 의해 잘린 마지막 조각을 더해주는 것)

3. 최종 정답을 출력한다.

 

# 에디터 문제

- https://www.acmicpc.net/problem/1406

- 한 줄 짜리 에디터를 시뮬레이션 하는 문제.

- abc|xyz  >L>  ab|cxyz  >B>  a|cxyz  >D>  ac|xyz  >P d>  acd|xyz

 

@ 비효율적인 방법

- 배열이나 문자열 중간에 뭔가를 삭제하거나 삽입하는 시간은 길이만큼 걸리게 된다. 그 길이가 N이라면 각각의 명령의 시간복잡도는 아래와 같다.

- L : 커서를 왼쪽으로 한 칸 옮김        -> O(1)

  D : 커서를 오른쪽으로 한 칸 옮김     -> O(1)

  B : 커서 왼쪽에 있는 문자를 삭제함  -> O(N)

  P $ : '$' 문자를 커서 오른쪽에 추가하고 커서는'$'오른쪽에 위치시킴  -> O(N)

- 따라서, 전체 시간복잡도는 문자열의 길이가 N일 때 최악의 경우"O(N) * 명령어의 개수"가 된다.
   문제에서 실행할 명령의 개수는 최대 500,000개 이고, 문자열의 길이는 최대 100,000이라고 한다.
   따라서 전체 시간복잡도는 "O(문자열의 길이 * 실행할 명령의 개수)" 약 50,000,000,000 (100억)이 되는데

   1억이 1초라고 한다면 1분40초정도가 소요된다. 따라서 좀 더 효율적인 방식으로 문제를 풀어야 한다.

 

@ 효율적인 방법

- 커서를 기준으로 왼쪽 스택과 오른쪽 스택으로 나누어 문제를 해결할 수 있다.

- L : 커서를 왼쪽으로 한 칸 옮기는 예시  (pop, push 두번의 연산만이 요구되므로 시간복잡도는 O(1))

- D : 커서를 오른쪽으로 한 칸 옮기는 예시  (pop, push 두번의 연산만이 요구되므로 시간복잡도는 O(1))

- B : 커서 왼쪽에 있는 문자를 삭제하는 예시 (pop 한번의 연산만이 요구되므로 시간복잡도는 O(1))

- P $ : '$' 문자를 커서 오른쪽에 추가하고 커서는'$'오른쪽에 위치시키는 예시 (push 한번의 연산만이 요구되므로 시간복잡도는 O(1))

- 따라서 전체 시간복잡도는 "O(1) * 실행할 명령의 개수" 즉, 500,000 이므로 위의 문제보다 복잡도가 엄청 줄어들었다.

- 마지막 출력은 왼쪽 스택의 글자를 차례로 pop 하여 오른쪽의 스택에 push해준 다음 하나씩 꺼내어 출력하면 된다.