Java Coding Test Course, Creating Ascending Sequences with Stacks

Problem Description

Write a program that arranges the numbers from 1 to N in ascending order using a stack for the given integer N. You can push numbers onto the stack if needed before outputting the sequence, and you can pop numbers to output them. However, if you cannot output the numbers in the given order, you must print ‘NO’.

Input Format

  • The first line contains the integer N. (1 ≤ N ≤ 100,000)
  • The next N lines each contain a number that needs to be output. This number is an integer between 1 and N.

Output Format

  • If it is possible to output the given numbers in ascending order, print each number in sequence.
  • If it is not possible, print ‘NO’.

Example Input

    4
    4
    3
    2
    1

Example Output

    YES
    PUSH
    PUSH
    PUSH
    PUSH
    POP
    POP
    POP
    POP

Explanation

To solve the problem, you need to manipulate the numbers using a stack data structure appropriately. The basic idea is as follows:

  1. Push the numbers from 1 to N onto the stack sequentially.
  2. Pop each number from the sequence to output. At this time, the top value of the stack must match the desired output value.
  3. If the top value of the stack does not match, it becomes impossible to output any number, and you must print ‘NO’.

Implementation Steps

Below is a Java code snippet to solve the problem:

    import java.util.*;

    public class StackSequence {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int N = scanner.nextInt();
            int[] sequence = new int[N];
            for (int i = 0; i < N; i++) {
                sequence[i] = scanner.nextInt();
            }

            Stack stack = new Stack<>();
            StringBuilder output = new StringBuilder();
            int current = 1;
            boolean isPossible = true;

            for (int i = 0; i < N; i++) {
                while (current <= sequence[i]) {
                    stack.push(current++);
                    output.append("PUSH\n");
                }
                if (stack.isEmpty() || stack.peek() != sequence[i]) {
                    isPossible = false;
                    break;
                }
                stack.pop();
                output.append("POP\n");
            }

            if (!isPossible) {
                System.out.println("NO");
            } else {
                System.out.println("YES");
                System.out.print(output);
            }

            scanner.close();
        }
    }

Code Explanation

The above Java code operates in the following way:

  1. Input Reading: It reads N and stores the next N integers in an array.
  2. Stack Initialization: It initializes a stack.
  3. Pushing from 1 to N: It pushes each number onto the stack. During operations, it outputs the string PUSH.
  4. Pop Operation: It checks if the current sequence number matches the top of the stack, and if not, it prints 'NO'.
  5. Result Output: If all numbers are successfully popped, it prints 'YES' along with the PUSH and POP operations.

Time Complexity Analysis

In this problem, since each number is pushed and popped from the stack only once, the overall time complexity is O(N). This is the time required to process the input through the sequence.

Conclusion

In this lecture, we learned how to use the stack data structure to output the given numbers in ascending order. In coding tests, stacks can be a useful tool for solving various problems. They can particularly contribute to the design of efficient algorithms considering memory usage and time complexity.

Through this problem, I hope you understand the characteristics of stacks and how to utilize them in solving algorithmic problems. Furthermore, I encourage you to practice similar problems on your own to discover how to utilize stacks effectively.