문제

BOJ 1874, 스택 수열 [C++, Java]

핵심

• 입력의 크기가 $10^5$이기에 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 문제 이름처럼 스택 수열을 만들어야 한다. 가장 큰 숫자를 저장하는 이유는 이미 pop한 숫자를 중복해서 저장하지 않기 위함이다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
#include <stack>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	stack<int> s;
	string ans = "";
    int n;
	cin >> n;
	int maxNum = 0;
	while (n--) {
		int num; 
		cin >> num;
		for (int i = maxNum + 1; i <= num; ++i) {
			s.push(i);	
			ans += "+\n";
		}
		maxNum = max(maxNum, num);
		if (!s.empty() && s.top() != num) {
            cout << "NO";
			return 0;
		}
		s.pop();
		ans += "-\n";
	}
    cout << ans;
}

Java

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 {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> s = new Stack<>();
        int maxNum = 0;
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            for (int j = maxNum + 1; j <= num; j++) {
                s.push(j);
                sb.append("+\n");
            }
            maxNum = Math.max(maxNum, num);
            if (!s.isEmpty() && s.peek() != num) {
                System.out.println("NO");
                return ;
            }
            s.pop();
            sb.append("-\n");
        }
        System.out.println(sb.toString());
    }
}