삭제, 삽입시 맨 위에 데이터를 삽입, 삭제하기 때문에 시간복잡도는 늘 O(1) 이다. 하지만, 특정 데이터를 찾을 때는 특정 데이터까지 탐색 하므로, O(n) 의 시간 복잡도를 가진다.
문제 : 포스택 (백준 25556번)
포닉스는 길이가 인 순열 와 네 개의 비어 있는 스택을 가지고 있다.
길이가 인 순열이란, 이상 이하의 서로 다른 정수 개가 임의로 나열된 수열을 말한다.
스택이란 자료구조의 한 종류로 가장 나중에 삽입한 자료가 가장 먼저 나오는 후입선출 (Last In First Out, LIFO)의 특성을 가지고 있다.
포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다.
순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 즉 순열을 으로 만들어야 한다.
순열 의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
순열 의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.
포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자.
입력
첫째 줄에 순열의 길이 이 주어진다.
둘째 줄에 순열 의 원소 가 공백으로 구분되어 주어진다. 모든 는 이상 이하의 서로 다른 정수임이 보장된다.
예제 입력 1
10
4 3 6 7 8 9 10 2 1 5
예제 출력 1
YES
예제 입력 2
5
5 4 3 2 1
예제 출력 2
NO
import java.util.*;
public class Main {
public static void main(String[] args) {
// 스택을 리스트에 담아 관리하면 쉽게 구현할 수 있다고 생각했다.
List<Stack<Integer>> stackList = new ArrayList<>();
// 입력 받기
Scanner in = new Scanner(System.in);
int n = in.nextInt();
ArrayList<Integer> list = new ArrayList<>();
for(int i=0;i<n;i++)
{
list.add(in.nextInt());
}
// 처음 들어갈 숫자는 비교대상이 필요하다.
// 문제조건 : '들어올 숫자는 1 이상 N 이하의 서로 다른 정수임이 보장된다'
// 4개의 스택에 미리 0을 넣어주고, 스택을 리스트에 담는다.
for(int i=0;i<4;i++)
{
Stack<Integer> stack = new Stack<>();
stack.add(0);
stackList.add(i,stack);
}
// solution함수가 true이면 YES, false이면 NO를 출력
if(solution(stackList,list))
System.out.println("YES");
else
System.out.println("NO");
}
//solution함수 : stack이 담긴 list와, 숫자를 입력받은 list를 받아온다.
public static boolean solution(List<Stack<Integer>> stackList,ArrayList<Integer> list)
{
for(Integer num:list)
{
int cnt=0; // count 0으로 초기화
for(int j=0;j<4;j++)
{
if(stackList.get(j).peek()<num) // 0~4번째 스택에 들어갈수 있을 때
{
stackList.get(j).push(num); //해당 스택에 숫자를 push한다.
break;
}
else cnt++; //들어가지 못했다면 count += 1
}
if(cnt==4) // 4개의 스택에서 거절당했을 때
{
return false; // false를 리턴한다.
}
}
return true; // 위 조건을 통과했다면 true를 리턴한다.
}
}
import java.io.*;
import java.util.*;
import java.util.stream.Stream;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int a=Integer.parseInt(bf.readLine());
Integer[] stack=new Integer[4];
for(int i=0; i<4; i++) stack[i]=0;
String[] numbers = bf.readLine().split(" ");
boolean flag=true;
for(int num: Stream.of(numbers).mapToInt(Integer::parseInt).toArray()){
boolean cond=false;
for(int j=0; j<4; j++){
if(stack[j]<num){
stack[j]=num;
cond=true;
break;
}
}
if(!cond){
flag=false;
break;
}
Arrays.sort(stack,Comparator.reverseOrder());
//가장 큰수부터 비교하게끔 배열 정렬 !!!
}
System.out.println(flag?"YES":"NO");
}
}
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<Integer> list = new ArrayList<>(n);
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
// 초기 스택 생성
List<Stack<Integer>> stackList = IntStream.range(0, 4)
.mapToObj(i -> new Stack<Integer>() {{
push(0);
}})
.collect(Collectors.toList());
// solution 함수
boolean result = list.stream()
.map(num -> {
int cnt = 0;
for (Stack<Integer> stack : stackList) {
if (stack.peek() < num) {
stack.push(num);
break;
} else {
cnt++;
}
}
return cnt;
})
.noneMatch(cnt -> cnt == 4);
System.out.println(result ? "YES" : "NO");
}
}