스택/큐) 프로그래머스 : 올바른 괄호, 기능개발

1. 올바른 괄호

• 문제 접근 : '('의 개수에 맞게 끔 ')'을 이어주면 되는 문제다. 따라서 ( 의 개수를 파악하고 이 개수만큼 ) 가 오면 되는 것이다. (는 괄호의 시작이므로 배치에 제약이 없다. 핵심은 여는 괄호가 몇 개이든 간에 어쨌든 닫히기만 하면 되는 것이다. 즉, 스택을 활용하여 (를 저장하고 )를 만날 때마다 하나씩 제거해주면 된다. 이는 +,- 관계로 생각하여 리스트로도 풀이가 가능하다.
  • 스택에 들어가는 타입은 문자이므로 Character 타입으로 선언한다.
  • 주어진 배열 s의 처음부터 끝까지 문자를 탐색하기 위해서 charAt( ) 메서드를 사용한다.
  • 스택의 추가는 push, 제거는 pop으로, ( 를 만날 때마다 push를 한다.
  • ) 를 만났을 때는 두 가지 상황이 주어진다.
    1. 스택이 비어있을 때 ) 가 있는 경우 : 여는 괄호가 없는 상태에서 닫는 괄호가 있기 때문에 올바르지 않다.
    2. 스택에 ( 가 있는 상황에서 ) 가 있는 경우 : ( 가 적어도 1개는 있는 것이기 때문에 올바른 괄호이다.
• 예외 사항 : 만약에 괄호가 ((()) 이런식으로 끝날 경우 (여는 괄호 3개, 닫는 괄호 3개) 이는 올바르지 않은 괄호이다. 하지만 위 문제접근으로 코드를 작성했을 때 통과하게 된다. ) 가 스택이 비어있지 않은 상황에서 추가가 됐고, 닫는 괄호의 위치가 잘못된 것이 아니라 부족한 상황이기 때문이다. 따라서 순회가 끝난 뒤에 검증하는 코드가 필요하다. 만약, 괄호가 올바르게 끝났다면 스택은 비어있을 것이다. 하지만 위처럼 괄호가 다 닫히지 않았을 경우 스택에 ( 가 남아있게 된다. 즉, 이를 검증함으로써 최종적으로 괄호를 평가할 수 있다.

import java.util.*;
class Solution {
    boolean solution(String s) {
        boolean answer = false;
        // 스택을 사용하여 (를 추가하기, (가 들어간 만큼 )를 추가하기
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(0) == ')') return answer;
            
            if(s.charAt(i) == '('){
                stack.push('(');
            } else { // ')'일 때
                if(stack.isEmpty()){
                   return answer;
                } else {
                    stack.pop();
                }
            }
        }
        answer = (stack.isEmpty()) ? true : false;

        return answer;
    }
}

1-2. 올바른 괄호 (리스트로 접근)

• ( 가 있을 때 +1, )가 있을 때 -1을 함으로써 올바른 괄호일 경우 최종 값이 0가 된다. (서로 상쇄되기 때문) 하지만 올바르지 않은 괄호, 즉 순회가 끝났을 때 ( 가 남아있는 경우로 최종 값이 양수이거나 혹은 ( 의 개수보다 ) 가 더 많이 오게 될 때는 값이 음수로 바뀌게 된다. 이러할 경우에는 올바르지 않은 괄호라고 판단한다.

class Solution {
    boolean solution(String s) {
        boolean answer = false;
        int count = 0;
        for(int i = 0; i<s.length();i++){
            if(s.charAt(i) == '('){
                count++;
            }
            else if(s.charAt(i) == ')'){
                count--;
            }
            if(count < 0){
                break;
            }
        }
        if(count == 0){
            answer = true;
        }

        return answer;
    }
}

2. 기능 개발

• 문제 접근 : progress가 speed 만큼 증가하여 100이 되었을 때 배포가 된다. 따라서 각 progress 별로 배포되기 까지의 날짜를 계산한 뒤에 Queue에 저장한다. Queue에 저장하는 이유는 먼저 100%를 달성하더라도 progress의 순서대로 배포되어야 하기 때문에 우선순위가 정해져 있다. (FIFO - Queue) 따라서 Queue에 저장되는 요소들의 순서는 progresses 배열과 동일하다.
  • progresses 배열에 있는 progress 요소 순서대로 날짜 값을 계산하여 Queue에 저장한다.
  • 값이 작을수록 더 빨리 끝나는 것이기 때문에 Queue의 앞 순서의 날짜 값과 비교하여 배포 날짜를 정한다.
  • 날짜 값을 기준으로, 앞에 있는 값보다 뒤에 있는 값이 더 작을 경우( 뒤에가 더 빨리 끝날 경우 ) 앞에 있는 요소와 같이 배포된다. 반대로 뒤에 값이 더 클 경우 ( 앞에가 더 빨리 끝날 경우 ) 앞에는 끝나는 대로 바로 배포된다.

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        // FIFO 방식 - Queue 사용
        /*
        progresses 순서대로 날짜 값(count) Queue에 삽입
        progresses 날짜 count 값을 기준으로 묶어주기
        */
        Queue<Integer> queue = new LinkedList<>();        
        for(int i = 0; i < progresses.length; i++){
            double share = ((100-progresses[i]) / (double)speeds[i]);
            queue.add((int)(Math.ceil(share)));
        }
        
        int progress =0;
        int min = queue.poll(); // 첫 번째 값 빼기 (비교 대상)
        int count = 1; // 값 꺼낸 개수, 첫 번째 값 뺐기 때문에 1
        
        List<Integer> list = new ArrayList<>();
        
        while(!queue.isEmpty()){
            progress = queue.poll();
            
            if(min >= progress) {
                count++;
            } else{
                list.add(count);
                count = 1;
                min = progress;
            }
            if(queue.size() == 0) {
                list.add(count);
            }
        }
        
        // ArrayList -> array로 변환
        int[] answer = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            answer[i] = list.get(i);
        }  
        return answer;
    }
}

• while 문을 통해 queue가 비어있지 않을 때까지 값을 꺼내서 비교한다. 대소관계에 따라 기준 값(min)을 변경하거나 유지할 수 있다. 이 때 min이 변경될 경우, 배포 날짜가 갈리기 때문에 count 값을 다시 1로 초기화해야 하며, 기존에 있던 count 값은 내보내야 한다. 이 때는 list에 저장한다. 그렇지 않을 경우에는 min 값을 변경하지 않아야 된다. (여기서 코드를 실수해서 계속 테스트에 실패했다.) 
  • count는 하루에 배포될 수 있는 progress의 최대값이다.
• 주의할 점 : share 값을 계산할 때, 나눗셈 연산이 int / int 이므로 double로 형변환되는 과정에서 값이 누락될 수 있다. 따라서 둘 중 하나를 double 타입으로 바꿔야 한다. Math.ceil( )의 매개변수 타입이 double 이기 때문에 double로 변환했다가 다시 int형으로 변환한다.

2-2. 실수 부분

while(!queue.isEmpty()){
            progress = queue.poll();
            
            if(min >= progress) {
                count++;
            } else{
                list.add(count);
                count = 1;
            }
            
            min = progress;
            
            if(queue.size() == 0) {
                list.add(count);
            }
        }

• 기준값이 변경되는 min = progress; 부분을 if 문 안에 넣지 않고 바깥쪽에 작성하였다. 따라서 순회할 때마다 기준 값이 변경되는 오류가 발생하였다. 항상 코드를 작성할 때, 반복문/조건문 부분을 꼼꼼히 확인해야할 것 같다.

3. 느낀점

• 코드를 작성할 때, 항상 한 번에 완벽하게 작성하려고 하는 버릇이 있다. 처음부터 큰 그림을 그리고 시작하려다 보니 중간에 막히는 부분이 생기면 이를 해결하지 못하곤 한다. 해답은 정말 다양하게 나올 수 있기 때문에 내 방법이 틀렸다고 생각하지 말고 일단 처음부터 끝까지 차근차근 작성하는 연습을 해야할 것 같다. 그리고 중요한 건 코드를 충분히 테스트함으로써 예외 상황들을 체크하고, 그 이후에 코드를 효율적으로 바꿔보는 것이 필요하다. 맨 처음부터 100점 짜리 코드를 작성하려고 하기보다는 50점에서 60점 짜리로 만든 다음에 이를 조금씩 개선하면서 보완하는 것이다. 그러면 쉬운 문제도 어렵게 해석해서 지레 겁먹고 포기하는 문제들을 줄여나갈 수 있을 것 같다.