안녕하세요 이번 시간에는 코딩테스트 문제 중 스택을 이용하여 푸는 문제들의 유형을 분석해보고 왜 스택을 사용하는지에 대해서 알아보는 시간을 갖도록 하겠습니다.
우선 첫 번째 유형은 쌍을 이루는 요소들을 찾는 문제입니다. 스택은 LIFO 특성을 가지고 있기 때문에 가장 최근에 푸시된 값을 참조 가능합니다. 따라서 가장 가까운 값과의 쌍을 확인해야 하는 문제의 경우 먼저 들어오는 쌍을 푸시하고 나중에 들어오는 쌍을 스택의 피크와 확인하여 같을 경우 쌍이고, 다를 경우는 쌍이 아닌 방식으로 확인이 가능합니다. 이 때 두 값이 쌍일 경우 스택을 팝하게 되면 모두 쌍으로 구성된 값들의 경우 스택이 비게 됩니다. 따라서 스택이 비어있는지 유무를 통해 모든 값이 쌍인지를 체크할수도 있습니다.
문제 예시를 들어보겠습니다. 백준의 9012번(괄호) 문제의 경우 괄호 쌍이 올바른지 확인하는 문제입니다. 위에서 살펴본 것처럼 '('를 스택에 추가하고 ')'일 경우 스택을 팝합니다. 이 때 비어 있는 스택을 팝하거나 최종 결과의 스택이 비어있지 않은 경우 잘봇된 경우를 리턴하므로 이 경우를 제외하면 됩니다.
3986(좋은 단어) 문제 역시 유사한 유형으로 스택에 값을 추가하고 찾을 경우 스택에서 팝하여 최종 스택이 비어있는지 유무를 체크하는 문제입니다.
10799(쇠막대기) 문제의 경우 레이저로 잘려진 쇠막대기의 총 수를 구하는 문제입니다. 이 경우 '()'이 레이저이고 나머지는 막대이기 때문에 '('일 경우 스택에 값을 추가시키고 ')'일 경우 만약 직전값이 '('일 경우 레이저이므로 현재 스택의 사이즈만큼, 아니라면 막대기이므로 1만큼 증가시키면 됩니다.
두 번째 유형은 커서를 기준으로 커서 위치 및 값을 조정하는 문제입니다. 배열이나 리스트를 통해 인덱스 값을 조정하는 방식은 탐색 속도가 O(N)인 반면, 현재 값을 기준으로 왼쪽 스택과 오른쪽 스택을 통해 값을 참조하는 방식은 O(1)X2이기 때문에 훨씬 더 빠릅니다. 또한 스택 특성상 왼쪽 스택에는 왼쪽 데이터 중 가지 자신과 가장 가까운 값이 추가되고 오른쪽도 마찬가지이기 때문에 로직적인 부분도 크게 문제가 되지 않습니다.
1406(에디터) 문제의 경우 커서의 위치를 조정 및 문자를 추가 삭제하는 것을 구현하는 문제입니다. 현재 위치의 왼쪽의 값을 왼쪽 스택에, 오른쪽의 값을 오른쪽 스택에 저장한 후 이동 및 추가 삭제를 구현하면 됩니다.
5397(키로거) 문제의 경우 문제와 백스페이스, 이동 키를 이용해서 입력 문자를 알아내는 문제입니다. 즉 1406의 역순이라고 생각하시면 됩니다. 마찬가지로 현재 위치를 0으로 잡고 왼쪽 스택과 오른쪽 스택에 값을 추가하여 최종 값을 리턴하면 됩니다.
세 번째 유형은 리스트를 탐색하면서 자기 자신과 값을 비교를 요구하는 문제입니다. 스택의 LIFO 특성으로 인해 리스트를 이동하는 과정에서 단순히 현재 시점에서 이전까지의 최대 혹은 최소값을 구하는 것에 그치지 않고, 구한 최대 혹은 최솟값 조건에 미치지 못한 값들의 리스트까지 같이 구할 수 있습니다. 따라서 단순히 최대 및 최소값을 구하는 것이 아니라, 특정 조건을 만족할 때까지의 최대 및 최소값을 구하고 만족 시 이전까지의 모든 값들을 변경해야 하는 경우 매우 적합합니다.
17298(오큰수) 문제의 경우 자기보다 크면서 오른쪽에 있는 수 중 가장 왼쪽에 있는 수를 구하는 문제입니다. 문제 특성상 하나의 큰 수 뒤로 모든 수가 다 작고, 그 순서가 내림차순으로 되어 있을 경우(예. 5,4,3,2,9) 9 이전의 모든 값을 다 변경해야 합니다. 따라서 일반적인 최대 최소값만으로 적용하는 것이 아니라 스택을 이용하여 현재 자신보다 큰 값이 아닐 경우 스택에 저장하고 큰 값이 나타나면 스택에 저장되어 있는 값들을 모두 현재 값으로 바꿔주는 방식으로 풀면 됩니다.
2304(창고 다각형)의 경우 창고 높이가 주어졌을 때 면적이 가장 작은 창고를 만드는 문제입니다. 이 문제 역시 오큰수랑 유사한 방식으로 스택을 이용하여 현재 자신보다 큰 값이 아닐 경우 스택에 저장하고 큰 값이 나타나면 스택의 가장 밑에 있는 값, 즉 현재까지 저장된 값 중 가장 큰 값의 인덱스까지 그 값으로 전부 바꾸는 방식으로 구현할 수 있습니다.
2841(외게인의 기타 연주) 문제의 경우 기타 연주 시 손가락을 가장 적게 움직이는 횟수를 구하는 문제입니다. 각 줄에서 더 앞의 줄이 눌리면 다른 손가락을 움직일 필요가 없고 작은 줄이 눌리면 그보다 큰 줄을 누른 손가락을 전부 떼야 하기 때문에 특정 조건을 만족할 때까지의 최대 및 최소값을 구하고 만족 이전까지의 모든 값들을 변경해야 하는 문제입니다. 각 줄 별로 스택(손가락이 누르고 있는 경우 푸시)을 만들어 입력된 값이 스택 피크보다 크면 그대로 푸시하고 작다면 입력값보다 작은 값이 피크가 될때까지 팝한 후 현재값을 푸시하면 됩니다. 이후 푸시 및 팝한 횟수를 리턴하면 됩니다.
3015(오아시스 재결합) 문제의 경우 두 사람 사이에 키가 큰 사람이 없어 서로를 볼 수 있는 쌍의 수를 구하는 문제입니다. 오큰수와 유사하지만 몇 가지 차이점이 존재합니다. 우선 쌍의 수를 구하기 때문에 스택에 저장되어 있는 값들을 변경하는 것이 아니라 스택에 저장된 수만큼 답을 증가시킵니다. 또한 오큰수와 달리 가장 큰 값의 오른쪽에 있는 값들도 고려를 해주어야 하기 때문에 스택에 값이 있는 상태에서 반복문이 종료될 경우 자기보다 전부 작은 값들이기 때문에 마주볼수 있는 케이스가 작은 값 중 최댓값 하나밖에 없어서 값을 1 증가시킵니다. 또한 오큰수와 달리 두 값이 같을 경우도 처리하되 큰 값처럼 처리하는 것이 아니라 누적합 개념으로 한번에 묶어서 값을 처리하는 방식으로 해결합니다.
마지막 유형은 후위 표기식 문제입니다. 후위 표기식이란 연산자를 피연산자 뒤에 위치시키는 표기법입니다.
후위 표기식을 잘 살펴보면 연산자의 경우 뒤에서부터 피연산자가 나오기 직전의 연산자부터 수행된다는 특징이 있습니다. 따라서 연산자를 스택에 넣게 되면 피연자가 나올때까지 연산자를 스택에 넣고 피연산자가 나오면 피연산자의 우선순위에 맞게 출력해주면 구현이 가능합니다.
