99클럽 코테 스터디 28일차 TIL + 스택 수열

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

문제 & 키워드

• 백준 - 스택 수열 (문제 링크)
• 스택
• 자료구조

 

---

 

문제 설명

스택은 컴퓨터 과학에서 자주 사용되는 자료구조 중 하나로, LIFO(Last In First Out) 원칙에 따라 작동합니다. 즉, 가장 최근에 스택에 추가된 항목이 가장 먼저 제거됩니다.

1부터 n까지의 수를 스택에 넣었다가 뽑아서 하나의 수열을 만들고자 합니다. 스택에 수를 push하는 순서는 오름차순을 지켜야 하며, 주어진 수열을 만들기 위해 필요한 push와 pop 연산을 출력하는 프로그램을 작성해야 합니다. 주어진 수열을 만들 수 없다면 "NO"를 출력해야 합니다.

입력

• 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어집니다.
• 다음 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어집니다.

출력

• 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력합니다.
• push 연산은 +로, pop 연산은 ``로 표현합니다.
• 주어진 수열을 만들 수 없는 경우 "NO"를 출력합니다.

예제 입력

8
4
3
6
8
7
5
2
1

예제 출력

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

 

---

 

문제 접근

이 문제는 스택의 LIFO 특성을 활용하여 주어진 수열을 만들 수 있는지를 판단하고, 그 과정에서의 연산을 기록하는 방식으로 접근합니다.

1. 오름차순으로 스택에 수를 쌓아야 하는 점
   • 현재 숫자가 목표 숫자보다 작으면 계속해서 push하고, 목표 숫자와 같아지면 pop하는 방식으로 구현할 수 있습니다.
2. 불가능한 경우를 처리
   • 스택의 최상단 요소가 목표 숫자와 다르다면 해당 수열은 만들 수 없으므로 "NO"를 출력합니다.

 

풀이 - Java 코드

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

public class Main {

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

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

        int n = sc.nextInt();
        int stackIndex = 1;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();

            while (true) {
                if (stackIndex <= num) {
                    sb.append("+").append("\\\\n");
                    stack.push(stackIndex);
                    stackIndex++;
                } else {
                    if (stack.isEmpty() || stack.peek() != num) {
                        System.out.println("NO");
                        return;
                    }
                    stack.pop();
                    sb.append("-").append("\\\\n");
                    break;
                }
            }
        }
        System.out.println(sb);
        sc.close();
    }
}

풀이 설명

1. 초기 설정
   • stackIndex는 스택에 추가할 수의 값을 나타냅니다. 이 값은 1부터 시작하며, 입력된 수열의 값에 맞춰 증가시킵니다.
2. 루프 및 조건 처리
   • 입력된 수 num을 스택의 최상단 값과 비교합니다.
   • stackIndex가 num보다 작거나 같다면, 해당 값을 스택에 push합니다.
   • 그렇지 않다면 스택에서 값을 pop하며 수열을 맞춥니다.
3. 불가능한 경우 처리
   • 스택의 최상단 값이 목표 숫자와 일치하지 않으면 "NO"를 출력하고 프로그램을 종료합니다.
4. 결과 출력
   • StringBuilder에 연산 결과를 모아 한 번에 출력하여 성능을 최적화합니다.

 

---

 

마무리하며

• 이 문제는 스택 자료구조의 기초적인 사용법을 익힐 수 있었습니다.
• 주어진 조건에 맞는 수열을 만드는 과정을 통해 LIFO 원칙을 잘 이해할 수 있습니다.