leetcode: Decode String

문제 조건

• k[encoded_string] => encoded_string을 k번 반복
• 3a 또는 2[4] 등의 경우는 없다고 생각한다

 

먼저, 괄호 중 ']' 을 만나는 순간, 뒤에서부터 가장 먼저 만나게 되는 '[' 의 위치를 찾아 그 부분을 반복하는 문제이다.

=> 뒤에서 부터 꺼내는 것이니까 스택을 사용하자

 

예를 들어 예시2와 같이 `3[a2[c]]` 가 주어졌다고 해 보자

아래와 같이 일단 닫는 괄호를 만나기 전까지는 스택에 push를 한다.

그 다음 여는 괄호를 만나기 전까지 pop을 하며 stringbuilder에 더해주고,

여는 괄호까지 pop한 뒤에 top이 숫자가 될 수 있는지 확인한다. 숫자이면 pop해주고, stringbuilder를 그 숫자만큼 반복해준다.

결과를 스택에 다시 넣어주고 위 규칙을 반복한다.

 

한가지 더 문제를 풀면서 주의할 점은 예시 4번과 같이 `abc3[cd]xyz`로 들어오게 되면 숫자와 문자의 분리가 필요하고,

스택에는 문자열로 집어넣기 때문에 문자열을 숫자로 바꿀 수 있는지 확인이 필요하다. 이는 아래와 같은 방법으로 해결했다.

class Solution {
	public String decodeString(String s) {
		Pattern p = Pattern.compile("(\\D)+|(\\d)+"); // 숫자와 숫자가 아닌것에 대한 분리
		Matcher m = p.matcher(s);
		
		while(m.find()) {
			System.out.println(m.group());
		}
	}

	private int isNumber(String str) { // 숫자인지 확인
		try {
			int n = Integer.parseInt(str);
			return n; // 맞다면 정수 리턴
		} catch (Exception e) {
			return -1; // 아니라면 -1 리턴
		}
	}
}

 

이를 코드로 옮겨보면 아래와 같다.

import java.util.*;
import java.util.regex.*;

class Solution {
	public String decodeString(String s) {
		Stack<String> stack = new Stack<String>();
		Queue<String> queue = new LinkedList<String>();

		Pattern p = Pattern.compile("(\\D)+|(\\d)+");
		Matcher m = p.matcher(s);

		while (m.find()) {
			StringTokenizer st = new StringTokenizer(m.group(), "[]", true);
			while (st.hasMoreElements()) {
				queue.add(st.nextToken());
			}
		}
		
		StringBuilder sb = new StringBuilder("");
		while (!queue.isEmpty()) {
			String str = queue.poll();

			if (str.equals("]")) {
				while (true) {
					String buffer = stack.pop();

					if (buffer.equals("[")) {
						break;
					}
					sb.insert(0, buffer);
				}

				if (!stack.isEmpty()) {
					int k = isNumber(stack.peek());
					if (k != -1) {
						stack.pop();
						for (int i = 0; i < k; i++) {
							stack.add(sb.toString());
						}
					}
				}
				
				sb.setLength(0);
			} else {
				stack.add(str);
			}
		}
		
		while(!stack.isEmpty()) {
			sb.insert(0, stack.pop());
		}
		return sb.toString();
	}

	private int isNumber(String str) {
		try {
			int n = Integer.parseInt(str);
			return n;
		} catch (Exception e) {
			return -1;
		}
	}
}