평소 자료구조를 공부하면서 que, stack등의 자료구조를 공부해가며, que는 FIFO(First In First Out), stack은 FILO(First In Last Out)구조라는것은 알고 있었다. 하지만 지금까지는 이러한 자료구조들의 활용 방법을 몰라서, 알고리즘 문제를 푸는데 활용하지 못해왔다.
오늘은 이런 자료구조를 알고리즘 문제를 푸는데 이용해봤다.
오늘 풀어본 문제는 햄버거 만들기!
배열속에 1~3의 숫자가 들어있고, 1,2,3,1 4개의 숫자가 연속으로 존재한다면 return 값을 1씩 늘려주면 되는 문제다.
이문제를 보자, stack을 활용하면 좋을것 같다고 생각했고, 활용방법은 알지 못해서 검색해봤다..
먼저 stack을 사용하려면
import java.util.Stack해당 값을 import시켜줘야 했다. 그 후에,
val a = Stack<Int>()변수에 Int형 stack을 이렇게 선언해주었다. 그후
for (i in ingredient) {
a.push(i)
// 스택의 맨 위 요소가 1이고 스택의 크기가 4 이상인 경우 조건 확인
if (a.peek() == 1 && a.size >= 4) {
val first = a[a.size - 4] == 1
val second = a[a.size - 3] == 2
val third = a[a.size - 2] == 3
val fourth = a[a.size - 1] == 1
if (first && second && third && fourth) {
// 1, 2, 3, 1이 등장한 부분을 스택에서 제거
repeat(4) { a.pop() }
answer++
}
}
}for문으로 배열의 값들을 하나씩 순회하며, 그 값들을 스택a에 넣어준다.
내가 원하는건 1,2,3,1 4개의 숫자가 연속으로 존재할때를 찾아야 하니까 if문을 이용해서 찾아주는데, peek()를 이용해서 스택의 맨 위 요소가 1일때를 찾아줬다.
그 이유는? stack은 FIFO형식의 자료구조로, 1,2,3,1이 순서대로 들어간다면 제일 위에있는 값은 1, 그아래는 3, 이렇게 위치하기때문에.
그리고 찾아야할 값이 4개이므로 배열의 크기가 4이상일때, 연속하는 수 4개가 1,2,3,1일때 pop()연산을 이용해서 stack에서 해당 값들을 지워주도록 했다.
전체코드
import java.util.Stack
class Solution {
fun solution(ingredient: IntArray): Int {
var answer: Int = 0
val a = Stack<Int>()
// 배열 ingredient의 각 요소를 스택에 추가하면서 연속된 숫자를 추적
for (i in ingredient) {
a.push(i)
// 스택의 맨 위 요소가 1이고 스택의 크기가 4 이상인 경우 조건 확인
if (a.peek() == 1 && a.size >= 4) {
val first = a[a.size - 4] == 1
val second = a[a.size - 3] == 2
val third = a[a.size - 2] == 3
val fourth = a[a.size - 1] == 1
if (first && second && third && fourth) {
// 1, 2, 3, 1이 등장한 부분을 스택에서 제거
repeat(4) { a.pop() }
answer++
}
}
}
return answer
}
}stack의 사용은 생각보다 간단했다. push & pop을 이용해서 stack에 값을 넣고, 뺄수 있다는 사실만 알면 앞으로도 잘 쓸수 있을것같다.
