PentaS

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

문제 접근

1. 인덱스와 우선순위를 저장할 수 있는 클래스 생성

2. 큐에 인덱스와 우선순위 저장

3. 제일 앞 원소를 꺼내고, 나머지 원소들 중 꺼낸 원소보다 높은 우선 순위가 있는지 검사

4. 없으면 출력한 수 증가

5. 있으면 큐에 다시 넣고 1번부터 반복

소스 코드

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

class Solution {
    
    public class Job {
        
        public Job() {
            
        }
        
        public Job(int index, int priority) {
            this.index = index;
            this.priority = priority;
        }
        
        public int index;
        public int priority;
    }
    
    public int solution(int[] priorities, int location) {
        Queue<Job> q = new LinkedList<>();
        
        for (int i = 0; i < priorities.length; i++) {
            q.add(new Job(i, priorities[i]));
        }
        
        int count = 0;
        while (!q.isEmpty()) {
            Job job = q.poll();
            if (isHigherPriority(q, job)) {
                q.add(job);
            } else {
                count++;
                
                if (job.index == location) {
                    return count;
                }
            }
        }
        
        return -1;
    }
    
    public boolean isHigherPriority(Queue<Job> q, Job curJob) {
        for (Job job : q) {
            if (job.priority > curJob.priority) {
                return true;
            }
        }
        
        return false;
    }
}

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

문제 접근

일반적인 접근

1. 완주자 명단으로 해쉬맵 만듬

2. 참가자 명단 돌면서 없는 사람 찾음

위와 같이 접근하면 큰일 난거다.(맞다 나다!)

주의 사항 중 "동명이인이 존재한다" 이걸 명심해야한다.

항상 실수하는 것이 나 혼자서 제약사항의 범위를 결정해버리는 것이다...

테스트 케이스에는 참가자 명단에만 동명이인이 있다.

그렇다. 나는 완주자 명단에도 동명이인이 존재할 수 있다는 것을 고려를 안했다.

다음은 동명이인이 참가자 및 완주자 명단에 있는 것을 고려한 접근법이다.

1. 완주자 명단을 순회하며 해쉬맵을 만듬 (key: 이름, value: 동명이인 숫자)

1-1. 순회할 때, 이미 같은 이름이 있으면 값을 +1해서 갱신

2. 참가자 명단을 순회하며 해쉬맵에 이름이 존재하는지 확인

3. 이름이 존재하면, 값을 -1함

3-1. 값이 0보다 작으면 완주하지 못한 사람이므로 return

3-2. 값이 0보다 크면 -1한 값으로 해쉬맵을 갱신

4. 이름이 존재하지 않으면, 완주하지 못한 사람이므로 return

소스 코드

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> map = new HashMap<>();
        
        for (String name : completion) {
            if (map.containsKey(name)) {
                map.put(name, map.get(name) + 1);
            } else {
                map.put(name, 1);
            }
        }
        
        for (String name : participant) {
            if (map.containsKey(name)) {
                int count = map.get(name) - 1;
                if (count < 0) {
                    return name;
                } else {
                    map.put(name, count);
                }
            } else {
                return name;
            }
        }
        return answer;
    }
}

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

문제 접근

혼자서 하려다가 도저히 모르겠어서 질문하기를 통해 답을 참고했다.

아직 어떤 원리로 돌아가는지 모르겠어서 내일 조사해봐야겠다.

소스 코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        List<String> strList = new ArrayList<>();
        for (int num : numbers) {
            strList.add(Integer.toString(num));
        }

        StringBuilder sb = new StringBuilder();
        strList.stream()
                .sorted((s1, s2) -> {
                    int a = Integer.parseInt(s1 + s2);
                    int b = Integer.parseInt(s2 + s1);
                    return b - a;
                })
                .forEach(sb::append);
        
        answer = sb.toString();
        return answer.charAt(0) == '0' ? "0" : answer;
    }
}

문제링크: 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형

class Solution {
    int answer;

    public int solution(int[] numbers, int target) {
        answer = 0;
        dfs(numbers, target, 0, '+', 0);
        dfs(numbers, target, 0, '-', 0);

        return answer;
    }

    public void dfs(int[] numbers, int target, int sum, char ch, int idx) {
        switch (ch) {
            case '+':
                sum += numbers[idx];
                break;
            case '-':
                sum -= numbers[idx];
                break;
        }

        if (idx == (numbers.length - 1)) {
            if (sum == target) {
                answer++;
            }
        } else {
            dfs(numbers, target, sum, '+', idx + 1);
            dfs(numbers, target, sum, '-', idx + 1);
        }
    }
}

재귀함수를 이용한 DFS 알고리즘으로 접근을 했다.

DFS를 이용해야겠다는 생각은 했지만 stack을 이용한 DFS로 처음에 접근했다.

약간의 힌트를 통해 재귀함수로 방향을 바꾸었으나, dfs 메소드 반환형을 int로 해야한다는 강박에 return 조건을 어떻게 설정해야하나 고민했었다.

결국 다른 분의 코드를 참고하여 반환형을 void로 바꾸고 idx값 비교와 sum 값 비교를 통해 문제를 해결할 수 있었다.


핵심

1. 재귀함수 반환형 void
2. idx값이 배열 끝에 도달했을 때, sum이 target과 같은지 비교