385. 미니 구문 분석기 (중간)

문자열 s가 정수 중첩 리스트를 나타낸다고 가정할 때, 이를 구문 분석하는 파서를 구현하고 파싱 결과인 NestedInteger를 반환하세요.

리스트의 각 요소는 정수 또는 정수 중첩 리스트일 수 있습니다.

예제 1:

<strong>입력:</strong> s = "324",
<strong>출력:</strong> 324
<strong>설명:</strong> 값 324만 포함하는 NestedInteger 객체를 반환해야 합니다.

예제 2:

<strong>입력:</strong> s = "[123,[456,[789]]]",
<strong>출력:</strong> [123,[456,[789]]]
<strong>설명:</strong> 다음 두 요소를 포함하는 NestedInteger 객체를 반환합니다:
1. 값 123을 포함하는 정수
2. 다음 두 요소를 포함하는 중첩 리스트:
   i.  값 456을 포함하는 정수
   ii. 다음 요소를 포함하는 중첩 리스트
        a. 값 789를 포함하는 정수

해결책 1. 스택

LIST_MARKER는 감지용 심볼로, 이전이 비어 있음을 나타내며 후속 감지에 대한 시작점을 알려줍니다. 각 문자에 대해:

1. [이면, 빈 인스턴스를 스택에 푸시하고 LIST_MARKER를 식별자로 추가합니다.
2. ]이면, LIST_MARKER 앞의 요소를 list에 넣고, LIST_MARKER를 제거한 후, list를 해당 빈 인스턴스에 추가합니다.
3. 숫자이면, while 루프를 사용하여 숫자를 추출하고 스택에 넣습니다.
4. ,이면, 계속 진행합니다.

주의할 점: while 루프 후 i는 숫자 범위를 벗어났으므로 i--가 필요합니다. 매번 i++로 감지할 때도 i < len을 확인하여 범위를 벗어나지 않도록 해야 합니다.

class Solution {
static NestedInteger LIST_MARKER = new NestedInteger(0);
public static NestedInteger deserialize(String s) {
Deque stack = new ArrayDeque<>();
boolean isNegative = false;
int length = s.length(), currentNumber = 0;
for(int i = 0; i < length; i++){
if(s.charAt(i) == ','){
// 쉼표는 무시
} else if(s.charAt(i) == '['){
stack.addLast(new NestedInteger());
stack.addLast(LIST_MARKER);
} else if(s.charAt(i) == ']'){
List tempList = new ArrayList<>();
while(stack.peekLast() != LIST_MARKER){
tempList.add(stack.removeLast());
}
stack.removeLast();
for(int j = tempList.size() - 1; j >= 0; j--) stack.peekLast().add(tempList.get(j));
} else {
currentNumber = 0;
if(s.charAt(i) == '-'){
i++;
isNegative = true;
}
while(i < length && Character.isDigit(s.charAt(i))){
currentNumber = currentNumber * 10 + s.charAt(i) - '0';
i++;
}
i--;
stack.addLast(isNegative ? new NestedInteger(-currentNumber) : new NestedInteger(currentNumber));
isNegative = false;
}
}
return stack.pop();
}
}

해결책 2. 재귀

문자열은 숫자형 또는 리스트형 중 하나입니다. 따라서 if 문을 사용하여 리스트와 숫자를 각각 처리합니다. 리스트의 경우, 리스트 내에 포함된 숫자와 리스트를 반복적으로 파싱하여 객체에 추가합니다. 숫자의 경우, 파싱된 객체를 반환합니다.

class Solution {
static int currentPosition = 0; // 현재 파싱 중인 문자열의 위치 인덱스

public static NestedInteger deserialize(String s) {
// 현재 문자가 '['이면 중첩 리스트 파싱 시작
if(s.charAt(currentPosition) == '[') {
currentPosition++; // '[' 건너뛰기
NestedInteger nestedInteger = new NestedIntegerImpl(); // 새로운 빈 NestedInteger 생성
while (s.charAt(currentPosition) != ']') { // ']'를 만날 때까지 계속 파싱
nestedInteger.add(deserialize(s)); // 중첩된 부분을 재귀적으로 파싱하고 결과를 현재 NestedInteger에 추가
if(s.charAt(currentPosition) == ','){ // 쉼표를 만나면 건너뛰기
currentPosition++;
}
}
currentPosition++; // ']' 건너뛰기
return nestedInteger; // 파싱된 NestedInteger 객체 반환
} else {
// 현재 문자가 '['가 아니면 단일 정수
boolean isNegative = false;
if (s.charAt(currentPosition) == '-') { // 음수인지 확인
isNegative = true;
currentPosition++;
}
int parsedNumber = 0;
// 숫자 부분 파싱
while (currentPosition < s.length() && Character.isDigit(s.charAt(currentPosition))) {
parsedNumber = parsedNumber * 10 + s.charAt(currentPosition) - '0'; // 숫자 생성
currentPosition++;
}
if (isNegative) {
parsedNumber *= -1; // 음수이면 -1을 곱함
}
return new NestedIntegerImpl(parsedNumber); // 파싱된 단일 정수의 NestedInteger 객체 반환
}
}
}

341. 중첩 리스트 평탄화 이터레이터 (중간)

중첩된 정수 리스트 nestedList가 주어집니다. 각 요소는 정수이거나 리스트일 수 있으며, 해당 리스트의 요소도 정수 또는 다른 리스트일 수 있습니다. 이 리스트의 모든 정수를 순회할 수 있도록 이를 평탄화하는 이터레이터를 구현하세요.

NestedIterator 클래스를 구현하세요:

• NestedIterator(List<NestedInteger> nestedList)는 중첩 리스트 nestedList로 이터레이터를 초기화합니다.
• int next()는 중첩 리스트의 다음 정수를 반환합니다.
• boolean hasNext()는 반복할 정수가 남아있으면 true를, 그렇지 않으면 false를 반환합니다.

코드는 다음 의사 코드로 검증됩니다:

이터레이터를 nestedList로 초기화
res = []
while iterator.hasNext()
   res의 끝에 iterator.next() 추가
return res

res가 예상되는 평탄화된 리스트와 일치하면 코드는 올바른 것으로 간주됩니다.

해결책 1. DFS

public class NestedIterator implements Iterator {
private List flattenedList; // 평탄화된 정수를 저장하는 리스트
private Iterator iterator; // 현재 순회 중인 이터레이터

// 생성자, 중첩 리스트를 받아 이터레이터를 초기화
public NestedIterator(List nestedList) {
flattenedList = new ArrayList(); // 정수 저장 리스트 초기화
depthFirstSearch(nestedList); // 깊이 우선 탐색 메서드 호출, 중첩 리스트 평탄화
iterator = flattenedList.iterator(); // 현재 이터레이터 초기화
}

// 다음 정수 반환
@Override
public Integer next() {
return iterator.next(); // 이터레이터를 사용하여 다음 정수 가져오기
}

// 다음 정수가 있는지 확인
@Override
public boolean hasNext() {
return iterator.hasNext(); // 이터레이터에 다음 요소가 있는지 확인
}

// 중첩 리스트를 평탄화하기 위한 깊이 우선 탐색 메서드
private void depthFirstSearch(List nestedList) {
for (NestedInteger element : nestedList) { // 중첩 리스트의 각 요소 순회
if (element.isInteger()) { // 정수이면 vals 리스트에 추가
flattenedList.add(element.getInteger());
} else { // 리스트이면 재귀적으로 처리
depthFirstSearch(element.getList());
}
}
}
}

해결책 2. 스택 + 재귀

public class NestedIterator implements Iterator {
// 현재 순회 중인 리스트 이터레이터를 저장하는 스택
private Deque> iteratorStack;

// 생성자, 중첩 리스트를 받아 이터레이터를 스택에 푸시
public NestedIterator(List nestedList) {
iteratorStack = new LinkedList>(); // 스택 초기화
iteratorStack.push(nestedList.iterator()); // 중첩 리스트의 이터레이터를 스택에 푸시
}

// 다음 정수 반환
@Override
public Integer next() {
// next 호출 전에 항상 hasNext가 호출된다고 보장되므로, 스택 맨 위 리스트의 현재 요소를 직접 반환
return iteratorStack.peek().next().getInteger();
}

// 다음 정수가 있는지 확인
@Override
public boolean hasNext() {
while (!iteratorStack.isEmpty()) {
Iterator currentIterator = iteratorStack.peek(); // 스택 맨 위 이터레이터 가져오기
if (!currentIterator.hasNext()) { // 현재 이터레이터가 끝났으면 스택에서 제거
iteratorStack.pop();
continue;
}
NestedInteger currentElement = currentIterator.next(); // 다음 요소 가져오기
if (currentElement.isInteger()) { // 요소가 정수이면
List singleElementList = new ArrayList();
singleElementList.add(currentElement); // 해당 정수를 리스트로 감싸기
iteratorStack.push(singleElementList.iterator()); // 해당 리스트의 이터레이터를 스택에 푸시
return true; // 정수를 찾았으므로, 다음 호출 시 반환할 수 있음
}
// 요소가 리스트이면, 해당 리스트의 이터레이터를 스택에 푸시하여 계속 확장
iteratorStack.push(currentElement.getList().iterator());
}
return false; // 스택이 비어 있으면 더 이상 순회할 요소가 없음
}
}

394. 문자열 디코딩 (중간)

인코딩된 문자열이 주어졌을 때, 그것을 디코딩한 문자열을 반환하세요.

인코딩 규칙은 다음과 같습니다: k[encoded_string], 여기서 괄호 안의 encoded_string은 정확히 k번 반복됩니다. k는 양의 정수임을 보장합니다.

입력 문자열은 항상 유효하다고 가정할 수 있습니다; 입력 문자열에는 추가 공백이 없으며, 입력된 괄호는 항상 올바른 형식을 따릅니다.

또한, 원본 데이터에는 숫자가 포함되지 않으며, 모든 숫자는 반복 횟수 k만을 나타냄을 가정할 수 있습니다. 예를 들어 3a 또는 2[4]와 같은 입력은 나타나지 않습니다.

해결책 1. 스택

1. c가 문자이면 res 업데이트
2. c가 숫자이면 multi 업데이트
3. c가 [이면 스택에 푸시하고 res와 multi를 재설정
4. c가 ]이면 스택에서 팝, 이전 res를 가져와 새로운 res와 연결

class Solution {
public static String decodeString(String s) {
int length = s.length(), multiplier = 0;;
StringBuffer currentString = new StringBuffer();
Deque multiplierStack = new ArrayDeque<>();
Deque stringStack = new ArrayDeque<>();
for(int i = 0; i < length; i++){
if(i < length && s.charAt(i) == '['){
multiplierStack.push(multiplier);
multiplier = 0;
stringStack.push(currentString.toString());
currentString = new StringBuffer();
} else if(i < length && s.charAt(i) == ']'){
int repeatCount = multiplierStack.pop();
StringBuffer temp = new StringBuffer();
while(repeatCount != 0){
temp.append(currentString);
repeatCount--;
}
currentString =  new StringBuffer(stringStack.pop() + temp);
} else if(i < length && Character.isDigit(s.charAt(i))){
while(i < length && Character.isDigit(s.charAt(i))){
multiplier = multiplier * 10 + s.charAt(i) - '0';
i++;
}
i--;
} else {
while(i < length && Character.isLetter(s.charAt(i))){
currentString.append(s.charAt(i));
i++;
}
i--;
}
}
return currentString.toString();
}
}

해결책 2. 재귀

주석 참조

class Solution {
// 주 함수, 재귀 함수를 호출하여 문자열 디코딩
public String decodeString(String s) {
return decode(s, 0)[0]; // 문자열의 첫 번째 문자부터 재귀 디코딩 시작
}

// 재귀 함수, 인덱스 i부터 시작하는 부분 문자열을 디코딩
private String[] decode(String s, int i) {
StringBuilder decodedString = new StringBuilder(); // 디코딩된 결과 저장
int repeatCount = 0; // 현재 숫자 배수 저장
while(i < s.length()) {
if(s.charAt(i) >= '0' && s.charAt(i) <= '9') {
// 현재 문자가 숫자이면 repeatCount 업데이트 (다자리 숫자 지원)
repeatCount = repeatCount * 10 + Integer.parseInt(String.valueOf(s.charAt(i)));
} else if(s.charAt(i) == '[') {
// '['를 만나면 괄호 내부 문자열 처리 시작, 재귀적으로 처리
String[] resultPair = decode(s, i + 1);
i = Integer.parseInt(resultPair[0]); // 인덱스 i를 괄호 끝 이후로 업데이트
// repeatCount 값만큼 디코딩된 문자열을 반복하여 추가
while(repeatCount > 0) {
decodedString.append(resultPair[1]);
repeatCount--;
}
} else if(s.charAt(i) == ']') {
// ']'를 만나면 현재 괄호 내부 처리 완료, 결과와 현재 인덱스 반환
return new String[] { String.valueOf(i), decodedString.toString() };
} else {
// 현재 문자가 문자이면 결과에 직접 추가
decodedString.append(String.valueOf(s.charAt(i)));
}
i++; // 다음 문자로 이동
}
// 완전히 디코딩된 문자열 반환 (가장 바깥쪽 호출용)
return new String[] { decodedString.toString() };
}
}