Sho1007

MMORPG 클라이언트 개발자 지망생

1 minute read

2434. Using a Robot to Print the Lexicographically Smallest String / c++ / Medium / 1시간+

문제 및 코드

#include <stack>
#include <set>
stack<char> Stack;
multiset<char> ms;
class Solution {
public:
    string robotWithString(string s) {
        int n = s.length();
        Stack = stack<char>();
        ms = multiset<char>();
        for (int i = 0; i < n; ++i)
        {
            ms.insert(s[i]);
        }
        string answer = "";
        int index = 0;
        while (index < n)
        {
            if (Stack.empty())
            {
                Stack.push(s[index]);
                ms.erase(ms.find(s[index++]));
            }

            while (!ms.empty() && Stack.top() > *ms.begin())
            {
                Stack.push(s[index]);
                ms.erase(ms.find(s[index++]));
            }

            answer += Stack.top(); Stack.pop();
            // cout << answer << '\n';
        }

        while (!Stack.empty())
        {
            answer += Stack.top(); Stack.pop();
        }

        return answer;
    }
};

접근 방식

자료 구조 / 스택

  1. 주어진 문자열 s와, 저장 공간 t를 활용하여 만들어질 수 있는 문자열 중, 사전적으로 가장 앞에 오는 문자열을 반환하는 문제
  2. 답은 문제에 있었다. 1번 동작은 s의 가장 앞 문자를 t의 가장 뒤에 붙이는 것, 2번 동작은 t의 가장 뒤에 있는 문자를 종이 (여기선는 answer)에 추가하는 것이었다.
  3. 2번에서 알 수 있듯이, t는 뒤에 추가되고, 뒤에서 제거된다. (LIFO) 즉, 스택 자료형이다.
  4. 이를 토대로 로직을 재구성해보면
  5. 우선 최소값을 알아야 하기 때문에 s의 모든 문자를 multiset인 ms에 넣는다.
  6. index가 n (s의 length)보다 작을 동안 아래를 반복
  7. 만약 t가 비어있다면 s[index]를 t에 넣고, ms에서 s[index]를 제거해준 후 index 증가
  8. t.top()이 *ms.begin() (남은 문자열 중 가장 작은 문자) 보다 크다면, 계속 t에 넣는다.
  9. 그러다 t.top()이 *ms.begin() 보다 작거나 같다면 (적지 않는 모든 문자 중 가장 작은 문자라면) answer에 적고 t에서 제거한다. (t.pop())
  10. 결국 s의 모든 문자가 t에 들어가고 그 중 일부는 answer에 적힌 채로 반복이 종료된다.
  11. 마지막으로 t가 빌 때까지, t에 들어있는 모든 문자를 answer에 추가해준다.
  12. answer를 반환
  13. 해결

생각해 볼 점

  1. 여러 방법을 생각하다 t의 구조가 stack과 유사하다고 생각했고, 남은 문자열의 최소 문자를 찾기 위해 multiset을 활용했다. 99클럽의 이전 문제에서 multiset을 활용했던 경험이 도움이 되었다.
  2. 나름 어렵게 느껴진 문제였지만, stl을 활용하여 스스로 풀었다는 점에서 성취감을 느낄 수 있었다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL

You may also enjoy