99클럽 코테 스터디 37일차 TIL - 385 Mini Parser

385. Mini Parser / c++ / Medium / 2시간+

문제 및 코드

class Solution {
public:
    NestedInteger deserialize(string s) {
        if (s[0] != '[') return NestedInteger(stoi(s));
        s = s.substr(1, s.length() - 2);

        NestedInteger ni;

        string current = "";
        for (int i = 0; i < s.length(); ++i)
        {
            if (s[i] == ',')
            {
                if (current != "")
                {
                    ni.add(NestedInteger(stoi(current)));
                    current = "";
                }
            }
            else if (s[i] == '[')
            {
                int bracketCount = 0;
                int j = i;
                for (; j < s.length(); ++j)
                {
                    if (s[j] =='[') bracketCount++;
                    else if (s[j] ==']')
                    {
                        if (--bracketCount == 0) break;
                    }
                }
                ni.add(deserialize(s.substr(i, j - i + 1)));
                i = j;
            }
            else
            {
                current += s[i];
            }
        }

        if (current != "")
        {
            ni.add(NestedInteger(stoi(current)));
        }

        return ni;
    }
};

접근 방식

자료 구조 / 스택

1. 주어진 문자열을 NestedInteger라고 하는 자료형구조로 변환(복원)하는 문제였다.
2. 문자열이 ‘[‘로 시작하면 앞뒤의 ‘[‘와 ‘]’를 제거해준다.
3. NestedInteger를 생성하고 문자열을 순회하면서 아래의 규칙으로 진행
   1. ’[‘을 만난다면, 괄호갯수를 카운트해주며 짝이 맞는 닫힌 괄호까지를 새롭게 deserialize에 넣어서 현재 NestedInteger에 add해준다. (그리고 i를 닫힌 괄호의 다음으로 이동)
   2. ’,’를 만나면, 만약 current (integer로 바꿀 string)이 비어있지 않다면 NestedInteger로 만들어서 현재 NestedInteger에 추가해준다.
   3. 위의 두 경우가 아니라면 숫자이므로 current에 추가해준다.
4. 위의 방법으로 생성된 NestedInteger를 반환

생각해 볼 점

1. 문제 자체는 재귀적으로 해결하면 쉬운 문제였지만, 이해를 잘못해서 시간을 엄청 잡아먹었다.

해시태그

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