[COS Pro 1급 JAVA 모의고사] 스택으로 큐 구현(빈칸 채우기)
문제 설명
스택 두 개를 이용해 Queue 자료구조를 만들었을 때, Queue 자료 구조의 pop(또는 dequeue) 메소드를 구현하려 합니다. Queue란 먼저 삽입한 데이터를 먼저 빼내는 자료구조를 뜻합니다. pop 메소드를 만들기 위해 다음과 같이 프로그램 구조를 작성했습니다.
1. 스택2가 비었다면 스택1에 아무것도 남지 않을때까지 스택1에서 pop한 값을 스택2에 push 한다.
2. 스택2에서 pop한 값을 리턴한다.
두 어레이리스트 stack1, stack2가 매개변수로 주어질 때, 두 어레이리스트를 스택으로 이용해 Queue 자료 구조의 pop 메소드를 구현하려 합니다. 위 구조를 참고하여 코드가 올바르게 동작할 수 있도록 빈칸에 주어진 func_a, func_b, func_c 메소드와 매개변수를 알맞게 채워주세요.
※ 어레이리스트 index가 0인 부분을 스택의 bottom으로 생각합니다.
매개변수 설명
두 어레이리스트 stack1와 stack2가 solution 메소드의 매개변수로 주어집니다.
- stack1과 stack2는 길이가 0 이상 10 이하입니다.
- stack1과 stack2의 길이가 모두 0인 경우는 주어지지 않습니다.
- stack1과 stack2의 원소는 100 이하인 정수입니다.
return 값 설명
stack1과 stack2로 구현한 큐에서 pop(또는 dequeue)한 값을 return 해주세요.
예제
| stack1 | stack2 | result |
| [1, 2] | [3, 4] | 4 |
| [1, 2, 3] | [] | 1 |
예제 설명
예제 #1
stack2가 비지 않았으므로 stack2에서 pop 한 결과인 4를 리턴합니다.
예제 #2
- stack2가 비었으므로 stack1의 원소를 전부 pop해 stack2로 넣습니다. 이 결과 stack2에는 [3,2,1]이 들어갑니다.
- stack2에서 pop한 결과인 1을 리턴합니다.
소스 코드
문제 풀이
빈칸이 없는 함수부터 살펴보면
func_a의 기능을 살펴보면 매개변수로 ArrayList(스택)를 받아 크기를 하나씩 줄이면서 값을 반환한다.
func_c의 기능은 ArrayList의 사이즈가 0이어야 참값을 반환한다.
이를 통해 func_b를 유추해보면 스택을 다른 스택에 pop 해주는 기능일 것이다.
그러므로 while 문에는 func_c가 들어가야 하며 매개변수는 문제의 조건에 따라 stack1을 stack2에 옮겨 닮아야 하니 stack1이 들어갈 것이다.
마찬가지로 stack2에 stack1의 값을 담아주기 위해 func_a함수를 stack1을 매개변수로 주어 실행한다.
void func_b(ArrayList<Integer> stack1, ArrayList<Integer> stack2) {
while(!func_c(stack1)) {
Integer item = func_a(stack1);
stack2.add(item);
}
}
다음은 solution의 기능을 완성하기 위해 로직을 고민해보자.
스택2가 비었을 때는 스택1을 스택2로 pop 해줘야 하고 스택2가 비어있지 않을 경우 바로 pop 해주면 된다.
그러므로 함수를 완성하기 위해서는 스택2가 비어있지 않으면 stack1을 stack2로 pop 해 줘야 하고 이후 stack2의 값을 pop 해주면 된다.
public int solution(ArrayList<Integer> stack1, ArrayList<Integer> stack2) {
if(func_c(stack2)) {
func_b(stack1, stack2);
}
Integer answer = (int)func_a(stack2);
return answer;
}