Seok Seung Min

1Page 노트정리 스택

1 Page 노트 정리

new repo

스택(Stack)의 개념과 활용

스택(Stack)은 후입선출(Last-In-First-Out; LIFO) 원리를 따르는 대표적인 선형 자료구조입니다. 이는 나중에 들어온 데이터가 가장 먼저 나간다는 의미로, 데이터가 입력된 순서대로 처리되지 않고 가장 나중에 들어온 데이터를 먼저 처리할 때 사용됩니다.

스택의 특징

  • 후입선출 구조 (LIFO): 먼저 들어간 자료가 나중에 나오는 구조입니다.
  • 시스템 해킹: 버퍼 오버플로우 공격 등에서 스택 메모리 영역을 이용합니다.
  • 인터럽트 처리: 수식 계산, 서브루틴의 복귀 번지 저장 등에 사용됩니다.
  • 재귀 함수 호출: 재귀 함수의 호출에서 사용됩니다.
  • 그래프 탐색: 깊이 우선 탐색(DFS)에서 사용됩니다.

시간 복잡도

스택의 삽입과 삭제 연산은 모두 O(1)의 시간 복잡도를 가집니다. 이는 삽입과 삭제가 항상 스택의 top에서 일어나기 때문입니다.

연산 평균 소모 시간 최악 소모 시간
Acess O(n) O(n)
Search O(n) O(n)
Push O(1) O(1)
Pop O(1) O(1)

Java에서의 스택 사용법

스택 선언

import java.util.Stack;

Stack<Integer> stack = new Stack<>();

스택 값 추가

stack.push(1);  // stack에 1 추가
stack.push(2);  // stack에 2 추가
stack.push(3);  // stack에 3 추가

스택 값 삭제

stack.pop();    // stack의 맨 위 값 삭제

스택의 가장 상단 값 확인

int topValue = stack.peek();  // stack의 가장 상단 값 확인

기타 메서드

int size = stack.size();          // stack의 크기 출력
boolean isEmpty = stack.empty();  // stack이 비어있는지 확인 (비어있다면 true 반환)
boolean contains = stack.contains(1);  // stack에 1이 있는지 확인 (있다면 true 반환)
stack.clear();                    // stack에 들어있는 모든 값 초기화
int index = stack.search(2);      // 2(value)의 인덱스 값 반환
메서드 설명
boolean empty() Stack이 비어있는지 알려줍니다.
Object peek() Stack의 맨 위에 저장된 객체를 반환합니다. pop()과는 달리 Stack에서 객체를 꺼내지는 않습니다. (비었다면 EmptyStackException 발생)
Object pop() Stack의 맨 위에 저장된 객체를 꺼냅니다. (비었다면 EmptyStackException 발생)
Object push(Object item) Stack에 객체(item)을 저장합니다.
int search(Object o) Stack에 주어진 객체(o)를 찾아서 그 위치를 반환합니다. 찾지 못하면 -1을 반환합니다. (배열과 달리 위치는 0이 아닌 1부터 시작합니다.)

필수 1문제

포스택

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 1024 MB 2488 988 724 38.531%

문제

포닉스는 길이가 N인 순열 A와 네 개의 비어 있는 스택을 가지고 있다.

길이가 N인 순열이란, 1 이상 N 이하의 서로 다른 정수 N개가 임의로 나열된 수열을 말한다.
스택이란 자료구조의 한 종류로 가장 나중에 삽입한 자료가 가장 먼저 나오는 후입선출 (Last In First Out, LIFO)의 특성을 가지고 있다.
포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다.

순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 즉 순열을 1, 2, 3, . . . N으로 만들어야 한다.

  1. 순열 A의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
  2. 순열 A의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
  3. 꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.

포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자.

입력

첫째 줄에 순열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에 순열 A의 원소 A_i가 공백으로 구분되어 주어진다. 모든 A_i는 1 이상 N 이하의 서로 다른 정수임이 보장된다.

출력

포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다.

예제 입력 1

10
4 3 6 7 8 9 10 2 1 5

예제 출력 1

YES

예제 입력 2

5
5 4 3 2 1

예제 출력 2

NO

문제풀이

랜덤으로 되어있는 순열을, 4개의 스택을 이용해서 오름차순으로 정렬을 하는 것이다.
여기서 중요한 것은 각 모든 스택은 오름차순으로 나열이 되어 있어야 한다.
이유는, 제일 큰 수를 오른쪽부터 왼쪽으로 숫자가 1씩 떨어지면서 정렬을 해야 하는 상황이다.
그래서 만약에 스택에 모든 숫자를 넣을 수 있다면, 오름차순으로 정렬이 가능하다.
반대로 스택에 숫자 하나라도 못 넣으면, 정렬이 불가능해진다.

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class BJ25556 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        Stack<Integer> stack3 = new Stack<Integer>();
        Stack<Integer> stack4 = new Stack<Integer>();

        int n = scanner.nextInt();
        ArrayList<Integer> list = new ArrayList<Integer>();

        for (int i = 0; i < n; i++) {
            list.add(scanner.nextInt());
        }

        boolean isPossible = true;
        for (int num : list) {
            if (stack1.empty() || stack1.peek() < num) {
                stack1.push(num);
            } else if (stack2.empty() || stack2.peek() < num) {
                stack2.push(num);
            } else if (stack3.empty() || stack3.peek() < num) {
                stack3.push(num);
            } else if (stack4.empty() || stack4.peek() < num) {
                stack4.push(num);
            } else {
                isPossible = false;
                System.out.println("NO");
                break;
            }
        }

        if (isPossible) {
            System.out.println("YES");
        }
    }

}

10
4 3 6 7 8 9 10 2 1 5
YES

5
5 4 3 2 1
NO

출처: 백준, https://www.acmicpc.net/problem/25556

문제 설명

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

  • arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 반환합니다.
  • arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 반환합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 반환하는 solution 함수를 완성해 주세요.

제한사항

  • 배열 arr의 크기: 1,000,000 이하의 자연수
  • 배열 arr의 원소의 크기: 0보다 크거나 같고 9보다 작거나 같은 정수

입출력 예

arr answer
[1, 1, 3, 3, 0, 1, 1] [1, 3, 0, 1]
[4, 4, 4, 3, 3] [4, 3]

입출력 예 설명

입출력 예 #1, #2

문제의 예시와 같습니다.

스택풀이

import java.util.*;

public class Solution {
    public int[] solution(int[] arr) {
        int[] answer = {};

        Stack<Integer> stack = new Stack<>();

        for (int i : arr) {
            if (stack.isEmpty()) stack.push(i);
            else if (stack.peek() != i) stack.push(i);
        }

        answer = new int[stack.size()];

        for (int i = answer.length - 1; i >= 0; i--) {
            answer[i] = stack.pop();
        }

        return answer;
    }
}

ArrayList풀이

import java.util.*;

public class Solution {
    public int[] solution(int[] arr) {
        List<Integer> answerList = new ArrayList<>();
        
        for (int i = 0; i < arr.length; i++) {
            if (i == 0 || arr[i] != arr[i - 1]) {
                answerList.add(arr[i]);
            }
        }
        
        int[] answer = new int[answerList.size()];
        for (int a = 0; a < answerList.size(); a++) {
            answer[a] = answerList.get(a);
        }
        
        return answer;
    }
}

테스트 1
입력값 〉	[1, 1, 3, 3, 0, 1, 1]
기댓값 〉	[1, 3, 0, 1]
실행 결과 〉	테스트를 통과하였습니다.
테스트 2
입력값 〉	[4, 4, 4, 3, 3]
기댓값 〉	[4, 3]
실행 결과 〉	테스트를 통과하였습니다.

출처: 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12906?language=java

Leave a comment

You may also enjoy