정리
| 문제 | 사용 자료구조 | 문제 의도 | 해결 포인트 (구현 관점) | 핵심 포인트 (사고 관점) |
|---|---|---|---|---|
| 10828 스택 | Stack | 스택 기본 동작 구현 | 배열 또는 ArrayList로 스택 직접 구현 | 스택은 마지막 원소만 접근 가능 |
| 10773 제로 | Stack | 입력 취소 처리 | 0 → pop, 그 외 → push | 스택은 히스토리 되돌리기에 최적 |
| 9012 괄호⭐ | Stack | 유효성 검사 | pop 전에 empty 검사 필수 | 괄호 문제는 스택이 비어야 정상 종료 |
| 18258 큐 2 | Queue | 큐 구현 + 시간 최적화 | Deque + LinkedList | 큐는 앞/뒤 접근만 허용 |
| 기능개발 | Queue | 순서 기반 시뮬레이션 | 완료 일수 계산 후 앞 기준으로 묶기 | 큐의 핵심은 순서가 절대 바뀌지 않음 |
코드
10828
package A0study;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class p10828_스택 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Stack<Integer> stack = new Stack<>();
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String order = st.nextToken();
int num = 0;
if(order.equals("push")) {
num = Integer.parseInt(st.nextToken());
}
switch(order) {
case "push":
stack.push(num);
break;
case "pop":
if (stack.empty()) {
System.out.println(-1);
} else {
System.out.println(stack.pop());
}
break;
case "size":
System.out.println(stack.size());
break;
case "empty":
if (stack.empty()) {
System.out.println(1);
} else {
System.out.println(0);
}
break;
case "top":
if (stack.empty()) {
System.out.println(-1);
} else {
System.out.println(stack.peek());
}
break;
default:
System.out.println();
}
}
}
}
10773
package A0study;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class p10773_제로 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int K = Integer.parseInt(br.readLine());
// 0이면 pop, 0이 아니면 push
Stack<Integer> stack = new Stack<>();
for(int i=0; i<K; i++) {
int input = Integer.parseInt(br.readLine());
if(input == 0) {
stack.pop();
} else {
stack.push(input);
}
}
// 총합 구하기
int sum = 0;
for(int num : stack) {
sum += num;
}
System.out.println(sum);
}
}
9012
package A0study;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class p9012_괄호 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
sb.append(isVPS(br.readLine())).append("\n");
}
System.out.println(sb);
}
public static String isVPS(String s) {
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()) {
// 1. '('면 stack에 push
if(c == '(') {
stack.push(c);
} else {
// 2. ')'면, stack이 비었는지 확인 -> 비었으면, "NO"
if(stack.isEmpty()) {
return "NO";
}
// -> 비어있지 않으면, stack에서 pop
stack.pop();
}
}
// 3. stack이 비었는지 확인
return stack.isEmpty() ? "YES" : "NO";
}
}
18258
package A0study;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class p18258_큐2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
Deque<Integer> q = new LinkedList<>(); // fifo
for(int i=0; i<N; i++) {
String[] input = br.readLine().split(" ");
String order = input[0];
switch (order) {
case "push":
q.offer(Integer.parseInt(input[1]));
break;
case "pop":
sb.append(q.isEmpty() ? -1 : q.poll()).append("\n");
break;
case "size":
sb.append(q.size()).append("\n");;
break;
case "empty":
sb.append(q.isEmpty() ? 1 : 0).append("\n");
break;
case "front":
sb.append(q.isEmpty() ? -1 : q.peek()).append("\n");
break;
case "back":
sb.append(q.isEmpty() ? -1 : q.peekLast()).append("\n");
break;
}
}
System.out.print(sb);
}
}
기능개발
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
List<Integer> answer = new ArrayList<>();
Queue<Integer> q = new LinkedList<>();
// 기능별 필요한 일수 계산
for(int i=0; i<progresses.length; i++) {
int days = (int) Math.ceil((100.0 - progresses[i]) / speeds[i]);
q.offer(days);
}
// 배포 가능한 기능 수 계산
while(!q.isEmpty()) {
int day = q.poll();
int count = 1;
while(!q.isEmpty() && q.peek() <= day) {
q.poll();
count++;
}
answer.add(count);
}
return answer.stream().mapToInt(i -> i).toArray();
}
}✔️ answer의 size를 정확히 알 수 없으니, List + ArrayList<> 사용
List<Integer> answer = new ArrayList<>();✔️ 필요한 일수계산시 올림 Math.ceil() 사용
int days = (int) Math.ceil((100.0 - progresses[i]) / speeds[i]);✔️ return 시 stream 사용
return answer.stream().mapToInt(i -> i).toArray();