프로그래머스 - 쇠막대기
https://programmers.co.kr/learn/courses/30/lessons/42585
문제 내용
여러 개의 쇠막대기를 레이저로 자르려고 한다.
쇠막대기는 아래에서 위로 겹쳐놓고, 레이저로 수직으로 자른다.
쇠막대기는 '('로 열고, ')'로 닫는다.
레이저는 '('와 ')'를 붙여서 표현한다.
생성된 쇠막대기의 수를 리턴하자.
제한 사항
- 2 <= 문자열의 길이 <= 100,000
- 괄호의 쌍은 항상 짝이 맞다.
1. stack을 이용하여 풀기 - O(N)
주어진 문자열은 마치 쌓아 놓은 막대기를 위에서 보듯이 표현하고 있다.
'('는 막대기의 시작을 의미하고, ')'는 막대기의 끝을 의미한다.
그리고 ‘()’는 레이저를 의미한다.
'('와 ')'의 용도가 두 개라서 어떻게 처리해야 할 지 고민할 수 있다.
사실 처리하는 방법은 간단한다.
괄호의 표현이 레이저가 되는 것은, '('과 ')'가 붙어있을 때 뿐이다.
'(())' 에서, 양 끝의 '('와 ')'는 막대기를 의미한다.
그리고 가운데의 '()'는 레이저를 의미한다.
즉, ')' 이전에 '('가 있었다면 이는 레이저라는 의미이다.
따라서 '('면 무조건 막대기다! 라고 생각하며 쌓아주고,
')'면 이전 문자가 '('였다면 사실은 레이저였다! 라고 생각하고 막대기를 하나 빼고,
'('가 아니었다면 막대기의 끝이다! 라고 생각하고 막대기를 하나 빼면 된다.
'(())'를 보며 생각해보자.
'('를 만났다. 막대기 한 칸을 쌓아준다. (1칸)
'('를 만났다. 막대기 한 칸을 쌓아준다. (2칸)
')'를 만났다. 막대기 한 칸을 줄여준다. (1칸)
그리고 전의 문자가 '('였다. 레이저를 쏴 주자.
1칸 쌓여있던 막대기가 잘려서 막대기가 하나 생겼다.
')'를 만났다. 막대기 한 칸을 줄여준다. (0칸)
그리고 전의 문자가 ')'였다.
잘리고 남은 막대기 하나를 더해주자.
이치에 맞게 돌아가고 있는 것을 확인할 수 있다.
그러면 이제 레이저를 쏘느냐, 막대기 하나가 끝나느냐에 따라 실제로 생성된 막대기 수를 세는 방법을 생각해야 한다.
레이저를 쏘게 된다면, 현재 쌓인 막대기 개수 만큼 새로운 막대기가 생길 것이다.
3개를 쌓았다면, 레이저로 잘린 왼편에는 3개의 막대기가 생길 것이다.
그리고 하나의 막대기의 끝에 도달했다면, 더 이상 잘리지 않는 막대기 1개가 추가될 것이다.
그렇다면 어떻게 해야 할 지 정해졌다.
'('를 만날 경우, 스택에 push를 하면 된다.
')'를 만날 경우, 스택에서 pop을 한 뒤,
바로 이전 문자가 '('이었다면 레이저를 쏘는 것이므로 현재 스택의 크기 만큼 답을 더해주고,
그게 아니라면 하나의 막대기의 끝을 나타내는 것이므로 1을 더해준다.
왜냐하면 이 막대기는 더이상 잘릴 일이 없기 때문이다.
모두 잘리고 남은 1조각을 의미하므로, 1을 더해준다.
그러면 코드를 작성해보자.
solution_stack.cpp
#include <string>
#include <stack>
using namespace std;
int solution(string arrangement) {
int answer = 0;
stack<char> st;
char prev = '.';
for (char c : arrangement)
{
if ('(' == c)
st.push('(');
else
{
st.pop();
answer += ('(' ==prev) ? static_cast<int>(st.size()) : 1;
}
prev = c;
}
return answer;
}
2. stack 자료구조를 사용하지 않기 - O(N)
'('를 push하고, ')'를 만날 때 마다 pop을 한다.
그리고 현재 stack의 크기를 확인하며 새로 생성되는 막대기의 수를 계산한다.
위의 문장은 우리가 구현한 문제의 해법이다.
그런데 위의 문장을 계속해서 읽다 보면 무언가 이상한 점이 하나 있다.
우리는 stack의 top에 무엇이 들어있는지 관심을 가진 적이 있었는가?
스택에 들어가는 글자는 단 하나, '(' 뿐이다.
우리는 스택의 맨 위에 글자가 무엇인지 항상 알고 있으며, 관심도 없다.
우리가 관심을 가지고 지켜보던 정보는
몇 개의 막대기가 쌓여 있는가 이다.
굳이 스택에다 '(' 문자를 쌓아 둘 필요가 없다.
높이를 기록하는 단 하나의 변수 만으로도 구현이 가능하다.
높이 변수를 하나 선언하자. 초기 높이는 0이다.
'('를 만난다면, 1을 더하고, ')'를 만난다면, 1을 뺀다.
사실상 스택의 push/pop이라고 생각하면 된다.
어자피 스택에는 '('만 들어간다. height 개의 '('가 push되어 있다고 생각하자.
push/pop 하는 코드를 변수의 증가와 감소로 바꿔서 구현해보자.
solution_without_stack.cpp
#include <string>
using namespace std;
int solution(string arrangement) {
int answer = 0, height = 0;
char prev = '.';
for (char c : arrangement)
{
if ('(' == c)
++height;
else
{
--height;
answer += ('(' ==prev) ? height : 1;
}
prev = c;
}
return answer;
}
이렇게 하면 장점이 무엇일까?
시간 복잡도는 여전히 O(N)이다. push()와 pop()은 O(1)이기 때문이다.
하지만 메모리 사용량은 어떻게 될까?
스택을 사용할 경우, 스택에는 계속해서 '(' 문자가 push 될 것이다.
경우에 따라 1~2개 씩만 쌓일수도 있겠지만, 최악의 경우 N/2개만큼의 '('가 쌓일 것이다.
하지만 크기의 정보만을 가지고 있는다면, 메모리는 int 변수 하나만큼만 있으면 된다.
따라서, 공간 복잡도가 O(N)에서 O(1)로 줄어들게 된다.
그리고 시간 복잡도는 둘 다 O(N)이지만, 필요한 작업량은 스택을 쓰는 것 보단 하나의 변수를 관리하는 편이 더 적다. 따라서 속도도 변수 하나만을 쓰는 편이 더 빠르다.
실제로 프로그래머스에서 두 코드를 채점해보면, 스택을 쓰는 쪽이 변수 하나만을 쓰는 쪽 보다 1.5배정도 더 오래걸린다.
나에게 필요한 정보가 무엇인지 정확하게 캐치하고, 필요한 만큼만 쓰는 것도 중요하다.
Comments