- 올바른 괄호(stack)
문제 설명: 괄호의 구조가 올바른지 판단하는 문제
int main(){
//freopen("input.txt","rt",stdin);
stack<int> st;
string s;
cin>>s;
for(int i=0; i<s.size();i++){
if(s[i]=='('){
st.push(1);
continue;
}
if(st.empty()){
cout<<"NO";
return 0; }
break;
}
else st.pop();
}
if(!st.empty()) cout<<"NO";
else cout<<"YES";
return 0;
}문제 자체는 이전에도 풀어본 기억이 있는 문제라 쉽게 풀었다.
stack 자료구조에 대해 배웠다. stack은 push와 pop을 통해 자료를 넣고 빼는데 가장 최근에 넣은 데이터가 pop을 통해 빠지는 형식의 구조이다. 내가 자주 사용했던 vector도 같은 기능이 있지만, stack은 그 기능이 제한적인 형태라고 한다. 그렇기 때문에 용도가 명확하다는 장점이 있다.
- 기차운행(stack응용)
문제설명:
int main(){
//freopen("input.txt","rt",stdin);
stack<int> st;
string answer="";
int n, tmp, cnt=1;
cin>>n;
st.push(0);
for(int i=0;i<n;i++){
cin>>tmp;
st.push(tmp);
answer+="P";
while(st.top()==cnt){
answer+="O";
cnt++;
st.pop();
}
}
while(st.top()==cnt){
answer+="O";
cnt++;
st.pop();
}
st.pop();
if(st.empty()){
cout<<answer;
}
else cout<<"impossible";
return 0;
}문제의 풀이방법 자체는 스택을 다루고 있다는 걸 알아서 빨리 생각해냈는데, 계속 답이 틀려서 시간을 많이 뺐겼다.
답이 틀린 경우의 수를 계속 코드에 덕지덕지 추가하다보니 지저분해지고 헷갈렸다.
코드를 짤 때 기능을 명확하게 하는게 중요할 것 같다. 이번에 고생한 게 push와pop을 한 번에 하는 케이스를 같이 고려했었는데, 그것때문에 많이 복잡했던 것 같다.
또 스택이 비어있는 상태에서 stack.top()을 사용하는 경우가 계속 발생해서 이를 방지하려고 stack에 0을 미리 넣어두는 방법을 썼는데, 차라리 empty()를 이용해 비어있는지 확인하고 top을 조회하는 방법이 더 깔끔하다.
결론
- 코드를 짜다가 너무 난잡해지면 덕지덕지 붙이느니 차라리 지우고 다시 짜자.
- 케이스를 나누되 공통적으로 수행하는 부분은 그냥 항상 수행하도록 하는 것이 명확하다. 이 문제에서는 push가 해당된다.
57. 재귀함수를 이용한 이진수 출력
문제 설명: 재귀함수를 이용해 10진수를 2진수로 변환한다.
void tenToTwo(int n){
if(n==0) return ;
tenToTwo(n/2);
cout<<n%2;
}
int main(){
//freopen("input.txt","rt",stdin);
int n;
cin>>n;
tenToTwo(n);
return 0;
}재귀 함수에 대해 배웠다.
함수는 호출되면 stack frame에 해당 함수의 매개변수, 지역변수, 복귀주소에 대한 정보를 기록한다. 그리고 작동되는 방식이 stack과 동일하다.
아직까진 이 복잡한 구조가 어떻게 활용될지 잘 모르겠다. 반복문보다 깔끔한 게 장점이라고 생각된다.
