2강 자료구조 1 - 연습

시로 치카포카

이번 강의는 지금까지 배운 자료구조의 연습문제를 풀어보는 시간을 갖도록 한다. 주로 스택을 다루는 문제를 풀어본다고 한다.

 

<17413번 / 단어 뒤집기 2>

이 문제는 단어 뒤집기 문제와 비슷하지만 다른 점은 태그가 있다는 점이다. 태그 안에 있는 단어는 뒤집지 않고 밖에 있는 단어만 뒤집어준다. 그래서 단어 뒤집기 문제에서 태그 판단만 추가를 해주고 나머지는 거의 동일하게 구현하면 된다.

이 문제의 Worst case는 모든 단어가 스택에 추가되는 경우이기 때문에 시간 복잡도는 문자열의 길이가 N이라고 할 때, O(N)이 된다.

조금 헷갈리긴 했는데 <가 나오면 tag이니까 이전 스택에 있던거 다 출력하고 <출력, >면 tag가 false가 되고 >출력, tag가 true면 뒤집지말고 그대로 출력, 아니면 공백이 아닌 경우에는 스택에 단어 넣어두고 공백이면 스택 출력. 이렇게 하면 된다!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include <iostream> #include <string> #include <stack> using namespace std; void print(stack<char> &s) {     while (!s.empty())     {         cout << s.top();         s.pop();     } } int main() {     string str;     getline(cin, str);     stack<char> s;     bool tag = false;     for (int i = 0; i < str.length(); i++)     {         if (str[i] == '<')         {             print(s);             tag = true;             cout << str[i];         }         else if (str[i] == '>')         {             tag = false;             cout << str[i];         }         else if (tag)         {             cout << str[i];         }         else         {             if (str[i] == ' ')             {                 print(s);                 cout << str[i];             }             else             {                 s.push(str[i]);             }         }     }     print(s);     cout << '\n';     return 0; }

cs

 

<10799번 / 쇠막대기>

이 문제는 괄호 문자열의 심화버전인데 그 문제는 스택을 굳이 사용하지 않아도 됐지만 이건 스택을 사용해야 한다. 스택에 문자열의 index를 넣고 ( )를 판단하여 레이저인지, 쇠막대기인지를 판단해준다. 문제 이해가 약간 어렵긴 한데 일단 도전! 강의자료보고 차근차근했더니 쉽게 풀린 문제!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#include <iostream> #include <string> #include <stack> using namespace std; int main() {     string str;     cin >> str;     stack<int> s;     int num = 0;     for (int i = 0; i < str.length(); i++)     {         if (str[i] == '(')         {             s.push(i + 1);         }         else if (str[i] == ')')         {             if (i == s.top())             {                 s.pop();                 num += s.size();             }             else             {                 s.pop();                 num++;             }         }     }     cout << num << '\n';     return 0; }

cs

 

<17298번 / 오큰수>

동적할당...  int *arr=new int[n] 이거를 ()로 했더니 런타임 에러났다...ㅋㅋㅋㅋㅋ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include <iostream> #include <string> #include <stack> using namespace std; int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     int n;     cin >> n;     int *arr = new int[n];     int *res = new int[n];     for (int i = 0; i < n; i++)     {         cin >> arr[i];     }     stack<int> s;     s.push(0);     for (int i = 1; i < n; i++)     {         if (s.empty())         {             s.push(i);         }         while (!s.empty() && arr[s.top()] < arr[i])         {             res[s.top()] = arr[i];             s.pop();         }         s.push(i);     }     while (!s.empty())     {         res[s.top()] = -1;         s.pop();     }     for (int i = 0; i < n; i++)     {         cout << res[i] << ' ';     }     cout << '\n';     return 0; }

cs

 

<17299번 / 오등큰수>

지역배열을 썼더니 오류가 났다. 찾아보니까 지역배열은 힙, 전역배열은 스택을 쓰는데 힙이 범위가 작아서 그런거라고 한다. 그래서 전역배열로 바꿔서 오류를 해결하였다.

이 문제는 오큰수에서 빈도를 확인하는 배열을 추가하여 해결하였다. 이 배열의 index는 arr[i]의 숫자를 그대로 사용해서 범위가 1000001로 잡고 해당 숫자와 같은 index에 빈도를 추가하는 식으로 해결하였다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#include <iostream> #include <string> #include <stack> using namespace std; int freq[1000001]; int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     int n;     cin >> n;     int *arr = new int[n];     int *res = new int[n];       for (int i = 0; i < n; i++)     {         cin >> arr[i];         freq[arr[i]] += 1;     }     stack<int> s;     s.push(0);     for (int i = 1; i < n; i++)     {         if (s.empty())         {             s.push(i);         }         while (!s.empty() && freq[arr[s.top()]] < freq[arr[i]])         {             res[s.top()] = arr[i];             s.pop();         }         s.push(i);     }     while (!s.empty())     {         res[s.top()] = -1;         s.pop();     }     for (int i = 0; i < n; i++)     {         cout << res[i] << ' ';     }     cout << '\n';     return 0; }

cs

 

챕터 2 드디어 끝! 개강 전에 다 듣자!!