본문 바로가기
CT

[BOJ] 29단계 스택2

kinggora 2023. 7. 21. 13:09
1 9935 문자열 폭발
  • 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
  • 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
  • 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
  • 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

모든 폭발이 끝나고 남는 문자열을 구하는 문제

남아있는 문자가 없는 경우에는 "FRULA"를 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String string = reader.readLine();
        String burst = reader.readLine();

        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < string.length(); i++) {
            stack.push(string.charAt(i));
            if(stack.size() >= burst.length()) {
                boolean burstOut = true;
                for(int j = 0; j < burst.length(); j++) {
                    if (stack.get(stack.size() - burst.length() + j) != burst.charAt(j)) {
                        burstOut = false;
                        break;
                    }
                }
                if(burstOut) {
                    for(int j = 0; j < burst.length(); j++) {
                        stack.pop();
                    }
                }
            }
        }

        if(stack.size() == 0) {
            System.out.println("FRULA");
        } else {
            StringBuilder sb = new StringBuilder();
            for(char c: stack) {
                sb.append(c);
            }
            System.out.println(sb);
        }
    }
}

 

  • 폭발이 일어나면 문자열이 재배치된다.
  • 1차원 배열과 같은 자료구조에 저장하면 폭발 후에 인덱스의 공백이 생김. 문자를 하나씩 읽을 때마다 뒷 부분에서 폭발 문자열 포함 여부를 확인하고 제거할 수 있어야 함 -> stack
  • 문자열이 재배치되어도 폭발 문자열이 포함될 수 있다 -> 반복 필요
  • 스택의 top 부분에서 폭발 문자열 길이만큼 확인하고 폭발 문자열이라면 pop

 

2 17298 오큰수

크기가 N인 수열 A = A1, A2, ..., AN (N >= 1)이 있을 때, 수열의 각 원소 Ai에 대한 오큰수 NGE(i)

Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다.

그러한 수가 없는 경우에 오큰수는 -1이다.

A = [3, 5, 2, 7]인 경우

  NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1

A = [9, 5, 4, 8]인 경우

  NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

*1차원 배열에 저장하고 O(n)=n^2 로 풀면 시간 초과

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        int[] seq = new int[N];
        StringTokenizer st = new StringTokenizer(reader.readLine());
        for(int i = 0; i < N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }
        
        Stack<Integer> stack = new Stack<>();
        int[] nge = new int[N];
        for(int i = N - 1; i >= 0; i--) {
            while(!stack.isEmpty()) {
                if(seq[i] < stack.peek()) {
                    nge[i] = stack.peek();
                    stack.push(seq[i]);
                    break;
                } else {
                    stack.pop();
                }
            }
            if(stack.isEmpty()) {
                nge[i] = -1;
                stack.push(seq[i]);
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int n : nge) {
            sb.append(n).append(" ");
        }
        System.out.println(sb);
    }
}

스택에 값을 저장

루프 1번에 nge를 구할 수 있지만 입력을 역순으로 읽고 저장해야 함

  •  NGE(i)는 i번째 수의 오른쪽에 있음
  • 오른쪽에 있는 수 중 가장 큰 값보다도 자기가 더 크면 NGE(i)=-1
  • 입력을 뒤에서부터 읽어서 nge의 가능성이 있는 수를 stack에 내림차 순으로 push
  • input < stack.top 이면, nge = stack.top
  • stack이 빌 때까지 조건을 만족하지 않는다면,  nge = -1; stack.push(input)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        int[] seq = new int[N];
        StringTokenizer st = new StringTokenizer(reader.readLine());
        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i < N; i++) {
            while(!stack.isEmpty()) {
                if(seq[stack.peek()] < seq[i]) {
                    seq[stack.pop()] = seq[i];
                } else {
                    stack.push(i);
                    break;
                }
            }
            if(stack.isEmpty()) {
                stack.push(i);
            }
        }

        while(!stack.isEmpty()) {
            seq[stack.pop()] = -1;
        }

        StringBuilder sb = new StringBuilder();
        for(int n : seq) {
            sb.append(n).append(" ");
        }
        System.out.println(sb);
    }
}

 

스택에 인덱스를 저장

마지막에 스택에 남은 인덱스에 대한 값을 -1로 지정해주는 작업 필요

  • nge가 초기화 되지 않은 인덱스를 stack에 저장
  • seq[stack.top] < seq[input] 이면, NEG(stack.top)=seq[input] 이고 top이 초기화 되었으므로 pop() => 반복
  • 그렇지 않으면 인덱스를 stack에 push

 

3 17299 오등큰수

크기가 N인 수열 A = A1, A2, ..., AN이 있을 때, 수열의 각 원소 Ai에 대한 오등큰수 NGF(i)

Ai가 수열 A에서 등장한 횟수를 F(Ai) 라고 할 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수

그러한 수가 없는 경우에 오등큰수는 -1이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        int[] seq = new int[N];
        int[] f = new int[1000001];
        StringTokenizer st = new StringTokenizer(reader.readLine());
        for(int i = 0; i < N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
            f[seq[i]]++;
        }

        Stack<Integer> stack = new Stack<>();
        int[] ngf = new int[N];
        for(int i = N - 1; i >= 0; i--) {
            while(!stack.isEmpty()) {
                if(f[seq[i]] < f[stack.peek()]) {
                    ngf[i] = stack.peek();
                    stack.push(seq[i]);
                    break;
                } else {
                    stack.pop();
                }
            }
            if(stack.isEmpty()) {
                ngf[i] = -1;
                stack.push(seq[i]);
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int n : ngf) {
            sb.append(n).append(" ");
        }
        System.out.println(sb);
    }
}

2번 문제에서 오등큰수를 판별하는 if절만 다르다.

if(f[seq[i]] < f[stack.peek()]) {
    ngf[i] = stack.peek();
    stack.push(seq[i]);
    break;
} ...

 

5 12789 도키도키 간식드리미

 

스택을 활용하여 오름차순으로 학생을 빼내는 문제

  • 입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.
  • 다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.
  • 승환이가 무사히 간식을 받을 수 있으면 "Nice", 그렇지 않다면 "Sad"를 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        // 현재 줄 서있는 곳
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        // 한 명씩만 설 수 있는 공간
        Stack<Integer> stack = new Stack<>();
        
        // 찾는 번호표: i번
        for(int i = 1; i <= n; i++) {
            // stack 에서 i 찾기
            if(!stack.isEmpty() && stack.peek() == i) {
                stack.pop();
                continue; // 찾으면 다음 번호표로
            }
            // token 에서 i 찾기
            boolean result = false;
            while(tokenizer.hasMoreTokens()) {
                int number = Integer.parseInt(tokenizer.nextToken());
                if(number == i) {
                    result = true;
                    break;
                }
                stack.push(number); // i가 아닌 수 -> stack에 저장
            }
            // stack 과 token 에서 i를 찾지 못한 경우 실패
            if(!result) {
                System.out.println("Sad");
                return;
            }
        }
        System.out.println("Nice");
    }
}

 

stack.top에 새로운 값이 쌓이기 전에 먼저 탐색

처리해야 하는 번호표(i)와 stack.top 값이 다르다면 token 읽고 stack 채우기

 

성공 조건

처리해야 하는 번호표를 모두 소진 => for-loop 가 정상적으로 종료

 

실패 조건

처리해야 하는 번호표가 있는데 => for- loop 가 끝나지 않은 상태

한 명씩만 설 수 있는 공간(stack.top)에도 현재 줄 서있는 곳(token)에도 찾는 번호표가 없을 때

 

4 1725 히스토그램

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 [2 1 4 5 1 3 3]이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(reader.readLine());
        }
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        stack.push(0);
        for(int i = 1; i < n; i++) {
            while(!stack.isEmpty()) {
                if(arr[stack.peek()] <= arr[i]) {
                    break;
                }
                int height = arr[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        while(!stack.isEmpty()) {
            int height = arr[stack.pop()];
            int width = stack.isEmpty() ? n : n - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        System.out.println(maxArea);
    }
}

 

 

인접한 직사각형 2개의 넓이를 구할 때 둘 중 더 낮은 높이가 기준이 됨

즉, i번째 직사각형을 확장하려면 높이가 h(i)보다 크거나 같은 직사각형이 인접할 때 가능

 

1. 직사각형을 순차적으로 방문할 때 이전 위치(i-1)보다 현재 위치(i)의 높이가 낮으면 이전 위치까지의 직사각형의 넓이 계산

  • 현재(i)보다 높이가 낮거나 같은 직사각형을 만날 때까지 또는 스택이 empty 상태가 될 때까지 pop하여 넓이를 계산하고 최댓값(maxArea) 비교
  • 스택에 저장된 직사각형은 높이에 대한 오름차 순으로 정렬되어 있음 → 스택에 직사각형이 a b 순으로 저장되었다면 [ a, b 사이의 거리 * a의 높이 ] 의 넓이를 가지는 직사각형 생성 가능. 밑변에 해당하는 a, b 사이의 거리를 구하기 위해 스택에 직사각형의 위치(index)를 저장

2. 현재 위치(i)를 스택에 저장

3. 1, 2번을 n-1번 반복한 후, 스택이 empty 상태가 될 때까지 같은 과정 수행

'CT' 카테고리의 다른 글

[BOJ] 30단계. 그래프와 순회 2  (0) 2024.05.10
[BOJ] 30단계. 그래프와 순회 1  (0) 2024.05.07
[BOJ] 28단계 동적 계획법 2  (0) 2023.06.16
[BOJ] 27단계 우선순위 큐  (0) 2023.06.14
[BOJ] 26단계 이분 탐색  (0) 2023.05.17

'CT' Related Articles

티스토리툴바