이번 장에서는 Stack을 활용해 문제를 해결해본다.
모든 코드는 깃허브 (링크)의 테스트 코드로 정리해두었다.
올바른 괄호
괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.
(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.
- 입력설명
첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다. - 출력설명
첫 번째 줄에 YES, NO를 출력한다. - 입력예제 1 (()(()))(()
- 출력예제 1 NO
public class CorrectBracket {
public String solution1(String brackets) {
Stack<Character> stackOfBrackets = new Stack<>();
for (int i = 0; i < brackets.length(); i++) {
if (brackets.charAt(i) == '(') {
stackOfBrackets.push('(');
} else {
if (stackOfBrackets.isEmpty()) {
return "NO";
} else {
stackOfBrackets.pop();
}
}
}
return stackOfBrackets.isEmpty() ? "YES" : "NO";
}
@Test
@DisplayName("올바른 괄호")
public void main() {
String expectedAnswer = "NO";
String answer1 = solution1("(()(()))(()");
assertEquals(expectedAnswer, answer1);
}
}괄호 문자 제거
입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하는 프로그램을 작성하세요.
- 입력설명
첫 줄에 문자열이 주어진다. 문자열의 길이는 100을 넘지 않는다. - 출력설명
남은 문자만 출력한다. - 입력예제 1 (A(BC)D)EF(G(H)(IJ)K)LM(N)
- 출력예제 1 EFLM
public class RemoveBracketCharacter {
// Stack을 활용한 풀이
public String solution1(String input) {
Stack<Character> stackOfBrackets = new Stack<>();
for (int i = 0; i < input.length(); i++) {
if (input.charAt(i) == '(') {
stackOfBrackets.push(input.charAt(i));
} else if (input.charAt(i) == ')') {
while (true) {
if (stackOfBrackets.pop() == '(') {
break;
}
}
} else {
stackOfBrackets.add(input.charAt(i));
}
}
return stackOfBrackets.stream()
.map(String::valueOf)
.collect(Collectors.joining());
}
// 괄호가 정상이라는 가정하에 단순 괄호 계산을 통한 풀이
public String solution2(String input) {
StringBuilder answer = new StringBuilder();
int count = 0;
for (int i = 0; i < input.length(); i++) {
if (input.charAt(i) == '(') {
count++;
} else if (input.charAt(i) == ')') {
count--;
} else if (count == 0) {
answer.append(input.charAt(i));
}
}
return answer.toString();
}
@Test
@DisplayName("괄호 문자 제거")
public void main() {
String input = "(A(BC)D)EF(G(H)(IJ)K)LM(N)";
String expectedAnswer = "EFLM";
String answer1 = solution1(input);
assertEquals(expectedAnswer, answer1);
String answer2 = solution2(input);
assertEquals(expectedAnswer, answer2);
}
}크레인 인형뽑기 (카카오 기출)
게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.
게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에 는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인 형은 바구니에 쌓이게 되는데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습 입니다.
만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.
크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)
게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위 치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 구하는 프로그램을 작성하세요.
- 입력설명
첫 줄에 자연수 N(5<=N<=30)이 주어집니다.
두 번째 줄부터 N*N board 배열이 주어집니다.
board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
0은 빈 칸을 나타냅니다.
1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나 타냅니다.
board배열이 끝난 다음줄에 moves 배열의 길이 M이 주어집니다.
마지막 줄에는 moves 배열이 주어집니다.
moves 배열의 크기는 1 이상 1,000 이하입니다.
moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다. - 출력설명
첫 줄에 터트려져 사라진 인형의 개수를 출력합니다. - 입력예제 1
5
00000
00103
02501
42442
35131
8
15351214 - 출력예제 1
4
public class DollClawMachine {
public int solution1(int[][] board, int gameCount, int[] moves) {
int answer = 0;
Stack<Integer> basket = new Stack<>();
for (int i = 0; i < gameCount; i++) {
int temp = 0;
for (int j = 0; j < board.length; j++) {
if (board[j][moves[i] - 1] != 0) {
temp = board[j][moves[i] - 1];
// 하나를 꺼냈으니 원래 있던 숫자의 자리를 0으로 바꾸어준다.
board[j][moves[i] - 1] = 0;
break;
}
}
if (temp != 0) {
if (!basket.isEmpty() && basket.peek() == temp) {
basket.pop();
// 한번에 두 개가 터지기 때문에 += 2
answer += 2;
} else {
basket.push(temp);
}
}
}
return answer;
}
@Test
@DisplayName("크레인 인형뽑기")
public void main() {
int[][] board = {
{0, 0, 0, 0, 0},
{0, 0, 1, 0, 3},
{0, 2, 5, 0, 1},
{4, 2, 4, 4, 2},
{3, 5, 1, 3, 1}
};
int gameCount = 8;
int[] moves = {1, 5, 3, 5, 1, 2, 1, 4};
int expectedAnswer = 4;
int answer1 = solution1(board, gameCount, moves);
assertEquals(expectedAnswer, answer1);
}
}후위식 연산
후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하세요.
만약 3(5+2)-9 을 후위연산식으로 표현하면 352+9- 로 표현되며 그 결과는 12입니다.
- 입력설명
첫 줄에 후위연산식이 주어집니다. 연산식의 길이는 50을 넘지 않습니다. 식은 1~9의 숫자와 +, -, *, / 연산자로만 이루어진다. - 출력설명
연산한 결과를 출력합니다. - 입력예제 1 352+*9-
- 출력예제 1 12
public class BackwardCalculation {
public int solution1(String input) {
char[] chars = input.toCharArray();
Stack<Integer> stackOfChar = new Stack<>();
for (char c : chars) {
if (Character.isDigit(c)) {
// Ascii '0' 은 10진수 48이므로
// Ascii - 48 은 10진수 0이 된다.
stackOfChar.push(c - 48);
} else {
int right = stackOfChar.pop();
int left = stackOfChar.pop();
switch (c) {
case '+':
stackOfChar.push(left + right);
break;
case '-':
stackOfChar.push(left - right);
break;
case '*':
stackOfChar.push(left * right);
break;
case '/':
stackOfChar.push(left / right);
break;
}
}
}
return stackOfChar.get(0);
}
@Test
@DisplayName("후위식 연산")
public void main() {
String input = "352+*9-";
int expectedAnswer = 12;
int answer1 = solution1(input);
assertEquals(expectedAnswer, answer1);
}
}쇠막대기
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.
- 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
- 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
- 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
- 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.
아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.
이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.
- 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반 드시 레이저를 표현한다.
- 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.
위 예의 괄호 표현은 그림 위에 주어져있다.
쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.
- 입력설명
한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다. - 출력설명
잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다. - 입력예제 1
()(((()())(())()))(()) - 출력예제 1
17 - 입력예제 2
(((()(()()))(())()))(()()) - 출력예제 2
24
public class IronStick {
public int solution1(String input) {
int answer = 0;
char[] chars = input.toCharArray();
Stack<Character> stackOfChar = new Stack<>();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(') {
stackOfChar.push(chars[i]);
} else {
stackOfChar.pop();
if (chars[i - 1] == '(') {
answer += stackOfChar.size();
} else {
answer++;
}
}
}
return answer;
}
@Test
@DisplayName("쇠막대기")
public void main() {
String input1 = "()(((()())(())()))(())";
int expectedAnswer1 = 17;
int answer1 = solution1(input1);
assertEquals(expectedAnswer1, answer1);
String input2 = "(((()(()()))(())()))(()())";
int expectedAnswer2 = 24;
int answer2 = solution1(input2);
assertEquals(expectedAnswer2, answer2);
}
}'Algorithm' 카테고리의 다른 글
| [Algorithm] Sorting (0) | 2022.02.25 |
|---|---|
| [Algorithm] Queue (0) | 2022.02.23 |
| [Algorithm] HashMap (0) | 2022.02.22 |
| [Algorithm] Sliding window (0) | 2022.02.21 |
| [Algorithm] Two Pointers (0) | 2022.02.21 |
