코딩 테스트 준비/개념

4. 스택

masxer 2025. 7. 4. 11:32

스택 추상 자료형(ADT / Abstract Data Type) : 인터페이스만 있고 실제로 구현은 되지 않은 자료형이다.

 

스택에는 push, pop, isFull, isEmpty와 같은 연산을 정의해야 한다. 그리고 스택은 최근에 삽입한 데이터의 위치를 저장할 변수인 top도 있어야 한다.

또한, 스택을 공부할 때 ADT뿐만 아니라 세부 구현도 알아두면 문제를 풀 때 도움이 된다.

 

스택 세부 동작에 대해

연산 과정은 push(2)를 호출하면 내부적으로 isFull()을 수행해 우선 data 배열에 데이터가 꽉찼는지 확인하고, 그렇지 않다면 top을 1만큼 증가시킨 후 top이 가리키는 위치에 data[0]에 3을 추가하면 된다.

반대로 pop() 연산을 수행한다면 내부적으로 isEmpty() 함수를 우선 수행해 data 배열에 데이터가 없는 건 아닌지 확인하고, 데이터가 있다면 top을 1만큼 감소시키고 데이터 3을 반환합니다.

올바른 괄호

 

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

제약 조건

문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

입출력 예

sanswer
"()()" true
"(())()" true
")()(" false
"(()(" false
 
입출력 예 설명

입출력 예 #1,2,3,4
문제의 예시와 같습니다.

다음은 짝이 맞지 않는 괄호의 예시이다. (1) 닫힌 괄호가 먼저 왔으므로 더 이상 상쇄 되지 않으며, 결과적으로 괄호가 전부 없어지지 않는다.

 

다른 예시도 마찬가지로 괄호의 짝이 맞지 않는다. 첫 괄의 짝은 맞아 상쇄할 수 있지만 (2) 마지막 괄호는 짝이 없으므로 상쇄할 수 없다.

 

그렇다면 짝이 맞는 경우를 살펴보자. 괄호의 짝이 맞으면 상쇄되고, (3) 그림에서 보듯 항상 첫 번째 짝만 괄호가 맞아야 할 필요는 없다.

 

주목해야 할 내용

닫힌 괄호가 임의 위치의 열린 괄호와 상쇄되는 것이 아니라 닫힌 괄호가 나오기 바로 전의, 즉 가장 가까운(최근) 열린 괄호와 상쇄된다는 것이다. 가장 가까운(최근)이라는 키워드를 보고 스택을 떠올리는 훈련이 필요하다.

 

괄호를 상쇄하는 과정

1. 문자열을 앞에서 하나씩 보며 열린 괄호가 나오면 푸시

2. 닫힌 괄호가 나오면 팝 연산을 통해 문자열에서 열린 괄호, 닫힌 괄호 한 쌍을 상쇄

3. 1~2를 마지막 문자열까지 반복해 스택에 열린 괄호가 남아 있다면 짝이 맞지 않은 것(false)이고, 괄호가 남아 있지 않다면 짝이 맞은 것(true)로 판단

 

 

1단계 과정을 자세히 살펴보자

크기가 6인 배열에 괄호를 배치하고 스택을 준비한다. 그런 다음 인덱스 0은 열린 괄호이므로 스택에 푸시하고 다음 인덱스에 있는괄호를 본다. 다음 인덱스에 있는 괄호는 닫힌 괄호이므로 스택에서 팝하고 다음 인덱스를 본다. 이 단계를 마치면 스택에는 아무것도 없으므로 인덱스 0~1에 한해서 괄호를 상쇄했다고 봐도 된다.

 

2단계 과정

인덱스 2는 열린 괄호이므로 푸시한다. 인덱스 3은 열린 괄호이므로 다시 푸시하고 다음을 본다. 이번엔 닫힌 괄호이므로 스택에서 팝하고 다음을 본다. 인덱스 5는 닫힌 괄호이므로 팝하고 연산을 마친다. 모든 탐색을 끝냈을 때 스택이 비어 있으므로 배열의 괄호는 모두 짝이 맞다고 볼 수 있다.

 

 

괄호의 짝이 맞지 않는 경우

그림과 같이 인덱스 2에 도달했을 때 열린 괄호 하나만 남으므로 짝이 맞지 않는다.

문제 코드 작성하기

 

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        Stack<Character> stk = new Stack<>();
        
        char[] ch = s.toCharArray();
        
        for(char c : ch) {
            if(c == '(') // 열린 괄호이면 push
                stk.push(c);
            else {
                if(stk.isEmpty() || stk.pop() == c) // 스택이 비어있거나 팝한 괄호가 c와 같을 때(열린 괄호)일 때는 false
                    return false;
            }
        }

        

        return stk.isEmpty(); // 스택이 비어있는지 확인 (비어 있으면 true, 비어 있지 않으면 false 반환)
    }
}

 

시간 복접도 분석하기

N은 s의 길이이고, s를 순회하며 괄호의 쌍을 확인하므로 시간 복잡도는 O(N)이다. 또한, 괄호 쌍을 확인할 때 push() 메서드와 pop() 메서드의 시간 복잡도는 O(1)이다.

 

짝지어 제거하기

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

 

제한사항

문자열의 길이 : 1,000,000이하의 자연수
문자열은 모두 소문자로 이루어져 있습니다.

 

입출력 예

sresult
baabaa 1
cdcd 0
 

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

 

문자열 제거 과정 생각해보기

보통 많은 사람들이 이중 반복문으로 문제를 해결하려는 경우가 많다. 나 역시 이중 반복문을 사용해야겠다는 생각이 먼저 들었다. 하지만 문자열의 최대 갈이는 100만이므로 이중 반복문은 O( 𝑛²)이기 때문에 사용할 수 없다. 따라서 O(n)인 알고리즘을 사용해야 한다. 따라서 이 문제는 스택으로 간단히 해결할 수 있는 문제였다. 앞에서 이야기 한 것 처럼 알고리즘이 바로 떠오르지 않는다면 문제를 이해하고 간단한 입력값, 출력값으로 문제가 해결되는 과정을 직접 그려보는 것이 좋다.

 

1단계

다음과 같은 문자열이 있다고 생각해보자.

 

2단계

가장 왼쪽부터 탐색해 AA를 찾아 제거한다.

3단계

문자열을 제거한 다음 BB가 붙으므로 BB를 제거하고 이어서 AA를 제거한다.

4단계

이 과정을 모두 마치면 모든 문자열이 제거되므로 이 문자열은 짝이 맞다고 볼 수 있다.

 

두 문자가 만나서 문자를 삭제하고, 붙이는 과정을 수학적으로 접근해 본다면 현재 가리키고 있는 문자가 i번째면 다음 문자는 i + 1번째이므로 이 둘을 비교한다. 이를 거꾸로 생각해 i + 1번째 문자 입장으로 이야기하면 바로 직전 문자, 즉, 최근 문자와 비교한다고 생각할 수 있다. 따라서 가장 최근에 탐색한 데이터를 먼저 비교한다고 할 수 있으므로 스택의 구조와 맞아 떨어진다.

 

그리고 문제 요구사항인 짝이 맞는 문자를 제거한 다음 문자열을 붙이는 연산은 팝 연산으로 자연스럽게 해결할 수 있으므로 구현 시 고려할 필요가 없다.

 

알고리즘 코드

 

import java.util.Stack;

class Solution
{
    public int solution(String s) {
        Stack<Character> stk = new Stack<>();
        
        char[] ch = s.toCharArray();
        for(char c : ch){
            if(stk.isEmpty()) { 
                stk.push(c);
            }else {
                if(c == stk.peek()){ // top이 가리키는 값과 비교
                    stk.pop(); // 스택의 맨 위 문자 제거
                }else {
                    stk.push(c); // 스택에 현재 문자 추가
                }
            }
        }
        
        return stk.isEmpty() ? 1 : 0; // 스택이 비어 있으면 1, 그렇지 않으면 0 반환
       
    }
}

 

시간 복잡도 분석

N은 s의 길이고 문자열의 모든 문자를 한 번씩 순회하므로 시간 복잡도는 O(N)이다.