[알고리즘] Java 프로그래머스 고득점 kit

 

 

 

Hash

완주하지 못한 선수 - LV1

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

 

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        Map<String, Integer> map = new HashMap<>();
        
        for(String ath : participant){
            map.putIfAbsent(ath, 0);
            map.put(ath, (map.get(ath)+1));
        }
        
        for(String comp : completion){
            map.put(comp, (map.get(comp)-1));
        }
        
        
        for(String name : map.keySet()){
            if(map.get(name) != 0){
                answer = name;
            }
        }
        
        return answer;
    }
}

 

폰켓몬 - LV1

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

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        HashSet<Integer> set = new HashSet<>();
        int selectNum = nums.length;
        for(int mon : nums){
            set.add(mon);
        }
        
        answer = Integer.min(selectNum/2, set.size());
        
        return answer;
    }
}

 

 

 

전화번호 목록 - LV2

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

 

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {

        Arrays.sort(phone_book);

        for (int i = 0; i < phone_book.length - 1; i++) {
            if (phone_book[i + 1].startsWith(phone_book[i])) {
                return false;
            }
        }

        return true;
        
    }
}

 

 

 

의상 - LV2

 

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        HashMap<String, Integer> map = new HashMap<>();

        // 종류별 의상 수 세기
        for (String[] clothe : clothes) {
            map.put(clothe[1], map.getOrDefault(clothe[1], 0) + 1);
        }

        int answer = 1;
        for (int count : map.values()) {
            answer *= (count + 1); // 입는 경우 + 안 입는 경우
        }

        return answer - 1; // 아무것도 안 입는 경우 제외

    }
}

 

 

베스트 앨범 - LV3

 

시간없어서 감 잡은 것 같아서 풀다 말았다

기억할 포인트

- 복잡한 자료구조여도 차근차근 해보기

- Arrays.asList() -> 이거 굉장히 많이 쓰는 것 같다

 

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        HashMap<String, PriorityQueue<List<Integer>>> map = new HashMap<>();
        
        int i = 0;
        for(String genre : genres){
            // 우선순위 큐 내부에 [재생수, 인덱스] 추가
            map.putIfAbsent(genre, new PriorityQueue<>((o1, o2) -> {
                int comp = Integer.compare(o2.get(0), o1.get(0));
                if(comp == 0){
                    return Integer.compare(o1.get(1), o2.get(1));
                }
                return comp;
            }
            ));
            map.get(genre).add(Arrays.asList(plays[i], i));
                
            i++;
        }
        
        System.out.println(map);
        
        return answer;
    }
}

 

 

DFS

 

여행경로 - LV3

 

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

기억할 포인트

- 백트래킹 없이 poll로 추가하는 아이디어

- 해쉬맵 안에서 우선순위 큐를 사용하는 아이디어

import java.util.*;

class Solution {
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        

        Map<String, PriorityQueue<String>> map = new HashMap<>();
        
        
        for(String[] ticket : tickets){
            map.putIfAbsent(ticket[0], new PriorityQueue<>());
            map.get(ticket[0]).add(ticket[1]);
        }
        
        List<String> path = new ArrayList<>();
        List<String> result = new ArrayList<>();
        
        dfs(result, path, map, "ICN");
        answer = result.toArray(new String[0]);
        
        return answer;
    }
    
    public void dfs(
        List<String> result,
        List<String>path,
        Map<String, PriorityQueue<String>> map,
        String current
    ){
        
        while(map.containsKey(current) && !map.get(current).isEmpty()){
            String next = map.get(current).poll();
            dfs(result, path, map, next);
        }
        
        result.add(0, current);
        
        
    }
}

 

 

게임 맵 최단 거리 - LV2

기본적인 BFS

생각해보니 준비하면서 BFS를 하나도 안풀고 DFS만 풀었다 ㅋㅎㅎ

 

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        
        int n = maps.length;
        int m = maps[0].length;
        
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[] {0,0});
        
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        
        
        while(!q.isEmpty()){
            int[] curr = q.poll();
            int currentX = curr[0];
            int currentY = curr[1];
            
            for(int i=0; i<4; i++){
                int nextX = currentX + dx[i];
                int nextY = currentY + dy[i];
                
                if(0 > nextX || nextX >= n || 0 > nextY || nextY >= m) continue;
                if(maps[nextX][nextY] != 1) continue;
                
                maps[nextX][nextY] = maps[currentX][currentY] + 1;
                q.add(new int[] {nextX, nextY});
            }
            
        }
        
        
        if(maps[n-1][m-1] == 1){
            return -1;
        }
        return maps[n-1][m-1];
    }
}

 

 

 

룹즈랑 공모전 한다고 준비 더 못한게 아쉽지만,, 

가보자

찢고 오자!