스택 문제 풀이 09번~10번 - 코딩 테스트 합격자 되기 C++

https://www.inflearn.com/course/cpp-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9/dashboard

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

박경록 저자님(ultrasuperrok@gmail.com) 책의 내용으로 공부하였습니다.

---

문제 09

10진수를 2진수로 변환하기
권장 시간복잡도 O(logN)

10진수 decimal을 입력받아 2진수로 변환해서 문자열 형태로 반환하는 solution() 함수를 구현하세요.

제약 조건
- 없음

입출력 예제

decimal	result
10	“1010”
27	“11011”
12345	“11000000111001”

---

#include <iostream>
#include <stack>
#include <string>
using namespace std;


string solution_09(int iDecimal);
int main()
{
    cout << solution_09(10) << endl;
    cout << solution_09(27) << endl;
    cout << solution_09(12345) << endl;

}

string solution_09(int iDecimal)
{
    if (iDecimal == 0) return "0";


    stack<int> s;
    while (iDecimal > 0) {
        s.push(iDecimal % 2);
        iDecimal = iDecimal / 2;
    }

    string sResult = "";
    while (!s.empty()) {
        sResult += to_string(s.top());
        s.pop();
    }
    return sResult;

}

---

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

 

[1차 막힘 구간]
배열에서 첫 번째 값이 무조건 닫힘 괄호면 0으로 리턴하는 건 알겠어,
그럼 첫 번째랑 두 번째가 pair인 것을 어떻게 알아차릴 수 있을까?
스택에서 가능한가? 다른 문법이 있는 건 아닐까

**틀린 문제 풀이**
int solution_10(string sParentheses)
{
    if (sParentheses == "") return 0;

    int iAnswer = 0;
    stack<char> sChar;
    if (sParentheses[0] == '{' || sParentheses[0] == '[' || sParentheses[0] == '(') 
    {
        sChar.push(sParentheses[0]);
        for (int i = 1; i < sParentheses.size()-1; i++)
        {
            // char 123-125 , char 91-93 , char 40-41 
            if (sParentheses[i] - sParentheses[i - 1])
                if (!sChar.empty())
                    sChar.pop();
                else
                    sChar.push(sParentheses[i]);
            else
                sChar.push(sParentheses[i]);
        }
        if (sChar.empty()) iAnswer += 1;
    }
    
    return iAnswer;
}

문자의 회전보다 먼저 괄호가 짝 맞추기가 가능한지 풀었다.
char의 번호를(ASCII) 번호를 빼서 숫자가 1 혹은 2가 나오면
pop을 하려고 하였으나 실패하였다.

책에 있는 괄호의 짝 마주는 과정 생각해 보기를 타이핑하며 이해해 보기로 하였다.

이제 괄호의 짝 맞추는 방법을 설명해 보겠습니다. 몸풀기 문제로 괄호 짝 맞추기를 스택으로 해결했습니다. 여기서도 당연히 스택을 사용해 풀 수 있습니다. 그런데 '스택을 사용해야겠군'이라는 아이디어가 바로 떠오르지 않으면 간단한 입력값을 놓고 출력값이 어떻게 나오는지 손으로 그려가면서 스택에 대한 힌트를 얻는 방법도 있습니다. 그렇게 한번 해봅시다. 이런 배열을 직접 그려놓고 생각해 봅시다.

여기서 핵심은 닫힌 괄호를 처음 보는 순간 가장 최근에 찾았던 같은 모양의 열린 괄호를 찾을 수 있어야 한다는 겁니다. 지금의 경우 인덱스 3의 대괄호가 처음 보는 닫힌 괄호이고, 마지막에 찾았던 열린 대괄호는 인덱스 2에 있습니다. 그다음에는 해당 열린 괄호 바로 직전에 찾았던 열린 괄호를 찾을 수 있어야 합니다. 즉, 열린 괄호를 관리하는 방법은 스택이 가장 적합하는 걸 알 수 있습니다. 그럼 코드로 문제를 풀어봅시다. -p.195-

책을 읽어도 Pair를 확인하는 방법은 아직 잘 모르겠다. 문자열을 회전할 수 있는 방법은 Queue로 진행하면 될 것 같은데 우선 저자님 코드를 읽어보자.

https://github.com/dremdeveloper/codingtest_cpp/blob/main/solution/10.cpp

codingtest_cpp/solution/10.cpp at main · dremdeveloper/codingtest_cpp

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;

int solution_t(string s);
int main()
{
    cout << solution_t("[](){}") << endl;
    cout << solution_t("}]()[{") << endl;
    cout << solution_t("[)(]") << endl;
    cout << solution_t("}}}") << endl;
}

// ❶ 닫힌 괄호의 짝을 바로 확인할 수 있도록 맵 선언 
unordered_map<char, char> breacketPair = {
    {')','('},
    {']','['},
    {'}','{'}
};

// ❷ 현재 인자로 받은 문자열 기준 괄호짝이 맞는지 확인
bool isValid(string& s, int start)
{
    stack<char> sPar;
    unsigned int sz = s.size(); // [궁금한점] 왜 unsigned로 하셨을까? => 양의 정수로만 for문 돌릴 예정이지 않을까 추측

    // ❸ 문자열을 순회하면서
    for (int i = 0; i < sz; i++)
    {
        char ch = s[(start + i) % sz]; // s[0%6] => s[0] 인거 같은데, [궁금한점]  이거 역순으로 하려고 %sz 적용하신걸까?
        // ❹ ch가 닫힌 괄호 인 경우
        if (breacketPair.count(ch)) {
            // ❺ 스택이 비었거나 top 원소가 ch와 짝이 맞는 열린 괄호가 아닌 경우 false 반환
            if (sPar.empty() || sPar.top() != breacketPair[ch]) return false;
            // ❻ ch와 짝이 맞는 열린 괄호일 경우 해당 열린 괄호를 제거
            sPar.pop();
        }
        else {
            // ❼ 열린 괄호일 경우 스택이 푸시
            sPar.push(ch);
        }
    }
    // ❽ for문을 다 돌고 스택이 비었다면 true를 반환
    return sPar.empty();
}

int solution_t(string s)
{
    int answer = 0;
    int n = s.size();

    // ❾ 문자열을 rotation하면서 괄호짝이 맞으면 answer를 1 증가 시킨다.
    for (int i = 0; i < n; i++)
    {
        answer += isValid(s, i);
    }
    return answer;
}

우선 내가 모르는 개념은
unordered_map를 사용해서 내부에 해당 key가 존재하는지 count() 함수로 찾아내는 것이다.

Count elements with a specific key
키가 k인 요소를 컨테이너에 검색하고 요소의 개수를 반환합니다.
unordered_map 컨테이너는 중복 키를 허용하지 않으므로,
해당 키가 있는 요소가 컨테이너에 있으면 함수가 실제로 1을 반환하고 그렇지 않으면 0을 반환합니다.

 

① unordered_map을 확용해서 각 닫힌 괄호를 키로, 이와 짝이 맞는 열린 괄호를 값으로 나타내었습니다. 이 코드에서는 두 가지를 고민해야 합니다. 1) 왜 열린 괄호가 아닌 닫힌 괄호를 키로 정했을까? 닫힌 괄호가 등장했을 때 앞에 짝이 맞는 열린 괄호가 있는지 확인해야 자연스럽기 때문입니다. 즉, '탐색의 기준'을 키로 정하면 됩니다. 2) map을 사용하지 않고 unordered_map을 사용했을까? map과 unordered_map의 공통점은 둘 다 key-value를 갖는 자료형입니다. 차이점은 map은 이진 탐색 트리로 구현되어 있으며 키를 기준으로 매번 자동 정렬이 되는 반면, unordered_map 은 해시 테이블로 구현되어 있으므로 키에 따른 정렬을 보장하지 않습니다. (...) 정렬할 필요가 없는데 매번 정렬하는 것은 불필요한 비용입니다. 따라서 이번 문제와 같이 키값을 기준으로 정렬할 필요가 없으면 unordered_map를 사용하는 게 더 좋습니다.

 

③ 먼저 괄호 패턴의 앞부터 차례대로 순회합니다. 문자열을 회전하면서 순회하는 부분이 좀 복잡할 수 있는데, string 의 실제 값을 변경하지 않고 start 값을 변경하면서 문자열이 마치 회전하는 것처럼 순회할 것입니다. 그림으로 좀 더 자세히 이해해 보겠습니다. 회색으로 칠한 칸이 start입니다. 반복문에서 start가 0이면 순회는 다음과 같이 진행됩니다.

그리고 start 1이면 다음과 같이 진행합니다. 문자열 string 의 맨 처음이 아닌 두 번째 문자부터 시작해서 맨 끝까지 탐생은 하다가, 더 이상 탐색할 문자가 없으면 맨 첫 문자부터 다시 탐색합니다. 즉, start=1이면 s [1]에서 시작해서 s [0]을 맨 마지막으로 순회합니다. 이는 s [1]을 맨 처음 문자로 하고, s [1] 이전의 문자들은 모두 배열의 맨 끝으로 보낸 후, 배열을 한번 순회한 것과 같습니다.

디버깅으로 start=4로 진행하면

이렇게 순회하는 식을 알 수 있다.

  char ch = s[(start + i) % sz];  이런식을 익혀두도록 하자.

---

[궁금했던점]

순회하는 식은 Queue로 진행할 수 있을것 같은데 Queue를 써도 되는 시간 복잡도인지 궁금합니다.