스택

• 정올 #1141 불쾌한 날(Bad hair day) , #1328 빌딩, #1809 탑문제에 대한 설명이 포함되어 있습니다.

스택이란?
자료구조 중 하나로 “한쪽 끝이 막힌 막대”로 형상화된다. lIFO (LAST IN FIRST OUT)의 구조로, 가장 나중에 push한 원소가 가장 먼저 pop된다. 스택은 기본적인 array를 가지고 스택을 구현할 수 있지만, c++ "stack" 라이브러리에서 더 편리하게 구현된다. stack 라이브러리에는 여러 가지 기본 함수가 내재되어 있다.

• push(element) : element를 스택에 넣는다.
• pop() : 가장 위의 원소를 꺼낸다.
• empty() : 스택이 비어있는지 확인한다. 스택이 비어있을 경우 true, 아니면 false를 반환한다.
• size() : 스택에 들어있는 원소의 개수를 반환한다.
• top() : 스택의 맨 위가 아닌 맨 아래 원소를 반환한다.

#1141 불쾌한 날(Bad hair day)

"Bad hair day" 문제를 처음 풀었을 때, 먼저 단순한 브루트 포스를 사용했다. 타임에러를 고려하지 않았을 첫 시도 당시, 가장 쉬운 이론적으로 가능한 풀이였다. 중복 for문으로 O(n^2) 풀이를 구현했고, 실제로 채점했을 때 90점이 나왔지만, 타임 리밋이 없다면 문제의 의미가 없었을 것이다.

스택을 이용한 풀이는 다음과 같다.

맨 왼쪽에 있는 소부터 보는 게 아니라, 맨 오른쪽에 위치한 n번째 소부터 스택 b에 넣어 처리한다. cnt는 현재 스택에 있는 소의 수(앞서 말한 내장 함수에서 항상 b.size() = cnt)로, 처음에는 아무 소도 넣지 않았으니 cnt를 0으로 초기화해준다. 스택 b에 원소(소)가 존재하고(empty() : false), 현재 소 (X라 하자)의 크기가 스택의 맨 위에 있는 소(b[cnt]) 크기보다 클 때 (= 현재 소가 앞에 있는 (스택에 미리 저장한) 소를 볼 수 있을 때) 스택에서 그 소를 pop하고, 스택의 원소 개수 cnt를 -1 해준다. 이때 cnt는 항상 스택의 맨 위 원소를 가리키는 포인터이다.

이런 식으로 while문 안에서 스택의 맨 위 소와 현재 소(X)를 비교하고 pop하는데, 스택의 맨 위 소가 현재 소보다 크기가 커서 볼 수 없을 때 while문을 탈출한다. 현재 소 X가 앞에서 자신보다 크거나 같은 소 Y를 마주했을 때 Y 앞의 소들은 볼 수 없게 된다. 따라서 자신보다 더 큰 소를 만나는 순간 더 이상 스택에 저장된 앞의 소들과의 비교는 무의미하므로 while문을 탈출한다.

이때 X가 볼 수 있는 소의 수를 result에 더한다. 스택에 원소가 존재할 때는 b[cnt](소 Y의 index) - i (현재 소 X의 index) - 1을 더하고, 스택의 원소가 존재하지 않을 경우, 소 X가 자신 앞에 있는 모든 소를 볼 수 있기 때문에 그냥 n (원래 배열 전체 소의 수) - i (현재 소 X의 index)을 더한다.

이 과정을 끝내면 소 X가 볼 수 있는 소를 모두 result에 합산한 것이다. 이제 현재 소 X를 스택에 넣고, 이 모든 과정을 다음 소에 대해 똑같이 반복한다. 그렇게 n번째 소부터 첫 번째 소까지 이 과정을 for문으로 반복하면 마지막 result가 곧 문제에서 찾는 답이다.

이때 주의할 점은 result의 범위인데, 대략 (80000^2)/2까지 증가할 수 있으니 int형으로 선언하지 말고 long long으로 선언하도록 한다. 자료형 범위에 따른 선언을 틀리는 실수를 내가 많이 한다.

#include <stdio.h>
int a[80005];
long long result = 0;
int b[80005];
 
int main(void){
    int n;
    scanf("%d", &n);
    for(int i = 1; i<= n; i++){
        scanf("%d", &a[i]);
    }
     
    int cnt = 0;
    for(int i = n; i>= 1; i--){
        while(cnt && a[i] > a[b[cnt]]){
            cnt--;
        }
        if(cnt){
            result += b[cnt] - i - 1;
        }
        else{
            result += n-i;
        }
        b[++cnt] = i;
    }
  
    printf("%lld \n", result);
    return 0;
}

#1328 빌딩

앞서 풀었던 문제와 거의 비슷하다. 다만 빌딩의 경우 같은 높이의 빌딩을 볼 수 없고, 자신보다 높은 빌딩만 볼 수 있다. (부등호에 주의하자.) 또, 문제에서 요구하는 답이 빌딩의 개수가 아닌 가장 가까운 빌딩이므로, 반환하는 값 역시 가장 가까운 빌딩의 높이의 배열이다. 이 외 모든 코드의 흐름은 전 문제와 완전히 같다.

#include <stdio.h>
int a[100005];
int result[1000005];
int b[100005];
 
int main(void){
    int n;
    scanf("%d", &n);
    for(int i = 1; i<= n; i++){
        scanf("%d", &a[i]);
    }
     
    int cnt = 0;
    for(int i = n; i>= 1; i--){
        while(cnt && a[i] >= a[b[cnt]]){
            cnt--;
        }
        if(cnt){
            result[i] = b[cnt];
        }
        else{
            result[i] = 0;
        }
        b[++cnt] = i;
    }
   
    for(int i = 1; i<= n; i++){
        printf("%d \n", result[i]);
    }
       
    return 0;
}

#1809 탑

역시 마찬가지로 거의 같은 유형의 코드이다.

#include <stdio.h>
int a[1000000];
int result[1000005];
int b[1000000];
 
int main(void){
    int n;
    scanf("%d", &n);
    for(int i = 1; i<= n; i++){
        scanf("%d", &a[i]);
    }
     
    int cnt = 0;
    for(int i = 1; i<= n; i++){
        while(cnt && a[i] > a[b[cnt]]){
            cnt--;
        }
        if(cnt){
            result[i] = b[cnt];
        }
        else{
            result[i] = 0;
        }
        b[++cnt] = i;
 
    }
  
    for(int i = 1; i<= n; i++){
        printf("%d ", result[i]);
    }
      
    return 0;
}