공부 기록

문제 조건

• 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;
		}
	}
}

브루트포스 방법으로 양 옆을 다 보는 방법의 경우 시간복잡도 O(N^2)이 걸릴 것이다.

이 문제의 경우 아래와 같이 왼쪽에  있는 높이 중에서 가장 높은 높이만 보고 있는 상태이므로

=> 스택을 사용한다면 O(N)만에 문제를 풀 수 있다.

문제풀이 로직은 아래와 같다.

1. index를 오른쪽으로 움직이면서 스택의 맨 위에 담은 높이와 비교했을때 height[index]이 크거나 같으면 스택에 담는다.

2. 높이가 바뀌면 이전까지 물을 계산해서 answer에 더해주며, 이전 높이는 pop 시켜준다.

import java.util.*;
class Solution {
	public int trap(int[] height) {
		int answer = 0;

		Stack<Integer> stack = new Stack<Integer>();
		int index = 0;
		while (index < height.length) {
			while (!stack.isEmpty() && height[index] >= height[stack.peek()]) {
				int top = stack.pop();

				if (stack.isEmpty()) {
					break;
				}
				int distance = index - stack.peek() - 1;
				int bounded_height = Math.min(height[index], height[stack.peek()]) - height[top];
				answer += distance * bounded_height;
			}
			stack.push(index++);
		}

		return answer;
	}
}