💡 문제
mini-parser (https://leetcode.com/problems/mini-parser/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.
총 소요 시간: 35~55분
💡 문제 (문제 설명 (한글 번역))
문자열 s가 중첩된 리스트의 serialization을 나타냅니다. 이를 deserialize하는 파서를 구현하여 deserialized된 NestedInteger를 반환하세요.
NestedInteger는 다음 두 가지 중 하나를 가질 수 있습니다:
- 단일 정수
- 정수 또는 다른 중첩 리스트를 포함하는 리스트
예제 1
입력: s = "324"
출력: 324
설명: 단일 정수 `324`를 포함하는 NestedInteger 객체를 반환합니다.
예제 2
입력: s = "[123,[456,[789]]]"
출력: [123,[456,[789]]]
설명: 다음과 같은 NestedInteger 객체를 반환합니다:
- 리스트는 두 요소를 포함합니다:
1. 값이 `123`인 정수
2. 또 다른 리스트:
- 값이 `456`인 정수
- 리스트:
- 값이 `789`인 정수
제약 조건
- 1 <= s.length <= 5 * 10^4
- s는 숫자, 대괄호([ ]), 음수 부호(), 쉼표(,)로 이루어져 있습니다.
- s는 유효한 NestedInteger serialization입니다.
- 입력 값은 범위 [-10^6, 10^6] 내의 정수를 포함합니다.
이 문제는 스택을 사용하여 중첩된 리스트 구조를 파싱할 수 있습니다.
📝 선행 개념
- 스택(Stack): 스택은 LIFO(Last In, First Out) 구조로, 중첩된 구조를 처리하거나 이전 상태로 돌아가야 할 때 유용하게 사용됩니다.
- Parsing: 문자열을 분석하여 원하는 데이터 구조로 변환하는 과정을 의미합니다.
- 재귀적 데이터 구조: 리스트가 다른 리스트나 정수를 포함할 수 있는 구조를 의미하며, 이 문제에서는 NestedInteger가 그 예입니다.
🤓 문제 풀이
🔨 문제 설명
문자열 s는 중첩된 리스트 또는 단일 정수를 직렬화한 데이터입니다. 이를 NestedInteger 객체로 deserialize해야 합니다.
예제 1
- 입력: "324"
- 출력: 324 (단일 정수)
예제 2
- 입력: "[123,[456,[789]]]"
- 출력: 중첩된 리스트를 표현하는 NestedInteger 객체
🔨 접근 방법
- 단일 정수 확인:
- 입력이 대괄호([)로 시작하지 않으면 단순 정수입니다. 이를 바로 변환하여 반환합니다.
- 스택을 활용한 중첩 처리:
- 중첩된 리스트 구조를 처리하기 위해 스택을 사용합니다. [를 만나면 새 리스트를 생성하고 스택에 추가하며, ]를 만나면 해당 리스트를 스택에서 꺼내 상위 리스트에 추가합니다.
- 숫자 파싱:
- 숫자가 여러 자리일 수 있으므로 num 변수에 저장하고, 음수(``)를 처리하기 위해 negative 플래그를 사용합니다.
- 최종 리스트 반환:
- 가장 외부 리스트는 스택이 비어 있는 상태에서 curr 변수에 남게 되며 이를 반환합니다.
🔨 문제 풀이 과정
- 문자열이 정수인지 확인:
- 문자열이 [, ]로 시작하지 않으면 단일 정수입니다.
- Integer.parseInt(s)를 사용해 정수로 변환 후 NestedInteger 객체로 반환합니다.
- 중첩 구조 처리:
- [를 만나면 새 NestedInteger 객체를 생성하고 스택에 추가합니다.
- ]를 만나면 현재 리스트를 스택에서 꺼내 상위 리스트에 추가합니다.
- 숫자와 음수 처리:
- 숫자를 순회하며 정수를 생성하고, 숫자가 끝나는 시점에 NestedInteger 리스트에 추가합니다.
- 음수를 만난 경우 이를 기록해 처리합니다.
- 결과 반환:
- 최종적으로 바깥쪽 리스트를 반환합니다.
🔨 구현코드
class Solution {
public NestedInteger deserialize(String s) {
// 단일 정수인 경우 바로 반환
if (!s.startsWith("[")) {
return new NestedInteger(Integer.parseInt(s));
}
// 스택을 활용하여 중첩된 구조를 처리
Stack<NestedInteger> stack = new Stack<>();
NestedInteger curr = null;
int num = 0; // 숫자를 저장
boolean negative = false; // 음수 여부 체크
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '[') {
// 새 NestedInteger를 생성하고 스택에 추가
if (curr != null) {
stack.push(curr);
}
curr = new NestedInteger();
} else if (ch == ']') {
// 숫자가 있다면 NestedInteger에 추가
if (Character.isDigit(s.charAt(i - 1))) {
curr.add(new NestedInteger(negative ? -num : num));
}
// 이전 상태로 돌아가기 위해 스택에서 pop
if (!stack.isEmpty()) {
NestedInteger top = stack.pop();
top.add(curr);
curr = top;
}
// 초기화
num = 0;
negative = false;
} else if (ch == ',') {
// 숫자가 있다면 NestedInteger에 추가
if (Character.isDigit(s.charAt(i - 1))) {
curr.add(new NestedInteger(negative ? -num : num));
}
// 초기화
num = 0;
negative = false;
} else if (ch == '-') {
// 음수 처리
negative = true;
} else if (Character.isDigit(ch)) {
// 숫자 처리
num = num * 10 + (ch - '0');
}
}
return curr;
}
}📚 풀이 보완
코드 설명
- 단일 정수 처리:
- 문자열이 대괄호([ 또는 ])로 시작하지 않으면 단일 정수입니다. 이를 바로 Integer.parseInt()를 사용해 파싱하여 NestedInteger 로 반환합니다.
- 스택을 이용한 리스트 처리:
- 중첩 구조 처리:
- [를 만나면 새 리스트를 생성하고 스택에 추가합니다.
- ]를 만나면 현재 리스트를 스택에서 꺼내 상위 리스트에 추가합니다.
- 중첩된 구조를 처리하기 위해 스택을 사용합니다.
- 대괄호 [ ]를 만날 때마다 새로운 NestedInteger 객체를 생성하여 스택에 추가하거나, 현재 작업 중인 리스트에 요소를 추가합니다.
- 중첩 구조 처리:
- 숫자 및 음수 처리:
- 숫자가 등장하면 num 변수에 저장하며, 음수 기호가 나오면 negative 플래그를 활성화합니다.
- 숫자가 끝나는 시점(,나 ] 등장)에 NestedInteger 객체에 추가합니다.
- 결과 반환:
- 가장 바깥쪽 리스트는 curr 변수에 저장되며, 이를 반환합니다.
📍 Plus+
시간 복잡도와 공간 복잡도 분석
시간 복잡도
- O(n): 문자열 s를 한 번 순회하며 각 문자에 대해 처리합니다.
공간 복잡도
- O(d): d는 중첩된 리스트의 최대 깊이입니다. 스택을 사용하므로 깊이에 비례한 메모리가 필요합니다.
요약
- 시간복잡도: O(n)
- 공간복잡도: O(d)