1. 스택(Stack)
1 - 1. 스택이란?
- "쌓다", 데이터를 차곡차곡 쌓아 올린 형태의 자료구조를 말합니다
- 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있습니다.
- 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 LIFO(Last In First Out) 구조
- 가장 최근에 스택에 삽입된 자료의 위치를 top이라고 합니다.
- 활용 예시
- 웹 브라우저 뒤로가기
- 실행 취소(Ctrl + z)
- 역순 문자열 만들기
- 후위 표기법 계산
- 수식의 괄호 검사(연산자 우선순위 표현을 위한 괄호 검사)
1 - 2. 자바에서의 스택
자바에서의 스택은 Stack 클래스를 구현하여 제공하고 있습니다.
Stack st = new Stack();
Stack의 메서드
- boolean empty() : Stack이 비어있는지 확인
- Object peek()
- Stack의 맨 위에 저장된 객체를 반환
- pop()과 달리 Stack에서 객체를 꺼내지 않음
- 비었을 때는 EmptyStackException 반환
- Object pop()
- Stack의 맨 위에 저장된 객체를 꺼냄
- 비었을 때는 EmptyStackException 반환
- Object push(Object item) : Stack에 객체(item)을 저장
- int search(Object o)
- Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환
- 못 찾으면 -1 반환(배열과 달리 위치가 1부터 시작)
1 - 3. 코딩테스트 스택 문제
[ 예시 문제 1 - 겹쳐진 압축 해제 ]
왜 스택 문제 인가?
=> 문자열의 압축을 해제하는 과정에서 괄호 안의 문자열이 중첩될 수 있다.
- 닫는 괄호 ')'를 만날때 까지 스택에 저장
- 만나면 스택에서 이전의 반복 횟수와 문자열을 꺼내와 현재 반복 횟수와 함께 해당 문자열을 반복해 스택에 다시 저장
[ 코드 ]
import java.util.*;
class Solution {
public String solution(String s){
String answer = "";
Stack<String> st = new Stack<>(); // 문자열을 담는 스택
for (char c : s.toCharArray()) {
if(c == ')') { //닫는 괄호를 만나면
String tmp = "";
while (!st.empty()) { //반복
String t = st.pop(); //pop()으로 꺼냄
if(t.equals("(")) { //여는 괄호 만날 때까지 꺼내서 저장 tmp에 저장
String num = "";
// 몇번 반복할 것인가? -> 여는 괄호 앞에 숫자 ->3(2(ac)) 이런식 으로도 받을 수 있어서 while로 반복
while (!st.empty() && Character.isDigit(st.peek().charAt(0))) {
num = st.pop() + num;
}
// 반복횟수 -> int로 변경
int cnt = 0;
if(num.equals("")) cnt = 1;
else cnt = Integer.parseInt(num);
String res = "";
for (int i = 0; i < cnt; i++) {
res += tmp;
}
st.push(res);
break; //종료하고 다시 닫는 괄호 만날 때까지 stack에 추가
} else {
tmp = t + tmp;
}
}
} else {
st.push(String.valueOf(c));
}
}
for(String x : st) {
answer += x;
}
return answer;
}
public static void main(String[] args){
Solution T = new Solution();
System.out.println(T.solution("3(a2(b))ef"));
System.out.println(T.solution("2(ab)k3(bc)"));
System.out.println(T.solution("2(ab3((cd)))"));
System.out.println(T.solution("2(2(ab)3(2(ac)))"));
System.out.println(T.solution("3(ab2(sg))"));
}
}
[ 결과 ]
abbabbabbef
ababkbcbcbc
abcdcdcdabcdcdcd
ababacacacacacacababacacacacacac
absgsgabsgsgabsgsg
[ 예시 문제 2 - 좋은 단어 ]
뒤에 들어온 문자를 체크해서 제거 해야한다.
3가지 케이스
- AABB : 교차안됨
- 스택 작업 : A -> AA(삭제) -> B -> BB(삭제) -> empty
- ABAB : 교차됨
- 스택 작업 : A -> AB -> ABA -> ABAB -> not empty
- ABBA : 교차안됨
- 스택 작업 : A -> AB -> ABB(삭제) -> AA(삭제) -> empty
따라서, 문자열을 계속해서 넣었을때 ABA나 BAB와 같이 삭제가 안되고 비어있지 않으면 좋은 단어가 없는 문자열이다.
[ 코드 ]
import java.util.*;
import java.io.*;
public class Main {
static int count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//logic
int t = Integer.parseInt(br.readLine());
count = 0;
for (int i = 0; i < t; i++) {
String s = br.readLine();
logic(s);
}
System.out.print(count);
}
static void logic(String s) {
//문자열의 길이가 홀수이다는 것은 A 또는 B의 개수가 홀수이므로 좋은단어가 아니다
if (s.length() % 2 == 1) return;
Stack<Character> stack = new Stack<>();
stack.push(s.charAt(0)); //첫 단어는 스택에 push
for (int i = 1; i < s.length(); i++) {
if (stack.size() > 0 && stack.peek() == s.charAt(i)) {
stack.pop();
} else {
stack.push(s.charAt(i));
}
}
if (stack.isEmpty()) count++;
}
}
2. 큐(Queue)
2 - 1. 큐란?
- 양쪽 끝에서 데이터의 삽입과 삭제가 각각 이루어지는 자료구조
- 먼저 들어온 것이 먼저 나가는 선입선출 FIFO(First In First Out)
- 데이터가 삽입되는 곳을 rear, 데이터가 제거되는 곳을 front
- 데이터를 삭제하기 전에는 큐가 empty 한지, 큐에 데이터를 추가하려 할 때는 큐가 full 인지 확인 후 진행해야 합니다.
- 활용 예시 - 입력된 시간 순서대로 처리해야 할 때
- 은행 업무
- 우선순위가 같은 작업 예약
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 캐시(Cache) 구현
2 - 2. 자바에서의 큐
자바에서의 큐는 인터페이스로만 정의해놓았을 뿐 별도의 클래스를 제공하고 있지 않습니다.
따라서 Queue 클래스 인스턴스를 생성하기 위해 Queue의 인터페이스 구현제인 LinkedList() 생성자를 호출해줍니다.
Queue q = new LinkedList();
Queue의 메서드
- boolean add(Object o)
- 지정된 객체를 Queue에 추가
- 성공하면 true 반환, 저장공간이 부족하면 IllegalstateException 발생
- boolean offer(Object o)
- Queue 에 객체를 저장
- 성공하면 true, 실패하면 false 반환
- Object element()
- 삭제없이 요소를 읽어옴
- pee()k와 달리 Queue가 비었을 때 NoSuchElementException 발생
- Object peek()
- 삭제없이 요소를 읽어옴
- Queue 가 비어있으면 null을 반환
- Object poll()
- Queue 에서 객체를 꺼내서 반환
- 비어있으면 null을 반환
- Object remove()
- Queue 에서 객체를 꺼내서 반환
- 비어잇으면 NoSuchElementException 발생
1 - 3. 코딩테스트 큐 문제
[ 예시 문제 1 - 현관문 출입순서 ]
왜 큐 문제 인가?
=> 들어온 순서대로 하나씩 꺼내서 처리하므로 FIFO인 큐를 사용해야한다
[ 코드 ]
package section03.problem03;
import java.util.*;
class Solution {
public int[] solution(int[] arrival, int[] state){
Queue<Integer> enter = new LinkedList<>();
Queue<Integer> exit = new LinkedList<>();
int n = arrival.length, prev = 1;
int[] answer = new int[n];
for (int t = 0, i = 0, cnt =0; ; t++) {
if(enter.isEmpty() && exit.isEmpty() && i < n) {
// t초에 사용하는 사원이 없다.
if(t < arrival[i]) {
t = arrival[i];
prev = 1;
}
}
while (i < n && arrival[i] <= t) {
if (state[i] == 0) enter.offer(i);
else exit.offer(i);
i++;
}
if(prev == 1) {
if(!exit.isEmpty()) {
answer[exit.poll()] = t;
prev = 1;
} else {
answer[enter.poll()] = t;
prev = 0;
}
} else if (prev == 0) {
if(!enter.isEmpty()) {
answer[enter.poll()] = t;
prev = 0;
} else {
answer[exit.poll()] = t;
prev = 1;
}
}
cnt++;
if(cnt==n) break;;
}
return answer;
}
public static void main(String[] args){
Solution T = new Solution();
/**
* 0초 : 0번 사원 나감
* 1초 : 1초 전에 0번 사원이 나갔기 때문에 -> 나가는 사원이 나감 -> 1초에 나가는 사원 3번
* 2초 : 1초 전에 3번 사원이 나갔기 때문에 -> 나가는 사원이 나감 -> 2초에 나가는 사원 없음 -> 1번 사원 들어옴
* 3초 : 1초 전에 1번 사원이 들어옴 -> 들어오는 사원 -> 2번 사원 들어옴
* 4초 : 1초 전에 2번 사원 들어옴 -> 들어오는 사원 -> 4번 사원 들어옴
* 5초 : 1초 전에 4번 사원 들어옴 -> 들어오는 사원 -> 5번 사원 들어옴
* 6초 : 1초 전에 5번 사원 들어옴 -> 들어오는 사원 -> 없음 -> 나가는 사원 없음 -> 이용 안함
* 7초 : 나가는 사원 없음
* 8초 6번 나가고 9초 7번 들어옴
*/
System.out.println(Arrays.toString(T.solution(new int[]{0, 1, 1, 1, 2, 3, 8, 8}, new int[]{1, 0, 0, 1, 0, 0, 1, 0})));
System.out.println(Arrays.toString(T.solution(new int[]{3, 3, 4, 5, 5, 5}, new int[]{1, 0, 1, 0, 1, 0})));
System.out.println(Arrays.toString(T.solution(new int[]{2, 2, 2, 3, 4, 8, 8, 9, 10, 10}, new int[]{1, 0, 0, 0, 1, 1, 0, 1, 1, 0})));
}
}
[ 결과 ]
[0, 2, 3, 1, 4, 5, 8, 9]
[3, 6, 4, 7, 5, 8]
[2, 3, 4, 5, 6, 8, 11, 9, 10, 12]
[ 예시 문제 2 - 피부과 대기열 ]
왜 큐 문제 인가?
=> 들어온 순서대로 하나씩 꺼내서 처리하므로 FIFO인 큐를 사용해야한다
[ 코드 ]
import java.util.*;
class Solution {
// 1. 문자열로 들어온 시간을 숫자로 변경하는 메소드
public int getTime(String time){
int H = Integer.parseInt(time.split(":")[0]);
int M = Integer.parseInt(time.split(":")[1]);
return H*60+M;
}
public int solution(int[] laser, String[] enter){
int answer = 0;
int n = enter.length;
// 2. enter(고객) -> 시간(int) / 시술 번호 리스트로 변경
int[][] inList = new int[n][2];
for (int i = 0; i < n; i++) {
inList[i][0] = getTime(enter[i].split(" ")[0]);
inList[i][1] = Integer.parseInt(enter[i].split(" ")[1]);
}
/**
* 시뮬레이션
*/
Queue<Integer> q = new LinkedList<>(); //대기열
// 첫 손님
q.offer(inList[0][1]);
int finishTime = inList[0][0];
int pos = 1;
for (int t = finishTime; t < 1200; t++) { //1200초(20시 까지) 시뮬레이션
if (pos < n && t == inList[pos][0]) { // 고객이 오는 시간이 됬을 때
if (q.isEmpty() && inList[pos][0] > finishTime) {
// 만약 대기열이 없다면 finishTime변경하여 아래 로직이 바로 실행되게함
finishTime = inList[pos][0];
}
// 일단 대기열에 고객 추가
q.offer(inList[pos][1]);
pos++;
}
if (t == finishTime && !q.isEmpty()) { // 시술이 끝난 시간인데 대기열이 비어있지않다면
// 대기열에서 꺼내서 시술 완료 시간 변경
finishTime += laser[q.poll()];
}
// 대기열 최대값 갱신
answer = Math.max(answer, q.size());
}
return answer;
}
public static void main(String[] args){
Solution T = new Solution();
System.out.println(T.solution(new int[]{30, 20, 25, 15}, new String[]{"10:23 0", "10:40 3", "10:42 2", "10:52 3", "11:10 2"}));
System.out.println(T.solution(new int[]{30, 20, 25, 15}, new String[]{"10:23 0", "10:40 3", "10:42 2", "10:52 3", "15:10 0", "15:20 3", "15:22 1", "15:23 0", "15:25 0"}));
System.out.println(T.solution(new int[]{30, 20, 25, 15}, new String[]{"10:20 1", "10:40 1", "11:00 1", "11:20 1", "11:40 1"}));
}
}
[ 결과 ]
3
4
0