해시, 스택/큐, 힙, 정렬, 완전탐색, DFS/BFS

 

---

해시

---

완주하지 못한 선수

 

import java.util.HashMap;
class Solution {
    public String solution(String[] participant, String[] completion) {
    
    
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
            }
        }
        return answer;
        
        
    }
}

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
    
    
        Arrays.sort(participant);
        Arrays.sort(completion);
        int i;
        for ( i=0; i<completion.length; i++){

            if (!participant[i].equals(completion[i])){
                return participant[i];
            }
        }
        return participant[i];
        
        
    }
   
}

 

전화번호 목록

 

    public boolean solution(String[] phone_book) {

        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < phone_book.length; i++)
            map.put(phone_book[i], i);
        

        for(int i = 0; i < phone_book.length; i++) {
            for(int j = 0; j < phone_book[i].length(); j++) {
                if(map.containsKey(phone_book[i].substring(0,j))) {
                    return false;
                }
            }
        }
        return true;
    }

 

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

 

 

 

위장

입력값

    static String[][] clothes ={{"yellowhat", "headgear"}, 
                                {"bluesunglasses", "eyewear"}, 
                                {"green_turban", "headgear"}}; // 정답은 5
                                
    static String[][] clothes ={{"crowmask", "face"}, 
                                {"bluesunglasses", "face"}, 
                                {"smoky_makeup", "face"}}; // 정답은 3

 

결과 1 

hashmap 의 getOrDefault  사용

    public static int solution(String[][] clothes) {

        int answer = 1;
        HashMap<String, Integer> hashMap = new HashMap<>(); // "옷카테고리", "옷종류"
        for(int i =0;i< clothes.length; i++){
            hashMap.put(clothes[i][1], hashMap.getOrDefault(clothes[i][1], 0)+1);
        }
        
        for(int val:hashMap.values()){
            answer = answer * (val+1);
        }
        return answer-1;
        
    }

 

결과2

함수적 풀이

import java.util.*;
import static java.util.stream.Collectors.*;

class Solution {
    public int solution(String[][] clothes) {
        return Arrays.stream(clothes)
                .collect(groupingBy(p -> p[1], mapping(p -> p[0], counting())))
                .values()
                .stream()
                .collect(reducing(1L, (x, y) -> x * (y + 1))).intValue() - 1;
    }
}

 

 

베스트 엘범

 

 

---

스택/큐

---

 

기능개발

 

 

프린터

 

    static int[] priorities = {2, 1, 3, 2};
    static int location = 2;
//    // 	1

//    static int[] priorities = {1, 1, 9, 1, 1, 1};
//    static int location = 0;
    // 	5

    public static int solution(int[] priorities, int location) {
        int answer = 0;

        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i<priorities.length; i++){
            int priArray[] = new int[2];
            priArray[0] = i;
            priArray[1] = priorities[i];
            queue.add(priArray); // 큐에 대기문서들을 차례로 담는다.
        }

        Arrays.sort(priorities);
        int[] anw = new int[priorities.length];    // location, priority
        // 큐에서 하나씩 꺼내면서 남은 대기목록중에서 큰게 있으면 맨뒤 아니면 꺼내서 결과 배열에 담는다.
        int idx = priorities.length-1;
        int idxAw=0;
        while (queue.size()!=0){
            int[] num = queue.poll();

            // 가장 큰수보다 작으면, 큐 맨뒤에 다시 담는다.
            if(num[1]<priorities[idx]){
                queue.offer(num);

            }else {// 가장 큰수랑 같거나 크면, 정답 배열에 담는다
                anw[idxAw] = num[0];
                idxAw = idxAw+1;
                idx = idx -1;
            }
        }

        for(int i = 0; i<anw.length; i++){
            if(anw[i]==location) return (i+1);
        }


        return answer;
    }

 

 

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        int l = location;

        Queue<Integer> que = new LinkedList<Integer>();
        for(int i : priorities){
            que.add(i);
        }

        Arrays.sort(priorities);
        int size = priorities.length-1;


        while(!que.isEmpty()){
            Integer i = que.poll();
            if(i == priorities[size - answer]){
                answer++;
                l--;
                if(l <0)
                    break;
            }else{
                que.add(i);
                l--;
                if(l<0)
                    l=que.size()-1;
            }
        }

        return answer;
    }
}

 

 

 

다리를 지나는 트럭

 

 

 

주식가격

 

 

---

힙

---

 

더 맵게

 

 

디스크 컨트롤러

 

 

이중우선순위큐

---

정렬

---

k번째 수

 

    static int[] array = {1, 5, 2, 6, 3, 7, 4};
    static int[][] commands = {{2, 5, 3}, {4, 4, 1}, {1, 7, 3}};
    //답: {5, 6, 3}

정답 1

    public static int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        for(int i =0; i< commands.length; i++){
            int [] com = commands[i];
            int [] first = Arrays.copyOfRange(array, com[0]-1, com[1]);
            Arrays.sort(first);
            answer[i] = first[com[2]-1];
        }

        return answer;
    }

 

 

 

가장 큰 수

 

 

H-Index

 

 

 

 

---

완전탐색

---

 

모의고사

 

 

소수찾기

 

 

카펫

 

 

 

---

깊이/너비 우선 탐색(DFS/BFS)

---

타겟넘버

 

 

네트워크

 

 

단어변환

 

 

여행경로