Stack

백준 포스택

• 포닉스는 길이가
  $N$인 순열
  $A$와 네 개의 비어 있는 스택을 가지고 있다.

길이가
$N$인 순열이란,
$1$ 이상
$N$ 이하의 서로 다른 정수
$N$개가 임의로 나열된 수열을 말한다.
스택이란 자료구조의 한 종류로 가장 나중에 삽입한 자료가 가장 먼저 나오는 후입선출 (Last In First Out, LIFO)의 특성을 가지고 있다.
포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다.

순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 즉 순열을
$1, 2, 3, \cdots N$으로 만들어야 한다.

순열
$A$의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
순열
$A$의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.
포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

  public static boolean canCleanPernutation(String str) {
    Stack<Integer>[] st = new Stack[4];
    boolean flag = true;
    for (int i = 0; i < st.length; i++) {
      st[i] = new Stack<>();
      st[i].push(0);
    }

    for (String s : str.split(" ")) {
      Integer num = Integer.parseInt(s);
      int idx = 0;
      while (idx < 4) {
        if (st[idx].peek() < num) {
          st[idx].push(num);
          flag = true;
          break;
        } else {
          flag = false;
          idx++;
        }
      }
      if (idx == 4) {
        if (flag == false)
          break;
      }
    }
    return flag;
  }

  public static void main(String[] args) {
    try {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      String str = br.readLine();
      boolean result = canCleanPernutation(str);
      if (result) {
        System.out.println("YES");
      } else
        System.out.println("NO");

    } catch (Exception e) {
      e.printStackTrace();
    }

  }


}

프로그래머스 같은 숫자는 싫어

• 배열 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 함수를 완성해 주세요.

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        Stack<Integer> st = new Stack<>();
        st.push(arr[0]);
        
        for (int i=1; i<arr.length; i++){
            if(arr[i]==st.peek())
                continue;
            else
                st.push(arr[i]);
        }
        
        int[] answer = new int[st.size()];
        for(int i=st.size()-1; i>=0; i--){
            answer[i] = st.pop();
        }
        

        return answer;
    }
}

TIL

• for(int s:st){
  // 가능
  }