2022. 7. 22. 20:13ㆍ2022 땅울림 썸머코딩
문제 접근방식
이 문제를 보고 운이 좋게도 자료구조시간에 stack 연습문제로 풀었던 괄호찾기문제가 떠올랐다. 그 문제는 괄호를 (,)이렇게 짝지어 내는 문제였는데 덕분에 stack을 써봐야겠다는 생각을 쉽게 할 수 있었다. 하지만 문제자체를 이해하기 어려워서 종이에 직접 괄호를 스틱으로 바꾸고 레이저로 잘라보았다. 처음으로 떠오른 아이디어는 레이저를 다른 char(나는 *로표시했다.)로 표시해보자였다. 코드는 다음과 같다.
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int main() {
int total=0; //출력값
stack<char>cut_stick; //괄호들을 넣을스택
string bracket; //괄호들을 입력받을 string
cin >> bracket;
for (auto& i : bracket) {
int count=0;
if (i == '(') { //(이면 push
cut_stick.push(i);
}
else if (i == ')') {
if (cut_stick.top() == '(') { //stack의 top이 (면 레이저로 표시
cut_stick.pop();
if (!cut_stick.empty()) {
cut_stick.push('*');
}
}
else if (cut_stick.top()=='*') {
while (cut_stick.top() == '*') {//다른 레이저가 top이면 레이저의 수만큼 count해주고
count++; //*를 pop해줬다가 다시넣어줌 이유는 한 레이저로
cut_stick.pop(); //여러막대를 잘라야하기때문에 그렇게 생각함.
}
cut_stick.pop();
total += (count+1); //해당막대의 레이저가 3개가 닿으면 4조각으로 잘리므로 +1
if (!cut_stick.empty()) {//만약 비어있다면 레이저가 닿는 막대가 끝부분에 도달한것
for(int j=0;j<count;j++){//그래서 다시 스택에 레이저를 넣지않음.
cut_stick.push('*');
}
}
}
}
}
cout << total;
}하지만 이러한 방식은 괄호의 갯수가 많아진다면 '*'을 수도 없이 stack에 push&pop을 반복해야하므로 너무 많은 시간이 필요했다. 그래서 시간초과가 떴다. 그래서 나는 레이저를 표시하지않고 해결하는 방법을 고민했다. 하지만 다른 방법이 떠오르지않아 다시 한 번 종이에 그려보았다.
이 그림에서 보면 첫 번째 레이저는 아무 막대도 자르지않는다. 하지만 두 번째 막대가 닿을 때, 3조각의 막대가 잘리고 세번째 레이저에 닿으면 또 3개가 생긴다. 그리고 4번째 막대가 닿을 때, 4개의 막대가 생기고 이런식으로 반복된다. 그래서 나는 stack에 들어있는 '('가 막대의 개수라고 생각해보았다. 그런데 문제는 레이저를 표시하지 않는다면 도대체 '('다음에 오는 ')'를 레이저인지 막대가 끝난 것 인지를 구분할 방법이 떠오르지 않았다. 이 부분을 제일 많이 고민했는데, 결국 결정 할 수 있는 요소는' )'전에 '('가 입력될때와 ')'가 입력되었을때를 알 수 있다면 해결할수있는것이었다. 그래서 bool변수를 이용해 마지막 입력된 괄호가 ')'일때를 표시하기로 했다.
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
stack<int>cut_stick;
string bracket;
int total=0;
bool is_closed=false; //이전의 괄호가 폐괄호일때
cin >> bracket;
for (auto& i : bracket) {
if (i == '(') {
cut_stick.push(i);
is_closed =false;
}
else if (i == ')') {
if (is_closed==false) {//레이저를 만났을때
cut_stick.pop();
total += cut_stick.size();//레이저로 잘라진 조각들 계산
is_closed = true;
}
else if (is_closed==true) {//막대기의 끝일때 ')'뒤에 또')'가나왔을때
total += 1;
cut_stick.pop();
}
}
}
cout << total;
}그렇게 했더니 레이저와 막대기의 끝을 구분해 문제를 풀수있었다.
느낀점: 난 성격이 급해 문제를 대충 읽으려는 경향이 좀 있는 것 같다. 그래서 문제를 한번에 이해하지 못하고,또 문제구상에 대한 것을 종이에 쓰는것을 너무 귀찮아한다. 그리고, 한번 방식을 정하면 코드를 엎는것을 귀찮아한다. 이 문제를 풀때 종이에 그려보니 천천히 윤곽이 잡히는게 느껴졌다. 어려웠던 부분이 확실히 있었지만 다른 방법을 시도해 풀어서 기뻤다.
시간복잡도: 입력값 n만큼 for문을 돌려야하므로 O(n)이고, 나머지 처리과정은 한번의pop과 push로 이루어지므로 결국 O(n)이다.