[프로그래머스 코딩테스트] 컨트롤 제트(Java)

  문제 설명

  숫자와 "Z"가 공백으로 구분되어 담긴 문자열이 주어집니다. 문자열에 있는 숫자를 차례대로 더하려고 합니다. 이 때 "Z"가 나오면 바로 전에 더했던 숫자를 뺀다는 뜻입니다. 숫자와 "Z"로 이루어진 문자열 s가 주어질 때, 머쓱이가 구한 값을 return 하도록 solution 함수를 완성해보세요.
 

  제한사항

• 1 <= s의 길이 <= 200
• -1,000 < s의 원소 중 숫자 < 1,000
• s에 있는 숫자와 "Z"는 서로 공백으로 구분됩니다.
• 연속된 공백은 주어지지 않습니다.
• 0을 제외하고는 0으로 시작하는 숫자는 없습니다.
• s는 "Z"로 시작하지 않습니다.
• s의 시작과 끝에는 공백이 없습니다.
• "Z"가 연속해서 나오는 경우는 없습니다.

 

  입출력 예

s	result
"1 2 Z 3"	4
"10 20 30 40"	100
"10 Z 20 Z 1"	1
"10 Z 20 Z"	0
"-1 -2 -3 Z"	-3

import java.util.Stack;
class Solution {
    public int solution(String s) {
        int answer = 0;
        Stack<String> stack = new Stack<>();
        for (String str: s.split(" ")) {
            if (str.equals("Z")) {
                stack.pop();
            } else {
                stack.push(str);
            }
        }
        while (!stack.isEmpty()) {
            answer += Integer.parseInt(stack.pop());
        }
        return answer;
    }
}

  문제를 보자마자 스택이 생각났습니다. 먼서 Stack을 생성합니다. for문은 split 메소드로 문자열 s를 공백으로 나눈 뒤 str 문자열에 할당합니다. str을 equals 메소드로 비교하여, 만약 문자열에 "Z"가 있다면 stack의 맨 위(마지막)에 있는 원소를 꺼냅니다. 더하기 목록에서 제거하는 것입니다. 이는 문제에서 제시한 숫자를 빼는 행위와 같습니다. 아직 문자열의 숫자들은 더해지지 않은 상태이고, 마지막에 한 번에 더해줄 것이기 때문입니다. 그렇지 않다면("Z"와 같지 않다면) push로 stack에 str을 원소로 삽입합니다.
  완성된 stack을 while문을 통해 계산할 차례입니다. while문은 stack이 비어있지 않은 동안 반복합니다. 원래 pop()처럼 자료구조에서 원소를 꺼내는 경우 자료구조가 비어있는지 항상 확인하는 것이 좋습니다. 그러나 이 문제는 조건이 명확한 탓에, if문에서는 확인하지 않았습니다. 테스트코드에서도 문제가 발생하지 않았구요.
  stack에서 꺼낸 값을 answer에 하나씩 더하여 할당합니다. 현재 stack에는 문자열이 삽입되어 있으므로, 계산 전에 Integer.parseInt를 사용하여 int형으로 바꿔주는 것을 잊으면 안 됩니다.
 

import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
    public int solution(String s) {
        int answer = 0;
        Deque<String> deque = new ArrayDeque<>();
        for (String str: s.split(" ")) {
            if (str.equals("Z")) {
                deque.pollLast();
            } else {
                deque.add(str);
            }
        }
        while (!deque.isEmpty()) {
            answer += Integer.parseInt(deque.pollLast());
        }
        return answer;
    }
}

  이 코드는 자료구조 중 Deque를 활용한 풀이입니다. 원리는 Stack을 풀 때와 동일합니다. 이렇게 표현하는 게 맞나 싶지만, 데크는 양방향 스택이라고 생각하면 편할 지 모르겠습니다. 스택은 단방향으로 쌓이는 반면, 데크는 양방향으로 쌓을 수 있습니다. 꺼내는 것도 물론 앞뒤로 자유롭게 가능합니다. 이 문제는 모든 원소의 합을 구하는 것이므로 앞에서 꺼내 더하든 뒤에서 꺼내 더하든 결과는 동일합니다. 그러나 다른 문제의 경우에는, 특히 순서 구분을 해야하는 문제라면 구분을 명확히 해주는 게 좋겠습니다. 이 코드에서는 스택으로 풀 때와 동일하게 한 방향으로 원소를 넣고 같은 방향으로 원소를 꺼냈습니다.

왼쪽 스택, 오른쪽 데크를 활용한 풀이 속도 차이 비교

  데크의 효율이 더 좋다기에 궁금해서 풀어봤는데 이렇게 확인해보니, 한눈에 비교가 가능합니다. 어떤 테스트 코드의 경우에는 약 5배의 속도 차이를 보여주는, 유의미한 결과를 보여줍니다.
  하나의 문제를 여러 방법으로 풀어보고 각 풀이의 효율성을 비교해보는 것도 괜찮은 것 같습니다. 아직 효율성을 따져보며 코딩할 능력은 안 되지만….
 

  어찌어찌 13일자까지 클리어 했습니다.