[Swift/자료구조] 1. 스택(Stack) + 간단한 문제풀이

이번시간에는 

Stack 자료구조 에 대해 알아보고 간단한 문제를 한번 풀어볼게요.

 

---

 

스택이란?

스택은 데이터를 특정순서대로 보관하는 자료구조

 

스택의 특징 

Last-In, First-Out (LIFO) 구조를 가짐
예를들어) 앱을 사용할 때 네비게이션을 통해 A -> B -> C 식으로 화면에 들어갔을 때, 뒤로가기 버튼을 누르면 C화면이 사라지고 B화면이 다시 나온다.
이처럼 가장 마지막에 들어온 화면(데이터)가 가장 빨리 나가는 구조

 

스택의 구현

Swift에서 배열로 매우쉽게 구현가능함 (배열 메서드들로 해결가능)

struct Stack<Element> {
  private var newArray: [Element] = []
  
  mutating func push(_ element: Element) {
    newArray.append(element)
  }
  
  mutating func pop() -> Element? {
    return newArray.popLast()
  }
  
  func peek() -> Element? {
    return newArray.last
  }
}

 

구조체로 스택을 구현하면 위와같이 구현 할 수 있다.

 

사실 코테에서는 위와같이 구조체로 만들어도 되지만 그냥 배열로 만들고,

append, popLast 등 메서드로 해결하는 것 같다.

(그냥 배열 쓰면됨)

 

스택 예제 풀이

프로그래머스의 올바른 괄호 문제를 예제로 한번 풀어보겠습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

한번 풀어보세요!

 

 

문제풀이 

사전처리. String의 첫번째 문자가 닫는괄호 ")" 라면 잘못됐으므로 바로 false 반환.

 

1. String으로 받은 문자열을 한개씩 for문으로 돌려보자.

2. 한개씩 받아서 스택에 넣는다.

  2-1 한개씩 받아서 넣을 때 여는괄호"(" 라면 그냥 스택에 넣어준다.

  2-2 한개씩 받아서 넣을 때 닫는괄호 ")" 라면 스택의 마지막 여는괄호를 제거해준다.
         "()" 가 한개 완성 됐으므로 제거)

         (스택에 데이터가 없으면 닫는 괄호가 먼저나왔거나, 닫는 괄호가 더 많다는 뜻이므로 false반환) 

func solution(_ s:String) -> Bool
{
    var stack: [Character] = []

    if s.first == ")" {
        return false
    }

    for str in s {
        if str == "(" {
            stack.append(str)
        } else {
            if stack.last == "(" {
                let _ = stack.popLast()
            } else {
                return false    
            }
        }
    }

    return stack.isEmpty
}

 

저는 위와같이 풀이했습니다.

물론 꼭 스택으로만 풀 필요는 없습니다.