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;
                    }
                }
            }
        }
    }
}

문제 접근
재귀 DFS로 문제를 접근함

1. 상하좌우에서 현재 체크 중인 값은 재귀 DFS 호출

2. 상하좌우에서 현재 체크 중인 값과 같지 않으면 해당 위치를 Stack에 저장함

3. 재귀 DFS가 끝나면 면적 체크해서 1 이상이면 면적 수 증가 & 면적 최대 크기 비교해서 갱신

3-1. 현재 체크 중인 값이 0이라면 3번 과정 진행X

4. Stack에 저장된 위치부터 1번 과정 진행

import java.util.*;

class Solution {
    static Stack<List<Integer>> anotherValueStack;
    static boolean[][] visit;
    static int visitCount;
    static int curAreaSize;
    static long[][] copiedPicture;

    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        int[] answer = new int[2];
        int mm = m;
        int nn = n;
        copiedPicture = new long[mm][nn];
        for (int i = 0; i < mm; i++) {
            for (int j = 0; j < nn; j++) {
                copiedPicture[i][j] = (long) picture[i][j];
            }
        }

        anotherValueStack = new Stack<>();

        visit = new boolean[mm][nn];
        for (int i = 0; i < mm; i++) {
            for (int j = 0; j < nn; j++) {
                visit[i][j] = false;
            }
        }
        visitCount = 0;
        curAreaSize = 0;

        int i = 0;
        int j = 0;
        long curValue = 0;
        List<Integer> initPos = new ArrayList<>();
        initPos.add(0);
        initPos.add(0);

        anotherValueStack.push(initPos);
        while (visitCount < mm * nn) {
            List<Integer> pos = anotherValueStack.pop();
            i = pos.get(0);
            j = pos.get(1);
            curValue = copiedPicture[i][j];
            curAreaSize = 0;
            dfs(i, j, mm, nn, curValue);

            //측정 영역 크기가 1이상이면 영역 수 증가 & 최대값 크기 갱신
            if (curAreaSize >= 1 && curValue != 0) {
                numberOfArea++; //영역 수 증가
                maxSizeOfOneArea = Math.max(maxSizeOfOneArea, curAreaSize);
            }
        }

        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }

    public void dfs(int i, int j, int m, int n, long curVal) {
        //이미 방문했으면 진행하지 않음
        if (!visit[i][j]) {
            visitCount++;
            visit[i][j] = true;
            curAreaSize++;

            //위
            if ((i - 1) >= 0) {
                if (copiedPicture[i - 1][j] == curVal) {
                    dfs(i - 1, j, m, n, curVal);
                } else {
                    List<Integer> pos = new ArrayList<>();
                    pos.add(i - 1);
                    pos.add(j);
                    anotherValueStack.push(pos);
                }
            }
            //아래
            if ((i + 1) < m) {
                if (copiedPicture[i + 1][j] == curVal) {
                    dfs(i + 1, j, m, n, curVal);
                } else {
                    List<Integer> pos = new ArrayList<>();
                    pos.add(i + 1);
                    pos.add(j);
                    anotherValueStack.push(pos);
                }
            }
            //왼쪽
            if ((j - 1) >= 0) {
                if (copiedPicture[i][j - 1] == curVal) {
                    dfs(i, j - 1, m, n, curVal);
                } else {
                    List<Integer> pos = new ArrayList<>();
                    pos.add(i);
                    pos.add(j - 1);
                    anotherValueStack.push(pos);
                }
            }
            //오른쪽
            if ((j + 1) < n) {
                if (copiedPicture[i][j + 1] == curVal) {
                    dfs(i, j + 1, m, n, curVal);
                } else {
                    List<Integer> pos = new ArrayList<>();
                    pos.add(i);
                    pos.add(j + 1);
                    anotherValueStack.push(pos);
                }
            }
        }
    }
}

"질문하기"를 보니 테스트 케이스를 모두 통과하더라도 채점만 하면 틀렸다는 분들이 많았습니다.

다음과 같은 조언을 반영해서 통과했습니다.

1. 모든 전역변수를 solution 메소드 내에서 초기화

2. picture배열을 복사해서 사용

3. 복사한 picture배열의 타입은 long형