방구석프로의 이야기

http://school.programmers.co.kr/learn/courses/30/lessons/42583

문제

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

문제 해결을 위한 과정

이 문제는 매 초마다 일어나는 변화를 코드로 큐를 이용해서 해결할 수 있습니다.

1. 데이터 구조 설계: 다리 위 트럭의 현재 위치와 무게를 담을 Bridge static 클래스를 생성합니다.
2. 두 개의 큐 활용:
   • q1 (다리 위): 현재 다리 위에서 이동 중인 트럭들을 담습니다.
   • q2 (대기 중): 아직 다리에 진입하지 못한 트럭들을 담습니다.
3. 매 초 진행되는 로직:
   • 이동: 다리 위 모든 트럭의 위치(pos)를 1씩 증가시킵니다. (q1의 트럭들 pos 값 증가)
   • 탈출: 맨 앞 트럭의 위치가 다리 길이(bridge_length)에 도달하면 다리에서 내리고, 현재 다리 위 총 무게(sum)에서 해당 트럭 무게를 뺍니다.
   • 진입: 대기 중인 다음 트럭이 다리의 무게 제한을 버틸 수 있다면, 새로운 트럭을 다리에 올리고 위치를 0으로 설정합니다.

소스코드

import java.util.*;

class Solution {
    static class Bridge {
        int pos;
        int w;

        public Bridge(int pos, int w) {
            this.pos = pos;
            this.w = w;
        }
    }

    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 1;
        int sum = 0;
        int pass = 0;
        Queue<Bridge> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();

        for(int i = 0; i < truck_weights.length; i++) {
            q2.offer(truck_weights[i]);
        }

        int temp = q2.poll();
        q1.offer(new Bridge(0, temp));
        sum += temp;

        while(pass != truck_weights.length) {
            answer += 1;
            // 기존 트럭 이동
            for(int i = 0; i < q1.size(); i++) {
                Bridge br = q1.poll();
                q1.offer(new Bridge(br.pos  + 1, br.w));
            }
            // 제일 끝에 도달한 트럭이 있으면 내리기
            if(q1.peek().pos == bridge_length) {
                Bridge br = q1.poll();
                sum -= br.w;
                pass += 1;
            }
            // 새로운 트럭 올릴 수 있는지 판단
            if(!q2.isEmpty() && sum + q2.peek() <= weight) {
                q1.offer(new Bridge(0, q2.peek()));
                sum += q2.poll();
            }
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=java

문제

문제 설명

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

문제 해결을 과정

이 문제는 Queue와 PriorityQueue 두 가지 자료구조를 조합하면 쉽게 풀 수 있습니다.

1. 데이터 구조화: 프로세스의 '우선순위'와 '원래 위치(index)'를 기억해야 하므로 Program이라는 static 클래스를 만들어 관리합니다.
2. 두 개의 큐 활용:
   • 일반 Queue: 프로세스들이 줄을 서 있는 대기열
   • PriorityQueue: 현재 대기열 중 가장 우선순위가 높은 프로세스를 확인하기 위함
   • 이때 자바의 우선순위 큐는 최소힙 이므로 -1을 곱하여 넣고, 뺄때 -1을 곱하면 쉽게 최대 힙 방식을 구현할 수 있습니다.

소스코드

import java.util.*;

class Solution {
    static class Program {
        int pri;
        int idx;
        
        public Program(int pri, int idx) {
            this.pri = pri;
            this.idx = idx;
        }
    }
        
    public int solution(int[] priorities, int location) {
        int answer = 0;
        Queue<Program> q = new LinkedList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int i = 0; i < priorities.length; i++) {
            q.offer(new Program(priorities[i], i));
            pq.offer(-1 * priorities[i]);
        }
        
        while(!q.isEmpty()) {
            Program program = q.poll();
            int temp = -1 * pq.poll();
            if (program.pri == temp) {
                answer += 1;
                if(program.idx == location) {
                    break;
                }
            } else {
                q.offer(program);
                pq.offer(-1 * temp);
            }
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12909

문제

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예

입출력 예 설명

입출력 예 #1,2,3,4
문제의 예시와 같습니다.

문제 해결을 위한 과정

이 문제는 스택으로 풀 수 있지만 각 괄호를 +1, -1로 대체한다면 조금 더 효율적으로 해결할 수 있습니다.

1. 카운팅 변수 설정: 여는 괄호를 담을 스택 대신, 숫자를 셀 number 변수를 0으로 초기화합니다.
2. 괄호 순회: 문자열을 한 글자씩 확인합니다.
   • ( 를 만나면: 숫자를 +1 합니다. 
   • ) 를 만나면: 숫자를 -1 합니다. 
3. 탈출 조건 : 만약 루프 중간에 number가 음수가 된다면? 이것은 괄호의 짝이 맞지 않는 경우이므로 즉시 false를 반환합니다.
4. 최종 확인: 모든 루프가 끝난 뒤 number가 딱 0이어야만 모든 짝이 맞은 것입니다. 0이 아니라면 false를 반환합니다.

소스코드

import java.util.*;

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

https://school.programmers.co.kr/learn/courses/30/lessons/42586

문제

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

입출력 예 설명

입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

문제 해결을 위한 과정

1. 큐 세팅: 모든 작업의 진도(progresses)와 속도(speeds)를 각각 큐에 담습니다.
2. 날짜 시뮬레이션: day를 1일부터 시작해서 매 루프마다 1씩 증가시킵니다.
3. 배포 조건 확인:
   • 큐의 맨 앞 작업이 현재 >= 100인지 확인합니다. (배포 가능 판단)
   • 조건이 충족되면 그날 배포될 수 있는 모든 작업을 poll() 하면서 숫자를 셉니다.
4. 결과 기록: 배포된 작업이 있다면 리스트에 추가합니다.

소스코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        ArrayList<Integer> arr = new ArrayList<>();
        
        while(true) {
            if(progresses.length == 0)
                break;
            for(int i = 0; i < progresses.length; i++) {
                progresses[i] += speeds[i];
            }
            
            Queue<Integer> q1 = new LinkedList<>();
            Queue<Integer> q2 = new LinkedList<>();
            
            for(int i = 0; i < progresses.length; i++) {
                q1.offer(progresses[i]);
                q2.offer(speeds[i]);
            }
            
            int num = 0;
            while(!q1.isEmpty()) {
                if(q1.peek() >= 100) {
                    num += 1;
                    q1.poll();
                    q2.poll();
                } else {
                    break;
                }
            }
            if(num > 0) {
                arr.add(num);
            }
            
            progresses = new int[q1.size()];
            speeds = new int[q2.size()];
            
            for(int i = 0; i < progresses.length; i++) {
                progresses[i] = q1.poll();
                speeds[i] = q2.poll();
            }
        }
        
        int[] answer = new int[arr.size()];
        for(int i = 0; i < arr.size(); i++) {
            answer[i] = arr.get(i);
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12906?language=java

문제

문제 설명

import java.util.*;

public class Solution {
    static Stack<Integer> stack = new Stack<>();
    
    public int[] solution(int []arr) {
        for(int i = 0; i < arr.length; i++) {
            if(stack.isEmpty() || stack.peek() != arr[i]) {
                stack.add(arr[i]);
            }
        }
        
        int[] answer = new int[stack.size()];
        int idx = 0;
        for(Integer n : stack) {
            answer[idx++] = n;
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/42579

문제

문제 설명
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

속한 노래가 많이 재생된 장르를 먼저 수록합니다.
장르 내에서 많이 재생된 노래를 먼저 수록합니다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항
genres[i]는 고유번호가 i인 노래의 장르입니다.
plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
장르 종류는 100개 미만입니다.
장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
모든 장르는 재생된 횟수가 다릅니다.
입출력 예
genres plays return
["classic", "pop", "classic", "classic", "pop"] [500, 600, 150, 800, 2500] [4, 1, 3, 0]
입출력 예 설명
classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

고유 번호 3: 800회 재생
고유 번호 0: 500회 재생
고유 번호 2: 150회 재생
pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

고유 번호 4: 2,500회 재생
고유 번호 1: 600회 재생
따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.

문제 해결을 위한 과정

이 문제는 관리해야 할 데이터가 많기 때문에 여러 변수의 정렬 이 중요 합니다.

1. 데이터 구조 설계: 각 곡의 정보(장르명, 장르 총 재생수, 개별 재생수, 고유 번호)를 한 번에 담을 수 있는 Gen 클래스를 만들었습니다.
2. 장르별 총합 계산: 첫 번째 반복문에서 HashMap을 사용해 각 장르가 총 몇 번 재생되었는지 합계를 구합니다.
3. 객체 리스트 생성: 각 노래를 Gen 객체로 생성하여 리스트에 담습니다. 이때 미리 구해둔 장르 총 재생수 정보도 함께 넣어줍니다.
4. 다중 조건 정렬: Comparable의 compareTo를 오버라이딩하여 문제의 우선순위(장르 총 재생수 desc -> 곡 재생수 desc -> 고유 번호 asc)대로 정렬합니다.
5. 두 개씩 선택: 정렬된 리스트를 순회하며 check용 Map을 이용해 각 장르당 최대 2곡까지만 결과 리스트에 담아줍니다.

소스코드

import java.util.*;

class Solution {
    static class Gen implements Comparable<Gen> {
        String name; // 장르명
        int cnt;     // 재생횟수
        int cnt2;    // 곡별 재생횟수
        int idx;     // 고유값
        
        public Gen(String name, int cnt, int cnt2, int idx) {
            this.name = name;
            this.cnt = cnt;
            this.cnt2 = cnt2;
            this.idx = idx;
        }
        
        @Override
        public int compareTo(Gen o) {
            int val = 0;
            val = o.cnt - this.cnt;
            if(val == 0) {
                val = o.cnt2 - this.cnt2;
                if(val == 0) {
                    return this.idx - o.idx;
                } else {
                    return val;
                }
            } else {
                return val;
            }
        }
    }
    
    static HashMap<String, Integer> map = new HashMap<>();
    static HashMap<String, Integer> check = new HashMap<>();
    static ArrayList<Gen> list1 = new ArrayList<>();
    
    public int[] solution(String[] genres, int[] plays) {
        ArrayList<Integer> ans = new ArrayList<>();
        
        for(int i = 0; i < genres.length; i++) {
            if(map.containsKey(genres[i])) {
                int num = map.get(genres[i]);
                num += plays[i];
                map.put(genres[i], num);
            } else {
                map.put(genres[i], plays[i]);
            }
        }
        
        for(int i = 0; i < genres.length; i++) {
            list1.add(new Gen(genres[i],  map.get(genres[i]), plays[i], i));
        }
        
        Collections.sort(list1);
        
        for(int i = 0; i < list1.size(); i++) {
            if(!check.containsKey(list1.get(i).name)) {
                ans.add(list1.get(i).idx);
                check.put(list1.get(i).name, 1);
            } else {
                if(check.get(list1.get(i).name) < 2) {
                    ans.add(list1.get(i).idx);
                    check.put(list1.get(i).name, check.getOrDefault(list1.get(i).name, 0) + 1);
                } else {
                    continue;
                }
            }
        }

        int[] answer = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++) {
            answer[i] = ans.get(i);
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=java

문제

문제 설명
코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.

종류 이름
얼굴 동그란 안경, 검정 선글라스
상의 파란색 티셔츠
하의 청바지
겉옷 긴 코트
코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
코니는 하루에 최소 한 개의 의상은 입습니다.
코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항
clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
같은 이름을 가진 의상은 존재하지 않습니다.
clothes의 모든 원소는 문자열로 이루어져 있습니다.
모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
입출력 예
clothes return
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]] 5
[["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]] 3

문제 해결을 위한 과정

이 문제는 의상이 종류별로 몇 개가 있는지를 파악 후 계산을 하면 됩니다.

의상 종류별 카운팅 : clothes[i][1]이 의상의 종류이므로 Key로 삼아 HashMap에 저장 합니다.

조합 계산 : 각 의상 종류별로 (의상 개수 + 1)을 곱해줍니다. 여기서 +1은 해당 종류의 옷을 입지 않는 경우를 의미 합니다.

최소 한 개는 입기: 1을 빼는 이유는 전체 종류의 옷을 하나도 입지 않는 경우가 포함되어있기 때문 입니다.

소소코드

import java.util.*;

class Solution {
    static HashMap<String, Integer> map = new HashMap<>();

    public int solution(String[][] clothes) {
        int answer = 1;

        for(int i = 0; i < clothes.length; i++) {
            map.put(clothes[i][1], map.getOrDefault(clothes[i][1], 0) + 1);
        }

        for(String str : map.keySet()) {
            answer *= (map.get(str) + 1);
        }
        answer -= 1;
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/42577

문제

문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.
입출력 예제
phone_book return
["119", "97674223", "1195524421"] false
["123","456","789"] true
["12","123","1235","567","88"] false
입출력 예 설명
입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

문제 해결을 위한 과정

이 문제는 번호 하나하나를 다른 번호와 일일이 비교하면 O(N^2)의 시간이 걸려 효율성 테스트를 통과할 수 없습니다. 따라서 Hash를 사용해서 문제를 풀어야 합니다.

1. 전체 번호 해싱: 우선 모든 전화번호를 HashMap에 담습니다. 이때 getOrDefault를 사용하여 각 번호가 존재함을 기록합니다.
2. 접두어 검사: 다시 전체 번호를 하나씩 꺼내어(phone), 해당 번호의 첫 글자부터 마지막 직전 글자까지 잘라보며(substring) 그 자른 문자열이 우리 Map에 존재하는지 확인합니다.
3. 즉시 반환: 만약 자른 문자열이 Map에 있다면, 어떤 번호가 다른 번호의 접두어라는 뜻이므로 즉시 false를 반환하고 종료합니다.

키포인트

1. 주의점: substring을 이용하여 map에 있는지 검사 시 범위를 phone.length() 직전까지 설정해야 자기 자신과 똑같은 번호를 찾는 실수를 방지할 수 있습니다.

소스코드

import java.util.*;

class Solution {
    static HashMap<String, Integer> map = new HashMap<>();
    
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        for(String phone : phone_book) {
            map.put(phone, map.getOrDefault(phone, 0) + 1);
        }
        
        for(String phone : phone_book) {
            for(int i = 0; i < phone.length(); i++) {
                if(map.containsKey(phone.substring(0, i)))
                    return false;
            }
        }
        return answer;
    }
}