BangBang's Devlogs

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

여러 자료구조를 연결하여 구현하였음

문제 설명 순서의 로직을 참고하여 그 순서대로 구현하려고 하였음

문제의 1번 과정인 장르별 총 플레이수 별로 저장한 자료구조와
문제의 2,3번 과정에 필요한 전체 노래 자료구조를 구현하여 각각을 정렬함

그 후 베스트 앨범에 들어갈 수 있도록 각 장르별 2곡씩 뽑음

* Comparable의 compareTo를 사용하여 내림차순, 오름차순을 구현하였음
오름 차순의 경우 o1.compareTo(o2)
내림 차순의 경우 o2.compareTo(o1)

import java.util.*;
// 베스트앨범
// 장르별 가장 많이 재생된 노래 2개씩 모아 베스트 앨범 출시
class Solution {
    static class Song implements Comparable<Song>{
        int sId;
        String genre;
        int play;
        
        Song(int sId, String genre, int play){
            this.sId = sId;
            this.genre = genre;
            this.play = play;
        }
        
        @Override
        public int compareTo(Song o){
            // 재생 수 내림차순
            int result = (o.play) - (this.play);
            
            // 재생수 같을 때 고유 번호 오름차순
            if(result == 0){
                result = (this.sId) - (o.sId);
            }
            
            return result;
        }
    }
    
    // 입력 테스트케이스 크기가 10^4
    public int[] solution(String[] genres, int[] plays) {
        
        // 해쉬 맵으로 genres별 총 재생 수 put
        // classic 1450    pop 3100
        Map<String, Integer> map = new HashMap<>();
        for(int i=0; i<genres.length; i++){
            if(map.containsKey(genres[i])){
                map.put(genres[i], (map.get(genres[i]) + plays[i]));
            }
            else{
                map.put(genres[i], plays[i]);
            }
        }
        
        // value(총 재생 수)에 따른 내림차순 정렬 (pop | classic)
        List<String> genreKeyList = new ArrayList<>(map.keySet());
        Collections.sort(genreKeyList, (o1, o2) -> (map.get(o2).compareTo(map.get(o1))));
        /*for(String key : genreKeyList) {
			System.out.println("key : " + key + " / " + "value : " + map.get(key));
		}*/
        
        // Song 클래스 만들어서 Array List에 다 넣기 (id, genres, plays)
        List<Song> songList = new ArrayList<>();
        for(int i=0; i<genres.length; i++){
            songList.add(new Song(i, genres[i], plays[i]));
        }
        // plays 역순 정렬 시키기 & id 작은 순(Song 클래스에서 compareTo 작성)
        Collections.sort(songList);
        /*for(Song song : songList){
            System.out.println(song.sId + ", " + song.play);
        }*/
        
        // 정렬된 genreKeyList(장르) 순서대로 // 플레이수 가장 많은 2개(미리정렬해놓은) 꺼내서 result List에 add 
        List<Integer> result = new ArrayList<>();
        int cnt;
        for(String key: genreKeyList){
            cnt = 0;
            for(Song song: songList){
                if(key.equals(song.genre)){
                    result.add(song.sId);
                    cnt++;
                }
                if(cnt==2)
                    break;
            }
        }
        
        // ArrayList result -> Array answer
        int[] answer = new int[result.size()];
        for(int i=0; i<answer.length; i++){
            answer[i] = (int)result.toArray()[i];
        }
        
        return answer;
    }
}

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

큐를 사용하여 구현함

해당 기능 완료하는데 걸리는 날을 미리 계산하여 Queue에 저장함

import java.util.*;
// 기능개발
// 큐 사용(병렬 스케줄링)
// 각각의 기능 개발
// 순서대로 배포 되야함
class Solution {
    
    public int[] solution(int[] progresses, int[] speeds) {
        
        ArrayList<Integer> results = new ArrayList<>();
        
        // 해당 기능 완료하는데 걸리는 날 Queue
        Queue<Integer> q = new LinkedList<>();
        int day = 0;
        for(int i=0; i<progresses.length; i++){
            if((100 - progresses[i]) % speeds[i] == 0 ){
                day = (100 - progresses[i]) / speeds[i];
            }
            else{
                day = (100 - progresses[i]) / speeds[i];
                day += 1;
            }
            q.offer(day);
        }
        
        // 7 3 9
        int cnt;
        while(!q.isEmpty()){
            // 기능 배포 수
            cnt = 0;
            // 첫 번째 기능 걸리는 날보다 작은 날 까지 배포 가능하므로 cnt++
            for(int i=0; i<q.size(); i++){
                if(q.peek() >= (int)q.toArray()[i]){
                    cnt++;
                }else{
                    break;
                }
            }
            
            // 가능한 기능 전부 배포 했으므로 poll
            for(int i=0; i<cnt; i++){
                q.poll();
            }
            
            // 몇 개의 기능 배포했는지 저장
            results.add(cnt);
        }
        
        // ArrayList -> array 변환
        int[] answer = new int[results.size()];
        int idx = 0;
        for(int result : results){
            answer[idx++] = result;
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42585

스택을 이용하여 구현하였음
쇠막대기가 잘라지는 규칙을 찾아내면 쉽게 구현할 수 있는 문제임

먼저 () 나오는 부분은 레이저 이므로 l로 바꿔서 처리하였음
그리고 스택에 넣으면서
1. (가 나오면 push 해주고
2. l이 나오면 레이저가 지금까지 쌓인 ( 갯수 만큼 쇠막대기를 자름
3. )이 나오면 pop을 해주고 쇠막대기 끝 부분이므로 answer ++ 해줌 

import java.util.*;
// 쇠막대기
// 쇠막대기 잘라지는 규칙을 찾아내는게 중요
class Solution {
    public int solution(String arrangement) {
        int answer = 0;
        
        // () 찾아서 ㅣ로 바꿔주기
        arrangement = arrangement.replace("()", "l");
        
        Stack<Character> stack = new Stack<>();
        
        for(int i=0; i<arrangement.length(); i++){
            // ( 가 나오면 push
            if(arrangement.charAt(i)=='('){
                stack.push(arrangement.charAt(i));
            }
            // l 가 나오면 laser인데 stack size 만큼 잘라짐
            else if(arrangement.charAt(i)=='l'){
                answer += stack.size();
            }
            // ) 가 나오면 pop인데 1개 잘라짐
            else{
                answer++;
                stack.pop();
            }
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42584

첫 번째 풀이

큐를 이용하여 구현하였음

각 주식 가격이 언제까지 떨어지지 않는지 시간을 재는 방식을 이용함

코드

import java.util.*;
// 주식가격

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        Queue<Integer> q = new LinkedList<>();
        // 주식 가격 queue에 넣기
        for(int i=0; i<prices.length; i++){
            q.offer(prices[i]);
        }
        
        //peek()에서 prices들과 가격 비교 time ++
        int idx = 0;
        int time = 0;
        while(!q.isEmpty()){
            time = 0;
            for(int i=idx+1; i<prices.length; i++){
                if(q.peek() <= prices[i]){
                    time++;
                }
                else{
                	time++;
                    break;
                }
            }
            q.poll();
            answer[idx] = time;
            idx ++;
        }
        
        return answer;
    }
}

두 번째 풀이

큐를 이용하지 않고 구현해봄

코드

import java.util.*;

// 주식가격
class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        int time;
        
        for(int i=0; i<prices.length; i++){
            
            time=0;
            for(int j=i+1; j<prices.length; j++){
                if(prices[i] <= prices[j]){
                    time++;
                }
                else{
                    time++;
                    break;
                }
            }
            answer[i] = time;
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42587

큐를 이용하여 구현하였음

flag를 둬서 뒤의 순서에 우선 순위가 더 높은 경우가 있는지 없는지 체크하고 그에 따른 로직을 구현하였음
location 위치를 계속 잘 따라가주고 몇 번째로 인쇄되는지 값을 가지는 answer 변수는 프린터 큐에서 poll이 될때마다 증가시켜줌  

import java.util.*;
// 프린터
// 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지
class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i=0; i<priorities.length; i++){
            q.offer(priorities[i]);
        }
        
        while(!q.isEmpty()){
        	// 가장 앞에 있는 순서의 우선 순위보다 더 큰 것 있는지 체크
            boolean flag = false;
            for(int i=1; i<q.size(); i++){
            	if(q.peek() < (int)(q.toArray()[i])) {
            		flag = true;
            		break;
            	}
            }
            
            for(int i=0; i<q.size(); i++) {
            	System.out.print(q.toArray()[i] + ",");
            }
            System.out.println();
            
            // priorities에 우선 순위가 더 큰 경우가 있는 경우
            if(flag){
                // 해당 위치의 값을 맨 뒤로 보냄
                q.offer(q.poll());
                
                // poll을 했으므로 해당 위치의 값을 하나씩 앞으로 땡기는데
                location--;
                // location < 0 이면 location 값이 제일 뒤로 갔으므로 q.size()-1
                if(location < 0){
                    location = q.size()-1;
                }
            }
            // q.peek()이 우선 순위 젤 크거나 같은 경우
            else{
            	// location이 0일 경우가 가장 앞까지 온 경우
                if(location == 0){
                    answer++;
                    q.clear();
                }
                else{
                    q.poll();
                    answer++;
                    // poll을 했으므로 해당 위치의 값을 하나씩 앞으로 땡기는데
                    location--;
                    // location < 0 이면 location 값이 제일 뒤로 갔으므로 q.size()-1
                    if(location < 0){
                        location = q.size()-1;
                    }
                }
            }
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42583

첫 번째 풀이

해결 방안

큐를 제대로 이해하고 있으면 풀 수 있는 문제였음

큐와 문제의 주어진 조건을 이용해서 푸는 문제.
각 트럭이 다리 길이 갔을 때 나가는 걸 체크하기 위해 enterTime을 활용

코드

import java.util.*;
// 다리를 지나는 트럭
// 모든 트럭이 다리를 건너는데 걸리는 시간

class Solution {
    static class Truck{
        int enterTime;
        int weight;
        
        Truck(int enterTime, int weight){
            this.enterTime = enterTime;
            this.weight = weight;
        }
    }
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
        int totalWeightOnBridge = 0;
        
        // 대기 트럭
        Queue<Truck> waiting_truck = new LinkedList<Truck>();
        // 다리를 건너는 트럭
        Queue<Truck> crossing_truck = new LinkedList<Truck>();
        
        // 대기 트럭 입력
        for(int i=0; i<truck_weights.length; i++){
            waiting_truck.offer(new Truck(0, truck_weights[i]));
        }
        
        //매 초 일어나는 동작 정의(대기 트럭과 다리를 건너는 트럭이 둘다 비어있지 않으면 실행)
        while(!(waiting_truck.isEmpty() && crossing_truck.isEmpty())){
            time ++;
            
            // 다리를 건너는 트럭이 있을 때
            if(!crossing_truck.isEmpty()){
                // 1. 다리를 나가야하는 트럭이 있는지 확인
                // 1.1. 해당 트럭의 (현재 시간-들어간 시간) >= bridege_length 이면 나감
                if((time - crossing_truck.peek().enterTime) >= bridge_length){
                    totalWeightOnBridge -= crossing_truck.peek().weight;
                    crossing_truck.poll();
                }
            }
            
            if(!waiting_truck.isEmpty()){
            	// 2. 대기 트럭이 다리를 올라가도 되는지 확인
            	if(totalWeightOnBridge + waiting_truck.peek().weight <= weight){
            		totalWeightOnBridge += waiting_truck.peek().weight;
            		
            		crossing_truck.offer(new Truck(time, waiting_truck.peek().weight));
            		waiting_truck.poll();
            	}
            }
        }
        
        return time;
    }
}

두 번째 풀이

해결 방안

첫 번째 풀이와 비슷하게 해결

코드

import java.util.*;

// 다리를 지나는 트럭
// 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려함
// 모든 트럭이 다리를 건너려면 최소 몇초가 걸리는지 알아내야함 (트럭은 1초에 1만큼 움직임)
class Solution {
    
    class Truck{
        public int weight; // 해당 트럭 무게
        public int enterTime; // 다리에 진입한 시간
        
        Truck(int weight, int enterTime){
            this.weight = weight;
            this.enterTime = enterTime;
        }
    }
    
    // bridge_length: 다리 길이, weight: 다리가 버틸 수 있는 무게
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
        
        // 대기 트럭
        Queue<Truck> waitingQ = new LinkedList<>();
        // 다리를 건너는 트럭
        Queue<Truck> crossingQ = new LinkedList<>();
        
        // 대기 트럭에 트럭 넣어주기
        Truck truck;
        for(int i=0; i<truck_weights.length; i++){
            truck = new Truck(truck_weights[i], -1);
            waitingQ.offer(truck);
        }
        
        // 다리를 지난 트럭은 대기 트럭과 다리를 건너는 트럭의 Queue가 다 empty인 경우임(while의 조건)
        int totalWeight = 0; // 다리에 올라와있는 트럭들의 무게
        int truck_weight;
        int truck_enterTime;
        Truck waitingTruck;
        Truck crossingTruck;
        while(!waitingQ.isEmpty() || !crossingQ.isEmpty()){
            // 시간 증가에 따른 트럭 움직임
            time ++;
            
            // 다리를 건너는 트럭 enterTime 확인해서 다리를 다 지났는지 확인
            // 꼭 먼저 확인해줘야 함 (다리를 건너던 트럭이 지나가서 대기 트럭이 올라올 수 있으므로)
            if(!crossingQ.isEmpty()){
                crossingTruck = crossingQ.peek();
                truck_enterTime = crossingTruck.enterTime;
                truck_weight = crossingTruck.weight;
                
                if(time - truck_enterTime >= bridge_length){
                    crossingQ.poll();
                    totalWeight -= truck_weight;
                }
            }
            
            // 대기 트럭이 다리에 올라올 수 있는지 무게 확인해서 견딜 수 있는 무게이면 다리에 올리기
            if(!waitingQ.isEmpty()){
                waitingTruck = waitingQ.peek();
                truck_weight = waitingTruck.weight;
                truck_enterTime = time;
                
                if(truck_weight + totalWeight <= weight){
                    crossingTruck = new Truck(truck_weight, truck_enterTime);
                    crossingQ.offer(crossingTruck);
                    
                    waitingQ.poll();
                    totalWeight += truck_weight;
                }
            }
            
        }
        
        // while 조건을 다 빠져나오면 모든 트럭이 다리를 지나간거임
        return time;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42578

수학적인 접근이 필요한 문제임

의상 종류의 수와 종류들의 각 갯수를 가지고 풀 수 있는 문제임
해쉬를 이용해서 각 의상 종류의 갯수들을 저장해줌
그리고 경우의 수를 구해줌

* for(String key :  keys) 는 keys에 있는 값들을 key값에 넣는 것이다.
(keys에 값이 더이상 없을때까지)

import java.util.*;
//위장
// [의상의 이름, 의상의 종류]
// 최소 한 개 이상의 의상
// 서로 다른 옷의 조합의 수 return
// 같은 종류의 의상은 조합 불가
class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        
        // 의상 종류끼리 갯수 저장
        Map<String, Integer> clothesKindsMap = new HashMap<>();
        String clothesKindsName;
        for(int i=0; i<clothes.length; i++){
            clothesKindsName = clothes[i][1];
            
            if(clothesKindsMap.containsKey(clothesKindsName)){
                clothesKindsMap.put(clothesKindsName, clothesKindsMap.get(clothesKindsName) + 1);
            }
            else{
                clothesKindsMap.put(clothesKindsName, 1);
            }
        }
        
        // 경우의 수 계산
        Set<String> keys = clothesKindsMap.keySet();
        
        int temp;
        answer = 1;
        for(String key : keys){
            // 해당 의상 종류 갯수(안 입는 경우 포함) 
            temp = clothesKindsMap.get(key) + 1;
            answer *= temp;
        }
        
        // 아무 것도 안 입은 경우 제외
        answer--;
        
        return answer;
    }
}

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

해결 방안

String 라이브러리 활용이 중요함
접두어인 경우이므로 startsWith 함수를 썼으며 indexOf == 0 일 경우를 확인하는 방법도 가능함

코드

import java.util.*;

//전화번호 목록
// 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false, 그렇지 않으면 true 
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        for(int i=0; i<phone_book.length; i++){
            for(int j=0; j<phone_book.length; j++){
                if(i==j) continue;
                if(phone_book[j].startsWith(phone_book[i])){
                    answer = false;
                    break;
                }
            }
            if(!answer)
                break;
        }
        return answer;
    }
}