[백준] 스택으로 오름차순 수열 만들기

---

백준 온라인 저지 1874번 - 스택으로 오름차순 수열 만들기

스택 자료구조를 사용하여 백준 알고리즘 문제를 해결해보았다.

StackAsc.java

package com.example.Etc;

import java.util.Stack;

/**
 * 스택으로 오름차순 수열 만들기
 * 오름차순을 만들 수 있는 경우 push(+), pop(-)의 순서를 리턴
 * 오름차순을 만들 수 없는 경우 "No"를 리턴 
 */
public class StackAsc {
    public String ascSortStack(int[] sequence) {
        Stack<Integer> stack = new Stack<>();
        int num = 1;
        StringBuffer bf = new StringBuffer();
        for(int i = 0; i < sequence.length; i++) {
            int su = sequence[i]; // 배열에서 i 인덱스의 값 대입
            if(su >= num) { // 수가 스택에 오름차순으로 쌓을 자연수보다 클 경우
                while (su >= num) { // 스택에 계속 push
                    stack.push(num++);
                    bf.append("+");
                }
                stack.pop();
                bf.append("-"); 
            } else {
                int n = stack.pop();
                if(n > su) { // pop연산으로 추출한 값이 여전히 큰 경우 더이상 스택을 오름차순 정렬할 수 없기 때문에 로직 종료(스택은 후입선출 구조)
                    return "No";
                } else {
                    bf.append("-");
                }
            }
        }
        return bf.toString();
    }
}

StackAscTest.java

package com.example.Etc;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class StackAscTest {
    @Test
    public void stackAscTest() {

        StackAsc stackAsc = new StackAsc();
        int[] sortableSeq = {4, 3, 6, 8, 7, 5, 2, 1}; // 정상 출력 케이스 수열에 해당
        int[] unsortableSeq = {5, 1, 2, 5, 3, 4}; // 오름차순 출력 실패 케이스 수열에 해당
        String result1 = stackAsc.ascSortStack(sortableSeq);
        String result2 = stackAsc.ascSortStack(unsortableSeq);

        assertEquals("++++--++-++-----", result1);
        assertEquals("No", result2);
    }
}

스택과 큐