Queue & Stack

1. Queue - zigzag level order traversal

Input :
Output : [[1], [3,2], [4,5]]

풀이

1. TreeNode 객체를 저장하는 Queue를 선언한다.
2. TreeNode의 root를 넣어준다.
3. 큐가 빌때까지 while문을 돌리면서 list에 값을 넣어주고, left 혹은 right가 있을 경우 큐에 넣어준다.
4. list에 값을 넣기 전에 zigzag 형태로 넣어야 하기 때문에 boolean변수를 이용한다.

소스

import java.util.*;

class TreeNode {
	int val;
	TreeNode left, right;

	public TreeNode(int x) {
		this.val = x;
	}
}

public class Q1 {

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.left = new TreeNode(4);
		root.left.right = new TreeNode(5);

		System.out.println(solve(root));

	}

	public static List<List<Integer>> solve(TreeNode root) {
		List<List<Integer>> result = new ArrayList<>();
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		q.offer(root);

		boolean zigzag = true;

		while (!q.isEmpty()) {
			int size = q.size();
			List<Integer> list = new ArrayList<Integer>();

			for (int i = 0; i < size; i++) {
				TreeNode node = q.poll();

				if (zigzag) {
					list.add(node.val);
				} else {
					list.add(0, node.val);
				}

				if (node.left != null) {
					q.offer(node.left);
				}

				if (node.right != null) {
					q.offer(node.right);
				}
			}

			zigzag = !zigzag;
			result.add(list);

		}

		return result;

	}

}

2. Stack

주어진 문자열에서 []안에있는 문자를 그 앞에있는 수만큼 반복해서 출력한다.
Input : String s = "12[a]2[bc]2[d]"
Output : "aaaaaaaaaaaabcbcdd"

풀이

1. 스택 2개를 만들어서 하나는 count를 담고, 하나는 괄호안에 있는 문자열을 담는다.
2. '['를 만났을 때와 ']'를 만났을 때 각각 해야하는 것을 구현하면 된다.
3. '['를 만나면 그 전까지 구한 count값을 스택에 넣고 문자열을 담는 result를 스택에 담는다.
4. ']'를 만나면 문자열을 담는 스택에서 문자열을 빼내고 count역시 빼서 count 만큼 []안에 있던 문자열을 append해준다.

소스

import java.util.*;

public class Q2 {

	public static void main(String[] args) {
		String s = "12[a]2[bc]2[d]";
		System.out.println(solve(s));
	}

	public static String solve(String s) {
		Stack<Integer> countStack = new Stack<Integer>();
		Stack<StringBuilder> stringStack = new Stack<StringBuilder>();

		StringBuilder result = new StringBuilder();
		// 숫자 담는 변수
		int k = 0;

		for (char c : s.toCharArray()) {
			if (Character.isDigit(c)) {
				k = k * 10 + c - '0';
			} else if (c == '[') {
				countStack.push(k);
				stringStack.push(result);

				result = new StringBuilder();
				k = 0;

			} else if (c == ']') {

				StringBuilder sb = stringStack.pop();
				for (int i = countStack.pop(); i > 0; i--) {
					sb.append(result);
				}

				result = sb;

			} else {
				result.append(c);
			}
		}

		return result.toString();
	}

}

참고

인프런 강의 : 코딩테스트 전 꼭 알아야 할 개념과 문제(with 자바) - 푸샵맨 코딩스터디