컨트롤 제트 - Java [프로그래머스 입문]

 

❤️ Problem

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

 

• 제한 사항
  • 0 < s의 길이 < 1,000
  • -1,000 < s의 원소 중 숫자 < 1,000
  • s는 숫자, "Z", 공백으로 이루어져 있습니다.
  • s에 있는 숫자와 "Z"는 서로 공백으로 구분됩니다.
  • 연속된 공백은 주어지지 않습니다.
  • 0을 제외하고는 0으로 시작하는 숫자는 없습니다.
  • s의 시작과 끝에는 공백이 없습니다.
  • 모든 숫자를 지우는 경우는 주어지지 않습니다.
  • 지울 숫자가 없는 상태에서 "Z"는 무시합니다.

 

입출력 예 & 설명

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

1. 본문과 동일합니다.
2. 10 + 20 + 30 + 40 = 100을 return 합니다.
3. "10 Z 20 Z 1"에서 10 다음 Z, 20 다음 Z로 10, 20이 지워지고 1만 더하여 1을 return 합니다.

 

---

 

💛 Solution

풀이

import java.util.Stack;
class Solution {
    public int solution(String s) {
        String[] str = s.split(" ");
        Stack<String> st = new Stack<>();

        int sum = 0;
        for(int i=0; i<str.length; i++) {
            if(!str[i].equals("Z")) {
                st.push(str[i]);
            } else {
                st.pop();
            }
        }

        while (!st.isEmpty()) {
            sum += Integer.parseInt(st.pop());
        }
        return sum;
    }
}

 

처리속도를 더 빠르게 할 수는 없을까

 

---

 

💜 Comment

이 문제는 통과까지 정말 오래걸렸던 문제.

처음에는 배열로 해결하려고 해봤는데 연달아서 "Z"가 나오는 경우를 도저히 해결할 수 없었다.

if문 안에 While문을 써서 "Z"가 연달아 나오는 상황을 대비하려고 아래와 같이 코드를 짰다.

class Solution {
    public int solution(String s) {
        String[] str = s.split(" ");
        int sum = 0;
        for(int i=0; i<str.length; i++) {
            if(str[i].equals("Z")) {
                int ctrl = i-1;
                String temp = "";
                if(str[ctrl].equals("Z")) {
                    while (str[ctrl].equals("Z")) {
                        temp = str[ctrl-1];
                        ctrl--;
                    }
                    sum -= Integer.parseInt(temp);
                } else {
                    sum -= Integer.parseInt(str[i-1]);
                }
            } else {
                sum += Integer.parseInt(str[i]);
            }
        }
        return sum;
    }
}

 

결과는 보다시피 테스트 7에서 실패가 나왔다.

어떻게 해결해야 할지 모르겠어서 막막하던 중에 "컨트롤 제트"의 컨셉을 다시 생각해 보았다.

"컨트롤 제트"의 정의는 직전에 수행한 행동을 취소하는 것.

즉, 컨트롤 제트를 연속으로 누르면 직전에 더해졌던 값이 하나씩 취소되어야하는 것이었다.

그렇다면 직전 값을 인덱스 없이 뺄 수 있는 형태는 없을까? 고민 하던 중에 문득 정보처리기사 공부하면서 배웠던 후입선출이라는 개념이 빡 떠올랐다. 덕분에 Stack을 사용해서 문제를 해결할 수 있었다🤩

 

테스트 통과도 행복한데 점수까지 많이 주면..😍

 

---

 

🤍 Concept

1. Stack

• 데이터가 하나씩 쌓이는 형태의 자료구조
• 가장 마지막에 삽입된 데이터가 가장 먼저 호출됨 (후입선출, Last In First Out)
• 같은 구조와 크기의 데이터를 정해진 방향으로만 쌓을 수 있음
• top으로 설정한 곳을 통해서만 접근

 

• Stack 관련 메서드
  • Stack 값 추가 == stack.push(VALUE);
  • Stack 값 제거 == stack.pop();
  • Stack 초기화 == stack.clear();
  • 최상단 값 출력 == stack.peek();
  • Stack이 비어있는지 체크 == stack.empty();
  • Stack에 특정 값이 있는지 체크 == stack.contains(VALUE);

 

• Stack 관련 개념
  • stack underflow: 빈 스텍에서 데이터 추출 시 발생
  • stack overflow: 스택이 넘치는 경우 발생
  • 용례: 뒤로가기 기능, 실행취소 기능 등

 

---

 

2. Queue

• 데이터가 순서대로 처리되는 자료 구조
• 한쪽 끝은 front (삭제만 수행), 다른 쪽 끝은 rear(삽입만 수행)
• front에서 발생하는 삭제연산 == deQueue
• rear에서 발생하는 삽입연산 == enQueue
• 가장 먼저 삽입된 데이터가 가장 먼저 호출됨 (선입선출, First In First Out)
• 컴퓨터 버퍼에서 사용 (순서대로 처리하기 위함)

 

• Queue관련 메서드

import java.util.LinkedList;
import java.util.Queue;

public static void main(String[] args) {
//    Queue<String> queue = new LinkedList<>()
    Queue<Integer> queue = new LinkedList<>();    
}

 

1. Queue에 값을 추가하는 메서드
   • queue.add(VALUE);
   • queue.offer(VALUE);
2. Queue 값 제거 == queue.remove();
3. Queue 초기화 == queue.clear();
4. Queue의 첫번째 값을 반환 후 제거, 만약 값이 비어있다면 null 반환
   • queue.poll();
5. Queue에서 가장 먼저 들어간 값 출력 == queue.peek();

 

• Queue 사용 예시
  • 프로세스 관리
  • 캐시 구현
  • 순차적으로 처리가 필요한 프로그램