백준 Swift, 막대기_17608 스택(Stack)문제풀이

 

 

안녕하세요? iOS Developer, 멍구입니다. 🤗
오늘은 간단한 스택 문제를 Swift로 풀어보겠습니다. 오늘 풀어볼 문제는 백준 17608번 문제, 막대기입니다. 

 

 

---

막대기 17608 문제 설명

백준 17608번 문제, 막대기 문제는 브론즈2 티어의 입문수준 문제입니다. 

 

 

시간 제한은 1초(추가 시간 없음) 으로 1억개 이하의 연산으로 끝내주어야 합니다. 정답비율은 54.438%입니다.

 

 

막대기 문제 설명입니다.
1) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙입니다. 
2) 이 후 우측에서 보았을때 보이는 막대기의 수를 보는 것입니다. 

이렇게 모두 일렬로 세웠을 때 보이는 막대기의 갯수는 어떻게 구할 수 있을까요??

일단 해당 막대기들 중 가장 긴 막대기는 보이게 되겠죠. 그리고 이후 가장 긴 막대기를 기점으로 점점 짧은 막대기가 측면으로 보이게 될 겁니다. 하지만 만약 도중에 긴 막대기가 보이게 되면 해당 막대기보다 짧은 막대기는 가려져 보이지 않게 됩니다. 
-> 이부분을 우리는 스택의 원리로 풀 수 있습니다. 

 

 

---

막대기 17608 입출력

입/출력 예시입니다. 입력 값 N이 주어지고, N개의 줄에 각각의 막대기 높이가 입력됩니다. 
N은 최대 10만까지 나오기 때문에 O(N^2)의 복잡도로는 어림도 없습니다. 10만 * 10만의 연산을 1억번의 연산을 훌쩍 넘기기 때문이죠!

저는 해당 문제를 Stack의 방법으로 풀 예정입니다. 그 원리는 아래와 같습니다.
1) 스택에 막대기 높이를 차례대로 넣어줍니다. 
2) 스택에 값이 있는데, 현재 들어갈 막대기보다 짧거나 같은 길이일 경우, 전부 제거해줍니다.(같은 길이여도 현재 막대기에 의해 가려지기 때문)
3) 이렇게 O(N)의 복잡도 만으로 문제를 해결할 수 있습니다. 

바로 알고리즘 문제, 막대기 풀이 가보겠습니다. 👨🏻‍💻

 

 

---

막대기 17608 문제풀이

1) 먼저 ip 라는 Int 타입 값 입력 받는 클로져를 정의합니다.

해당 코드는 입력 받는 코드를 단순하게 하기위해 사용했습니다. 이제 Int 타입의 값을 입력 받기 위해서 ip() 를 사용하면 됩니다. 

2) N을 입력 받고, stack변수를 선언합니다.

Swift에서는 별도의 스택을 지원하지 않습니다. 그래서 대신 배열을 스택(Stack)으로 사용합니다.

 

 

해당 문제에 대한 핵심 구현 코드입니다.

3) N번의 막대기 높이를 입력 받습니다. 하나하나 값을 받을 때마다 stack의 직전 막대기 높이값과, 현재 입력받은 막대기 높이값을 비교합니다. 

4) 이때 스택의 직전 높이(stack.last!)가 현재 막대기 높이보다 낮거나, 같다면 제거해줍니다.(removeLast())현재 막대기 높이보다 낮거나 같은 막대기들은 현재 막대기에 의해 가려질 것이기 때문입니다. 

5) 그렇게 최종적으로 [Int] 타입의 stack 배열에는 우측 측면에서 보이는 막대기의 리스트만 남게 됩니다. 

stack.last! 를 사용하기 전에 stack.isEmpty를 통해 stack이 비어있는지를 체크해 주어야 안전합니다. 만약 stack 변수가 비어있는데 last! 로 강제 접근 시, 런타임 에러를 유발하게 됩니다. 

 

 

---

문제 풀이가 완료되었습니다. 해당 코드를 제출합니다. 제출 결과는 아래와 같습니다. 😊