문제
Stack 자료구조를 활용해 주어진 수열을 정렬할 수 있는지 체크하는 문제이다.
문제에서 주어진 조건을 살펴보면 무작위 순서대로 N 이하의 자연수들이 나열된 것을 살필 수 있다.
이 수들을 4개의 스택을 활용해서 오름차순으로 정렬을 할 수 있는지를 묻는 문제이다.
Stack
Stack 자료구조는 지문에서도 나오지만 후입선출(LIFO)의 특징을 지닌 자료구조이다.
자료를 넣을 땐 Push, 자료를 빼낼 때는 Pop이라는 용어를 사용한다.
Push와 Pop은 O(1)의 성능을 보이기 때문에, 가장 후순위에 있는 값을 빼낼 때 이점이 있는 자료구조이다.
풀이 방법
그렇다면 이 Stack을 사용해서 어떤 식으로 이 문제를 해결해야 할까.
나는 다음과 같이 접근을 해보았다.
어떤 식으로 나와야 하나?
당연하게 10 9 8 7 ... 이런 순으로 pop이 되어야 할 것이다.
그럼 그렇게 pop이 그렇게 나오기 위한 조건은 어떻게 될 까??
가장 Pop이 되는 것이 그 스택에서 가장 큰 수가 되도록 설정을 하는 것이다.
이 생각으로 예제 1번에 대해서 그림을 그려 풀어 보았다.
이런 그림이 그려졌다.
이 그림을 그리면서 2가지 정보를 알았다.
이 그림에서 본 바로는 push를 하기 이전에 stack의 최상단의 값이 넣으려는 값보다 작다면 다른 stack에 넣어야 한다는 것을 알았다.
그리고 모든 수를 스택에 넣을 수 있다면 굳이 빼보지 않더라도 성공한다는 것을 알았다. 규칙에 맞게 넣을 수 있다면 이미 성공했다는 것이기 때문이다.
이 정보들을 가지고 코드로 구현을 하였다.
코드
코드에서는 다음과 같은 변수를 사용했다
int[] arr <- 주어진 수열
Stack[] <- 사용할 4개의 스텍
flag <- 규칙에 맞게 넣지 못하면 실패!
for (int i = 0; i < n; i++) {
int target = arr[i]; // 이번 순서 수열
boolean flag = false;
for(int j = 0; j<4; j++){
if (stacks[j].isEmpty()) { // 스택에 아무것도 없다면 넣기
flag = push(stacks[j], target);
break;
}
Integer peek = (Integer) stacks[j].peek();
if (target > peek) { // 이번 순서 수열이 스택의 최상단보다 크다면 넣
flag = push(stacks[j], target);
break;
}
}
if (!flag) {
System.out.println("NO"); // 규칙 실패 시 NO 출력 후 종료
return;
}
}
System.out.println("YES"); // 규칙이 실패하지 않아서 성공
...
private boolean push(Stack stacks, int target) { // 넣을 수 있다면 규칙 성공
boolean flag = true;
stacks.push(target);
return flag;
}
수열의 순서에 따라서 규칙(각 stack의 peek값 보다 커야 push 가능)을 적용하고 이에 실패하면 프로그램을 종료하도록 하였다.
PS
첫 블로그 게시글이라서 글 솜씨가 많이 부족하네요.
앞으로 공부한 내용 자주 업로드 하며 불편함 없이 읽히는 글 작성하겠습니다~
전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public void solution() throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Stack[] stacks = new Stack[4];
for(int i = 0; i<4; i++)
stacks[i] = new Stack<Integer>();
StringTokenizer st = new StringTokenizer(br.readLine());
int [] arr = new int[n];
int idx = 0;
while(st.hasMoreTokens())
arr[idx++] = Integer.parseInt(st.nextToken());
for (int i = 0; i < n; i++) {
int target = arr[i];
boolean flag = false;
for(int j = 0; j<4; j++){
if (stacks[j].isEmpty()) {
flag = push(stacks[j], target);
break;
}
Integer peek = (Integer) stacks[j].peek();
if (target > peek) {
flag = push(stacks[j], target);
break;
}
}
if (!flag) {
System.out.println("NO");
return;
}
}
System.out.println("YES");
}
private boolean push(Stack stacks, int target) {
boolean flag = true;
stacks.push(target);
return flag;
}
public static void main(String[] args) throws Exception {
new Main().solution();
}
}
