PentaS

문제링크: https://programmers.co.kr/learn/courses/30/lessons/12973

문제 접근

스택을 이용하여 괄호 맞추기랑 비스무리하게 풀면 된다.

1. 스택이 비었거나 스택 제일 위쪽에 있는 글자랑 현재 글자랑 다르면 스택에 넣음

2. 스택 제일 위쪽에 있는 글자랑 현재 글자가 같으면 스택에서 꺼냄

3. 문자열을 모두 순회 후, 스택이 비어있으면 1 아니면 0

문제 상황

처음 풀었을 때는 스택을 이용하지 않았다.

StringBuilder로 현재 포지션과 다음 포지션에 있는 글자가 같으면 두개를 지우고 포지션을 앞당겨서 푸는 방식으로 했다.

이렇게 하니 정확성 테스트는 통과했는데 효율성 테스트의 모든 케이스에서 시간 초과가 났다...

어쨋든 핵심은 스택이다.

소스 코드

import java.util.Stack;

class Solution {
    public int solution(String s) {
        Stack<Character> stack = new Stack<>();
        
        stack.push(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            char ch = s.charAt(i);
            
            if (stack.isEmpty() || stack.peek() != ch) {
                stack.push(ch);
            } else if (stack.peek() == ch)  {
                stack.pop();
            }
        }

        return stack.isEmpty() ? 1 : 0;
    }
}

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42586

문제 접근

1. 각 작업 진행 속도와 진행된 퍼센티지를 기반으로 배포까지 걸리는 일 수 계산

2. 배포 시작 기준이 되는 작업을 기준으로 전체 작업의 걸리는 일 수를 차감

3. 배포 시작 기준이 되는 작업부터 몇 개를 배포할 수 있는지 검사

4. 모든 작업이 배포될 때까지 1-3번 반복

문제 상황

문제 접근 3번을 잘 못 이해해서 좀 해맸었다.

내가 이해한 방식은 다음과 같다.

위와 같은 작업 상황일 때, 배포 될 수 있는 작업은 [1번 작업, 3번 작업, 4번 작업]의 총 3개라고 생각했다.

하지만, 문제에서 요구한 카운팅 방식은 2번 작업이 아직 완료되지 않았기 때문에 1번 작업만 배포 될 수 있다.

즉, 완료된 작업이 연속적으로 나열되어있는 갯수를 카운팅 하는 것이었다.

소스 코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] answer = {};
        boolean[] isDone = new boolean[progresses.length]; //작업이 완료됐는지 체크하는 배열
        int[] remainDays = new int[progresses.length]; //작업이 몇일이나 걸리는지를 저장하는 배열
        List<Integer> releaseCount = new ArrayList<>(); //배포된 작업의 갯수를 저장하는 리스트

        //작업 속도와 진행된 퍼센트를 이용해 배포까지 몇일 걸리는지 계산
        for (int i = 0; i < remainDays.length; i++) {
            int remainPercent = 100 - progresses[i];
            remainDays[i] = remainPercent / speeds[i];
            if (remainPercent % speeds[i] > 0) {
                remainDays[i]++;
            }
        }

        int curIndex = 0;
        int nextIndex;
        do {
            checkDone(isDone, remainDays, curIndex); //기준 작업의 남은 일을 기준으로 작업량 차감 및 완료된 작업 체크

            nextIndex = findNextIndex(isDone, curIndex); //다음 배포되지 않은 작업 인덱스 탐색
            //배포될 수 있는 작업 수를 리스트에 저장
            if (nextIndex != -1) {
                releaseCount.add(nextIndex - curIndex);
            } else {
                releaseCount.add(progresses.length - curIndex);
            }
            curIndex = nextIndex;
        } while(curIndex != -1);

        //배포된 이력을 배열로 변환
        answer = new int[releaseCount.size()];
        for (int i = 0; i < releaseCount.size(); i++) {
            answer[i] = releaseCount.get(i);
        }
        return answer;
    }

    public int findNextIndex(boolean[] isDone, int curIndex) {
        for (int i = curIndex + 1; i < isDone.length; i++) {
            if (!isDone[i]) {
                return i;
            }
        }

        return -1;
    }

    public void checkDone(boolean[] isDone, int[] remainDays, int curIndex) {
        int stdDay = remainDays[curIndex];
        for (int i = 0; i < remainDays.length; i++) {
            if (!isDone[i]) {
                if (remainDays[i] > 0 && remainDays[i] <= stdDay) {
                    remainDays[i] -= stdDay;

                    if (remainDays[i] <= 0) {
                        isDone[i] = true;
                    }
                }
            }
        }
    }
}