[코딩테스트/알고리즘 맛집] 자바 스택(Stack) 문제 유형과 코드 정리

스택(Stack)

개요

"스택"은 데이터를 쌓아서 사용하는 자료구조로, "후입선출(LIFO, Last In First Out)" 방식으로 작동한다. 즉, 나중에 들어간 데이터가 먼저 나오는 구조이다. 스택은 주로 함수 호출, 계산기 프로그램에서 수식 계산, 또는 브라우저의 뒤로 가기 기능 등에서 사용된다.

* 이와 반대의 "선입선출(FIFO, First In First Out)" 구조의 자료구조를 '큐'라고 한다.  

 

스택을 활용한 코딩테스트 문제는 유형이 정해져 있다. 문제를 잘 읽어보고 데이터를 쌓아 올린다든지, 나중에 쌓은 데이터를 먼저 처리하는 방식이면 스택을 활용하면 된다. 

 

스택을 사용하는 문제 유형

 

✅ 괄호 유효성 검사

• 주어진 문자열에서 괄호의 짝이 맞는지 확인하는 문제
• 스택을 사용해 여는 괄호는 스택에 넣고, 닫는 괄호는 스택에서 하나씩 꺼내며 매칭을 확인한다. 

"()" → 유효
"({[()]})" → 유효
"([)]" → 유효하지 않음

 

✅ 후위 표기법 계산

• 수식이 후위 표기법으로 주어졌을 때 계산하는 문제
• 후위 표기법에서 숫자는 스택에 넣고, 연산자는 스택에서 숫자를 꺼내 계산 후 다시 스택에 넣는 방식으로 처리한다.

"2 3 + 5 *" → 25

 

✅ 가장 큰 직사각형 

• 히스토그램 형태의 막대그래프에서 가장 큰 직사각형을 찾는 문제
• 스택을 이용해 각 막대의 높이를 기준으로 직사각형의 최대 면적을 계산한다.

[2, 1, 5, 6, 2, 3] → 가장 큰 직사각형의 면적은 10

 

✅ 배열에서 두 번째로 큰 수 찾기

• 주어진 배열에서 두 번째로 큰 값을 찾는 문제
• 스택을 사용하여 배열을 한 번 순회하면서 조건에 맞는 값을 찾아낸다.

[5, 1, 7, 3, 9] → 두 번째로 큰 수는 7

 

✅ 주식가격 문제 (스택을 이용한 최댓값 구하기)

• 주어진 주식의 가격에서 오늘의 주식 가격을 기준으로 몇 일 전부터 가격이 더 높았는지 구하는 문제
• 스택을 사용하여 가격을 기록하면서 최대값을 찾아가는 방식
•  각 가격에 대해, 그 가격보다 더 높은 가격이 나온 가장 가까운 날을 찾는 것이 관건
• 스택에 가격과 해당 날짜를 쌍으로 저장
• 현재 가격보다 작은 가격이 나올 때까지 스택에서 꺼내고, 그 차이를 계산하여 결과에 저장
• 스택에 현재 가격을 추가
• 이렇게 하면 각 가격에 대해 몇 일 전부터 가격이 더 높았는지를 효율적으로 구할 수 있다.

[1, 2, 3, 2, 3] → [0, 1, 2, 1, 4]

 

✅ 최소값 구하기

• 스택에 요소를 넣을 때마다 현재 스택 내의 최소값을 추적해야 하는 문제
• 스택에 값을 넣을 때, 각 값과 함께 현재까지의 최소값을 함께 저장한다.
• 예를 들어, 값 x를 스택에 넣을 때, 현재 스택의 최소값을 min_value라고 할 때, 새로운 최소값은 min(min_value, x)로 설정하여 함께 저장한다.
• 이렇게 하면, 스택에서 값을 꺼낼 때 가장 최근의 최소값을 빠르게 찾을 수 있다. 

push(3), push(1), push(2), pop() → 최소값은 1

 

자바로 스택 구현

 

소스코드

package algo03.StackAndQueue;

public class myStack {
	public static void main(String[] args) {
		// 스택 구현한 코드
		// Stack은 후입선출(LIFO, Last In First Out) 방식으로 기능함

		StackExample stack = new StackExample(5); // 크기가 5인 스택 생성

		// 스택에 값 추가
		stack.push(10);
		stack.push(20);
		stack.push(30);

		// 스택의 가장 상단 값 확인
		System.out.println("스택의 가장 상단 값: " + stack.peek());

		// 스택에서 값 제거
		System.out.println("pop: " + stack.pop());
		System.out.println("pop: " + stack.pop());

		// 스택이 비었는지 확인
		System.out.println("스택이 비었나요? " + stack.isEmpty());

		// 스택의 크기 확인
		System.out.println("스택 크기: " + stack.size());

		// 스택에서 값을 더 제거
		System.out.println("pop: " + stack.pop());
		System.out.println("pop: " + stack.pop()); // 이때는 스택이 비어 있음
	}

	// StackExample 클래스 정의
	public static class StackExample {
		// Stack을 구현할 배열
		private int[] stack;
		private int top; // 스택의 가장 상단 인덱스를 추적

		// 생성자: 스택의 크기를 지정하여 배열을 초기화
		public StackExample(int size) {
			stack = new int[size]; // 주어진 크기의 배열을 생성
			top = -1; // 스택이 비어있으므로 top을 -1로 초기화
		}

		// 스택에 값을 추가하는 메소드
		public void push(int value) {
			// 스택이 꽉 찼을 때 예외 처리
			if (top == stack.length - 1) {
				System.out.println("스택이 꽉 찼습니다.");
			} else {
				stack[++top] = value; // top을 1 증가시키고 값을 추가
				System.out.println(value + "이(가) 스택에 추가되었습니다.");
			}
		}

		// 스택에서 값을 제거하고 반환하는 메소드
		public int pop() {
			// 스택이 비었을 때 예외 처리
			if (top == -1) {
				System.out.println("스택이 비어 있습니다.");
				return -1; // 스택이 비었으면 -1 반환
			} else {
				int poppedValue = stack[top--]; // top에서 값을 꺼내고 top을 1 감소
				return poppedValue; // 꺼낸 값 반환
			}
		}

		// 스택의 가장 상단 값을 반환하는 메소드 (값을 제거하지 않음)
		public int peek() {
			// 스택이 비었을 때 예외 처리
			if (top == -1) {
				System.out.println("스택이 비어 있습니다.");
				return -1; // 스택이 비었으면 -1 반환
			} else {
				return stack[top]; // top에 있는 값 반환
			}
		}

		// 스택이 비었는지 확인하는 메소드
		public boolean isEmpty() {
			return top == -1; // top이 -1이면 스택이 비어 있다는 의미
		}

		// 스택의 크기를 반환하는 메소드
		public int size() {
			return top + 1; // top 인덱스 + 1이 스택의 크기
		}
	}
}

 

예제 1 - 10진수를 2진수로 (decimalToBinary.java)

10진수를 입력받아 2진수로 변환해 반환하는 solution() 함수를 구현하세요

 

제한 조건

• decimal은 1이상 10억 미만의 자연수

 

입출력 예

decimal	return
10	1010
27	11011
12345	11000000111001

 

요점

• 주어진 십진수를 2로 나누며 나머지를 스택에 쌓고, 나중에 스택에서 하나씩 꺼내면 이진수가 나온다.

소스 코드

package algo03.StackAndQueue;

import java.util.Stack;

public class queue_decimalToBinary {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

	public static String solution(int decimal) {
		// 10진수를 2진수로
		Stack<Integer> stack = new Stack<>(); // 나머지를 저장할 스택

		while (decimal != 0) { // 몫이 0이 될 때 까지 반복
			stack.push(decimal % 2); // 나머지 스택에 넣기
			decimal /= 2; // 2로 나누기
		}

		StringBuilder sb = new StringBuilder();
		while (!stack.isEmpty()) {
			sb.append(stack.pop()); // 스택에 있는 나머지 꺼내기
		}
		return sb.toString();
	}
}

[코딩테스트] (Java) 십진수를 이진수로 변환하기 (스택)

 

예제 2 - 크레인 인형뽑기 게임 (craneGame.java)

게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음) 게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한 조건

• board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
• 0은 빈 칸을 나타냅니다.
• 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

 

입출력 예

board	moves	result
[[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]	[1,5,3,5,1,2,1,4]	4

 

요점

• 인형을 뽑을 때마다 해당 인형이 스택의 최상단 인형과 동일한지 확인한 후, 동일하다면 스택에서 두 인형을 모두 제거하고 점수를 2점 증가한다. 다르면 스택에 그 인형을 추가한다.

 

소스 코드

package algo03.StackAndQueue;

import java.util.Stack;

public class stack_craneGame {
	public static void main(String[] args) {
		int[][] board = { { 0, 0, 0, 0, 0 }, { 0, 0, 1, 0, 3 }, { 0, 2, 5, 0, 1 }, { 4, 2, 4, 4, 2 },
				{ 3, 5, 1, 3, 1 } };

		int[] moves = { 1, 5, 3, 5, 1, 2, 1, 4 }; // 크레인이 움직이는 위치 배열

		stack_craneGame game = new stack_craneGame();
		int result = game.solution(board, moves);

		System.out.println("터진 인형 개수: " + result); // 예상 출력: 4
	}

	public int solution(int[][] board, int[] moves) {
		// 프로그래머스 크레인 인형봅기 게임 문제
		
		int answer = 0; // 터진 인형의 총 개수 (2개씩 사라짐)
		Stack<Integer> stack = new Stack<>(); // 뽑은 인형을 저장할 스택

		// 'moves' 배열의 각 이동에 대해 반복
		for (int move : moves) {
			// 각 열을 순차적으로 확인 (board.length는 행의 개수)
			for (int j = 0; j < board.length; j++) {
				// 현재 위치에 인형이 있다면 (0이 아닌 값)
				if (board[j][move - 1] != 0) {
					int doll = board[j][move - 1]; // 해당 위치의 인형을 가져옴

					// 스택이 비어있지 않고, 스택의 맨 위 인형과 현재 인형이 같으면
					if (!stack.isEmpty() && stack.peek() == doll) {
						stack.pop(); // 인형을 터뜨리기 위해 스택에서 제거
						answer += 2; // 같은 인형이 터져서 2개가 사라짐
					} else {
						stack.push(doll); // 스택에 인형을 추가
					}

					board[j][move - 1] = 0; // 뽑은 인형은 해당 위치에서 제거 (0으로 설정)
					break; // 한 번에 하나의 인형만 뽑을 수 있으므로 반복문을 탈출
				}
			}
		}

		return answer; // 터진 인형의 총 개수 반환
	}

}

[프로그래머스] (Java) 크레인 인형 뽑기 게임 (스택)

 

예제 3 - 같은 숫자는 싫어 (noMoreSameNums.java)

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

예를 들면,
arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 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]

 

요점

• 연속된 중복 숫자를 제거하는 방법은, 이전 숫자와 다를 때만 스택에 추가하고, 최종적으로 스택에 남은 요소들을 배열로 변환하여 반환하는 방식으로 해결 가능하다. 

 

소스 코드

package algo03.StackAndQueue;

import java.util.Arrays;
import java.util.Stack;

public class stack_noMoreSameNums {

	public static void main(String[] args) {
		// 프로그래머스 같은 숫자는 싫어 문제
		stack_noMoreSameNums solution = new stack_noMoreSameNums();

		// 테스트 1
		int[] arr1 = { 1, 1, 3, 3, 0, 1, 1 };
		System.out.println("Test 1: " + Arrays.toString(solution.solution(arr1))); // [1, 3, 0, 1]

		// 테스트 2
		int[] arr2 = { 4, 4, 4, 3, 3, 2, 2 };
		System.out.println("Test 2: " + Arrays.toString(solution.solution(arr2))); // [4, 3, 2]

		// 테스트 3
		int[] arr3 = { 7, 8, 8, 7, 9, 7 };
		System.out.println("Test 3: " + Arrays.toString(solution.solution(arr3))); // [7, 8, 9, 7]
	}

	public int[] solution(int[] arr) {
		// 결과를 저장할 배열
		int[] answer;

		// 스택을 생성 (스택을 이용해 중복된 숫자를 제거할 것임)
		Stack<Integer> st = new Stack<>();

		// 배열의 첫 번째 값은 스택에 넣음
		if (arr.length > 0) {
			st.add(arr[0]);
		}

		// 배열을 순차적으로 탐색하며 스택의 가장 위 값과 비교
		for (int i = 1; i < arr.length; i++) {
			// 스택의 가장 위 값과 현재 값이 다르면 스택에 추가
			if (st.peek() != arr[i])
				st.push(arr[i]);
		}

		// 스택의 크기만큼 answer 배열 생성
		answer = new int[st.size()];

		// 스택의 값을 하나씩 꺼내어 answer 배열에 저장 (스택의 순서가 반대이므로 역순으로 넣음)
		for (int i = st.size() - 1; i >= 0; i--) {
			answer[i] = st.pop();
		}

		// 결과 배열 반환
		return answer;
	}
}

[프로그래머스] (Java) 같은 숫자는 싫어 문제 풀이 (스택/큐)

 

예제 4 - 히스토그램에서 가장 큰 직사각형의 찾기 (rectangularArea.java)

주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하세요.
히스토그램은 heights[i]로 표현되며, 각 값은 해당 위치의 막대 높이를 나타냅니다.

 

제한 조건

• 입력: 배열 길이: 1 ≤ heights.length ≤ 100,000
• 각 막대의 높이: 0 ≤ heights[i] ≤ 10^9
• 시간: 복잡도 제한 O(N) (최대 O(N log N) 가능)
• 출력: 가장 큰 직사각형의 넓이 (정수)

 

입출력 예

입력 (heights)	출력 (가장 큰 직사각형의 넓이)
[2, 1, 5, 6, 2, 3]	10
[1, 2, 3, 4, 5]	9
[5, 5, 5, 5]	20
[2, 4]	4

 

요점

• 높이가 증가하는 인덱스를 모노토닉 스택에 저장한다. 현재 높이가 이전보다 작아지는 순간 직사각형의 최대 넓이를 계산하고, 스택에서 높이를 하나씩 꺼내며 heights[stack.pop()]을 기준으로 넓이를 계산한다.
• 너비: 현재 인덱스 - 스택의 최상단 인덱스 - 1

 

소스 코드

package algo03.StackAndQueue;

import java.util.Stack;

public class stack_rectangularArea {

	public static void main(String[] args) {
		int[] heights = { 2, 1, 5, 6, 2, 3 };
		System.out.println(largestRectangleArea(heights)); // 10
	}

	public static int largestRectangleArea(int[] heights) {
		// 히스토그램에서 직사각형 넓이 구하기
		// 주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제
		// 스택을 사용하여 높이를 추적하면서 넓이를 계산한다.
		Stack<Integer> stack = new Stack<>();
		int maxArea = 0;
		int i = 0;

		while (i < heights.length) {
			if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
				stack.push(i++);
			} else {
				int h = heights[stack.pop()];
				int width = stack.isEmpty() ? i : i - stack.peek() - 1;
				maxArea = Math.max(maxArea, h * width);
			}
		}

		while (!stack.isEmpty()) {
			int h = heights[stack.pop()];
			int width = stack.isEmpty() ? i : i - stack.peek() - 1;
			maxArea = Math.max(maxArea, h * width);
		}
		return maxArea;
	}
}

 

 

예제 5 - 후위 표기법(Reverse Polish Notation, RPN) 계산기 (reversePolish.java)

주어진 후위 표기법(Reverse Polish Notation, RPN) 수식을 계산하세요.
후위 표기법은 연산자가 피연산자 뒤에 위치하는 표기법입니다.
예를 들어, **"2 1 + 3 *"**는 **"(2 + 1) * 3"**과 같은 의미이며, 결과는 9입니다.
주어진 연산은 더하기(+), 빼기(-), 곱하기(*), 나누기(/) 네 가지입니다.
나눗셈은 정수 나눗셈을 의미하며, 소수점 이하를 버립니다.

 

제한 조건

• 입력 배열 크기: 1 ≤ tokens.length ≤ 10^4
• 토큰 값: 숫자 또는 "+", "-", "*", "/" 중 하나
• 숫자 범위: -200 ≤ tokens[i] ≤ 200
• 연산 결과: 범위 int 범위를 벗어나지 않음
• 출력: 후위 표기법의 계산 결과 (정수)

 

입출력 예

입력(token)	출력 (계산결과)
["2", "1", "+", "3", "*"]	9
["4", "13" , "5", "/", "+"]	6
["10", "6", "9", "3", "/", "*", "-"]	4

 

요점

• 숫자는 스택에 push한다. 연산자가 나오면 스택에서 두 개를 pop 후 연산하여 다시 push한다. 모든 연산을 처리한 후, 최종 결과를 pop해서 반환한다. O(N) 시간복잡도로 해결 가능하다. 

소스 코드

package algo03.StackAndQueue;

import java.util.Stack;

public class stack_reversePolish {

	public static void main(String[] args) {
		String[] tokens = { "2", "1", "+", "3", "*" };
		System.out.println(evalRPN(tokens)); // 9
	}

	public static int evalRPN(String[] tokens) {
		// 리버스 Polish 표기법 (후위 표기법)
		// 후위 표기법을 사용하여 수식을 계산하는 문제
		// 스택을 사용하여 연산자와 피연산자를 처리
		Stack<Integer> stack = new Stack<>();
		for (String token : tokens) {
			if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
				int b = stack.pop();
				int a = stack.pop();
				switch (token) {
				case "+":
					stack.push(a + b);
					break;
				case "-":
					stack.push(a - b);
					break;
				case "*":
					stack.push(a * b);
					break;
				case "/":
					stack.push(a / b);
					break;
				}
			} else {
				stack.push(Integer.parseInt(token));
			}
		}
		return stack.pop();
	}
}

 

 

예제 6 - 주식 가격 (stockPrices.java)

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

 

제한 조건

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

 

입출력 예

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

요점

• 주가가 유지되거나 증가하면 인덱스를 스택에 push한다. 모노토닉 스택(감소하는 스택)에 (인덱스)를 저장해서 가격이 떨어지는 순간 스택에서 값을 꺼내며경과 시간을 계산한다. 
• 현재 인덱스 - 스택에서 pop한 인덱스 = 가격이 유지된 기간
• 모든 가격을 순회한 후, 스택에 남아 있는 값 처리
• 끝까지 떨어지지 않은 가격들은 배열의 끝까지 유지된 것으로 간주
• 시간복잡도: O(N) (각 요소가 최대 1번 push, 1번 pop됨)

 

소스 코드

package algo03.StackAndQueue;

public class stack_stockPrices {

    public static void main(String[] args) {
        // 프로그래머스 주식가격 문제
    	
        int[] prices1 = {1, 2, 3, 2, 3};
        int[] result1 = solution(prices1);
        System.out.print("Test 1: ");
        for (int i : result1) {
            System.out.print(i + " ");
        }
        // 4 3 1 1 0 (각각 가격이 떨어지기까지 걸리는 시간)

        System.out.println();

        int[] prices2 = {5, 3, 6, 7, 4};
        int[] result2 = solution(prices2);
        System.out.print("Test 2: ");
        for (int i : result2) {
            System.out.print(i + " "); // 1 1 2 1 0 (각각 가격이 떨어지기까지 걸리는 시간)
        }
    }

    // prices 배열에 대해, 각 주식 가격이 언제 떨어지는지 구하는 문제
    public static int[] solution(int[] prices) {
        int[] answer = new int[prices.length]; // 결과를 담을 배열

        // 주식 가격 배열을 순회
        for (int i = 0; i < prices.length; i++) {
            // 각 주식 가격에 대해 이후 가격을 순회
            for (int j = i + 1; j < prices.length; j++) {
                answer[i]++; // 주식 가격이 떨어질 때까지 시간 증가
                // 만약 현재 가격이 이후 가격보다 크다면, 주식 가격이 떨어진 것이므로 반복 종료
                if (prices[i] > prices[j]) {
                    break;
                }
            }
        }
        return answer; // 결과 배열 반환
    }
}

[프로그래머스] (Java) 주식가격 (스택/큐)

 

예제 7 - 올바른 괄호 (validParentheses.java)

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

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

 

제한 조건

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

 

입출력 예

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

 

요점

• 괄호가 열릴 때마다 스택에 넣고, 닫힌 괄호가 나오면 스택의 최상단 요소를 꺼내 짝이 맞는지 확인하며, 모든 괄호가 올바르게 짝지어졌는지 검사하는 방식으로 풀이한다.

 

소스 코드

package algo03.StackAndQueue;

import java.util.Stack;

public class stack_validParentheses {

	public static void main(String[] args) {
		// 프로그래머스 올바른 괄호 문제
		stack_validParentheses solution = new stack_validParentheses();

		// 테스트 코드
		System.out.println(solution.solution("()()")); // true
		System.out.println(solution.solution("(()")); // false
		System.out.println(solution.solution("())")); // false
		System.out.println(solution.solution("(())()"));// true
		System.out.println(solution.solution("")); // true
	}

	// 괄호의 짝이 맞는지 확인하는 함수
	boolean solution(String s) {
		// 열린 괄호를 추적할 스택 생성
		Stack<Character> cnt = new Stack<>();

		// 문자열의 각 문자에 대해 반복
		for (int i = 0; i < s.length(); i++) {
			// 열린 괄호 '('를 만나면 스택에 푸시
			if (s.charAt(i) == '(') {
				cnt.push('(');
			}
			// 닫힌 괄호 ')'를 만나면
			else if (s.charAt(i) == ')') {
				// 스택이 비어있으면 짝이 맞지 않으므로 false 반환
				if (cnt.isEmpty()) {
					return false;
				}
				// 스택에서 열린 괄호 '('를 pop
				cnt.pop();
			}
		}

		// 스택이 비어있으면 모든 괄호가 짝을 맞춘 것이므로 true 반환, 아니면 false
		return cnt.isEmpty();
	}

}

[프로그래머스] (Java) 올바른 괄호 문제풀이 (스택/큐)

 

스택 예제를 풀어본 후

스택 관련 코딩테스트 문제를 풀면서, 단순한 자료구조지만 문제 유형이 다양하고 활용 범위가 넓다는 점이 흥미로웠다.  특히 괄호 검사, 최소값 유지, 히스토그램 최대 직사각형, 주식 가격 문제 등에서 모노토닉 스택이나 보조 스택을 활용하는 방식이 인상적이었다. 또한, 스택과 반대되는 구조를 가진 큐(Queue) 도 함께 공부하면 문제 해결의 폭이 넓어질 것 같다고 느꼈다.

 

스택에는 모노토닉 스택과 보조스택이 있다. 

 

모노토닉 스택(Monotonic Stack)은 값이 정렬된 상태, 즉 오름차순 또는 내림차순 형태를 유지하는 스택이다. 이 구조는 주식 가격 문제, 히스토그램 최대 직사각형 문제, 다음 큰 수 찾기 문제와 같은 문제에서 유용하게 사용된다. 예를 들어, 주식 가격 문제에서는 가격이 떨어지는 순간까지 인덱스를 스택에 저장하여 유지 기간을 계산하거나, 히스토그램 문제에서는 높이가 낮아지는 순간 넓이를 계산한다. 이처럼 모노토닉 스택은 값을 비교하여 조건을 만족하는 순간 적절한 처리를 하며, 특정 패턴을 빠르게 찾아내는 데 도움을 준다.

 

반대로 최소값, 최대값을 구하는 문제에서는 보조스택(Auxiliary Stack)을 사용한다. 보조스택은 기존 스택과 함께 사용하여 특정 값을 추적하는 데 쓰인다. 주로 최솟값이나 최댓값을 추적할 때 활용되며, 최소값을 저장하는 보조 스택을 유지하면 pop 연산을 할 때도 O(1) 시간 안에 최소값을 구할 수 있다. 이 방식은 스택에서 가장 큰 값이나 작은 값을 빠르게 참조할 수 있게 해 주며, 스택 연산을 효율적으로 관리할 수 있게 돕는다. 보조 스택은 기존 스택의 데이터를 유지하면서 특정 정보를 추가로 저장하고 빠르게 반환할 수 있도록 하는 데 중요한 역할을 한다.

 

스택 문제들은 대체로 쉬운 편에 속한다고 생각 되었고, 스택을 구현하는 방식에는 배열로 구현하는 것과 linked list로 구현하는 것이 있는데 배열로 구현하는 문제만 나오는 편이다. 

 

GitHub: https://github.com/awesomepossumgirl/Algorithm/tree/main/src/algo03/StackAndQueue

문제 출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/parts/12081

---

[자료구조] 스택에 대해서 정리가 잘 된 블로그들

 

✅ 스택 일반

[자료구조] | 스택(Stack)

[자료구조] 스택(Stack)과 큐(Queue)에 대해서 알아보자!

✅ 스택과 재귀호출 (파이썬)

1-4. [자료구조이론] 스택(Stack)

✅ 이건 자료를 조사하다가 흥미로운 내용이라서 가져왔다.  

자바의 Stack 클래스는 왜 사용하지 않는 걸까?

✅ 배열(Array)과 연결리스트(LinkedList)를 이용한 스택 구현 비교

[자료구조] 스택(Stack) 자료구조 알아보기 & Java 예제 코드

✅ 스택(Stack) VS 큐(Queue) VS 덱(Deque)

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시

[자료구조] 2. 스택(Stack)과 큐(Queue), 덱(Deque)

'Stack vs Queue' & 'LIFO(후입선출) vs FIFO(선입선출)'