[프로그래머스] 코딩테스트 고득점 Kit (Java)

해시

완주하지 못한 선수 (Lv1)

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";

        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(String name : participant){
            if(map.get(name) == null){
                map.put(name, 1);
            } else {
                int cnt = map.get(name) + 1 ;
                map.put(name, cnt);
            }
        }
        
        for(String name :  completion){
            int cnt = map.get(name) + 1 ;
            map.put(name, cnt);
        }
        
        Iterator<String> iter = map.keySet().iterator();
        while(iter.hasNext()){
            String name = iter.next();
            if(map.get(name) % 2 != 0){
                answer = name;
            }
        }
        
        return answer;
    }
}

 

 

전화번호 목록 (Lv2)

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        HashMap<String, Integer> hm = new HashMap<String, Integer>();
        
        hm.put(phone_book[0], phone_book[0].length());
        
        for(int i = 1; i < phone_book.length; i++){
            for(int j = 1 ; j < phone_book[i].length(); j++){
                if(hm.get(phone_book[i].substring(0, j)) != null){
                    return false;
                }
            }
            hm.put(phone_book[i], phone_book[i].length());
        }
        
        return answer;
    }
}

위장 (Lv2)

2021.11.21 - [Problem Solving/Programmers] - [프로그래머스] 위장 (Java)

베스트앨범 (Lv3)

2021.11.30 - [Problem Solving/Programmers] - [프로그래머스] 베스트앨범 (Java)

 

스택/큐

기능개발 (Lv2)

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] answer = {};
        List<Integer> answerList = new ArrayList<Integer>();
        Stack<int[]> st = new Stack<int[]>();
         
        for(int i = progresses.length-1; i >= 0; i--){
            st.push(new int[] {progresses[i], speeds[i]});
        }
        
        while(!st.isEmpty()){            
            int[] target = st.pop();
            int itemCnt = 1;
            int progress = target[0];
            int speed = target[1];
            int days = (100-progress)/speed;
            if((100-progress)%speed != 0) days++;
            
            while(!st.isEmpty()){
                if(isCompleteNextItem(st, days)){
                   st.pop(); 
                   itemCnt++;
                } else {
                    break;
                }
            }
            answerList.add(itemCnt);
        }
        
        return answerList.stream().mapToInt(x->x).toArray();
    }
    
    public static boolean isCompleteNextItem(Stack<int[]> st, int days) {
        int[] target = st.peek();    
        int progress = target[0];
        int speed = target[1];

        if((progress + speed*days) >= 100){
            return true;
        }
        return false;
    }
    
}

프린터 (Lv2)

import java.util.*;

class Document{
    int location; // 0~99
    int priority; // 1~9
    
    public Document(int location, int priority){
        this.location = location;
        this.priority = priority;
    }
}

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        int max = 0;
        ArrayList<Integer> list = new ArrayList<Integer>();
        Queue<Document> queue = new LinkedList<Document>();
        
        for(int i = 0; i < priorities.length; i++){
            int priority = priorities[i];
            list.add(priority);
            queue.offer(new Document(i, priority));
        }
       
        Collections.sort(list, new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                return b-a;
            }
        });
        while(!queue.isEmpty()){ 
            Document target = queue.poll();
            if(target.priority == list.get(0)){
                //Max
                list.remove(0);
                answer++;
                if(target.location == location) break;
            } else {
                queue.offer(target);
            }
        }
        return answer;
    }
}

다리를 지나는 트럭 (Lv2)

2021.10.20 - [Problem Solving/Programmers] - [프로그래머스] 다리를 지나가는 트럭 (Java)

주식가격 (Lv2)

import java.util.*; 

class Solution {
    public ArrayList<Integer> result;
    public int[] answer;
    public int price, time;
    
    public int[] solution(int[] prices) {
        result = new ArrayList<Integer>();
        for(int i = 0; i < prices.length; i++){
            price = prices[i];
            time = 0;
            for(int j = i+1; j < prices.length; j++){
                time++;
                if(price > prices[j]) break;
                
            }
            result.add(time);
        }
        
        return  result.stream().mapToInt(x -> x).toArray();
    }
}

 

힙(Heap)

더 맵게 (Lv2)

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pque = new PriorityQueue<Integer>();
        for(int i = 0; i < scoville.length; i++){
            pque.add(scoville[i]);
        }
        
        boolean isExist = false;
        while(!pque.isEmpty()){
            int first = pque.poll(); 
            if(first >= K){
                isExist = true;
                break;
            }
            if(pque.size() == 0) break;
            int second = pque.poll();
            pque.offer(first + (second*2));
            answer++;
        }
        
        if(!isExist){
            return -1;
        } 
        return answer;
    }
}

디스크 컨트롤러 (Lv3)

2021.11.17 - [Problem Solving/Programmers] - [프로그래머스] 디스크 컨트롤러 (Java)

이중우선순위큐 (Lv3)

2021.11.03 - [Problem Solving/Programmers] - [프로그래머스] 이중우선순위큐 (Java)

 

정렬

K번째수 (Lv1)

import java.util.*;

class Solution {

    public ArrayList<Integer> list, temp;
    public int[] answer;
    
    public ArrayList<Integer> getSubList(ArrayList<Integer> list, int fromIdx, int toIdx){
        ArrayList<Integer> result = new ArrayList<Integer>();
        for(int i = fromIdx; i < toIdx; i++){
            result.add(list.get(i));
        }
        return result;
    }    
    
    public int[] solution(int[] array, int[][] commands) {
        list = new ArrayList<Integer>();
        answer = new int[commands.length];
        for(int i = 0; i < array.length; i++){
            list.add(array[i]);
        }
        for(int i =0; i < commands.length; i++){
             temp = getSubList(list, commands[i][0] - 1, commands[i][1]);
             Collections.sort(temp);
             answer[i] = temp.get(commands[i][2]-1);
        }
        
        return answer;
    }
}

가장 큰 수 (Lv2)

2021.12.08 - [Problem Solving/Programmers] - [프로그래머스] 가장 큰 수 (Java)

H-Index (Lv2)

2021.10.21 - [Problem Solving/Programmers] - [프로그래머스] H-Index (Java)

 

완전탐색

모의고사 (Lv1)

import java.util.*;
public class Student implements Comparable<Student>{
    int id;
    int[] pattern, answers;
    int correctCnt;
    
    public Student(int id, int[] pattern, int[] answers){
        this.id = id;
        this.answers = answers;
        this.pattern = pattern;
        grade();
    }
    
    public void grade(){
       for(int i = 0; i < answers.length; i ++){
           if(answers[i] == pattern[i%pattern.length]) correctCnt++;
       } 
    }
    
    @Override
    public int compareTo(Student next){
        if(next.correctCnt - this.correctCnt == 0){
            return this.id - next.id;
        }
        return next.correctCnt - this.correctCnt;
    }
    
}

class Solution {
    ArrayList<Student> students;
    ArrayList<Integer> answer;
    public int[] solution(int[] answers) {
        
        students = new ArrayList<Student>();        
        students.add(new Student(1, new int[]{1, 2, 3, 4, 5}, answers));
        students.add(new Student(2, new int[]{2, 1, 2, 3, 2, 4, 2, 5}, answers));
        students.add(new Student(3, new int[]{3, 3, 1, 1, 2, 2, 4, 4, 5, 5}, answers));
        
        answer = new ArrayList<Integer>();
        Collections.sort(students);
        
        int max = students.get(0).correctCnt;
        answer.add(students.get(0).id);
        for(int i = 1; i < students.size(); i++){
            if(max > students.get(i).correctCnt){
                break;
            }
            answer.add(students.get(i).id);
        }
    
        return answer.stream().mapToInt(x->x).toArray();
    }
}

 

소수 찾기 (Lv2)

2021.10.23 - [Problem Solving/Programmers] - [프로그래머스] 소수 찾기 (Java)

카펫 (Lv2)

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {};
        
        int sum = (brown - 4)/2;
        System.out.println(sum);
        
        int W = 0, H = 0;
        for(int i = 1; i < sum; i++){
            if(yellow%i == 0 && yellow/i == sum-i){
                W = Math.max(i + 2, sum-i + 2);
                H = Math.min(i + 2, sum-i + 2);
                break;
            }
        }
        
        answer = new int[]{ W, H};
        
        return answer;
    }
}

 

탐욕법(Greedy)

체육복 (Lv1)

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;   
        boolean[] haveReserve = new boolean[n+1];
        for(int i= 0; i < reserve.length; i++){
            haveReserve[reserve[i]] = true;
        }        
        answer = n - lost.length;    
        
        Arrays.sort(lost);
        for(int i = 0; i < lost.length; i++){
            if(haveReserve[lost[i]]) { 
                haveReserve[lost[i]] = false;
                lost[i] = 0;
                answer++;
            }
        }
        
        for(int i = 0; i < lost.length; i++){
            if(lost[i] == 0) continue;
            int left = lost[i]-1;
            int right = lost[i]+1;
            if(left > 0 && haveReserve[left]){
                haveReserve[left] = false;
                answer++;
            } else if(right <= n && haveReserve[right]){
                haveReserve[right] = false;
                answer++;
            }
        }
        
        return answer;
    }
}

조이스틱 (Lv2)

 

큰 수 만들기 (Lv2)

 

구명보트 (Lv2)

2021.11.12 - [Problem Solving/Programmers] - [프로그래머스] 구명보트 (Java)

섬 연결하기 (Lv3)

2021.11.03 - [Problem Solving/Programmers] - [프로그래머스] 섬 연결하기 (Java)

 

단속카메라 (Lv3)

2021.11.02 - [Problem Solving/Programmers] - [프로그래머스] 단속카메라 (Java)

 

동적계획법(Dynamic Programming)

N으로 표현 (Lv3)

정수 삼각형 (Lv3)

2021.11.09 - [Problem Solving/Programmers] - [프로그래머스] 정수 삼각형 (Java)

등굣길 (Lv3)

2021.11.05 - [Problem Solving/Programmers] - [프로그래머스] 등굣길 (Java)

도둑질 (Lv4)

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

타겟 넘버 (Lv2)

class Solution {
    
    public int N, target, answer, num;
    public int[] numbers;
    
    public void recurFunc(int k){
        if(k == N){
            if(num == target){
                answer++;
            }
        } else {
            int temp = num;
            num += numbers[k];
            recurFunc(k+1);
            num = temp;
            num -= numbers[k];
            recurFunc(k+1);
            num+= numbers[k];
        }
    }
    
    public int solution(int[] numbers, int target) {
        this.N = numbers.length;
        this.target = target;
        this.numbers = numbers;
        
        recurFunc(0);
        
        return answer;
    }
}

네트워크 (Lv3)

class Solution {
    public int[][] computers;
    public int n, answer;
    public boolean[] visited;
    
    public void dfs(int vertex){
        visited[vertex] = true;
        
        for(int i = 0; i < n; i++){
            if(computers[vertex][i] == 0) continue;
            if(visited[i]) continue;
            dfs(i);
        }
    }
    
    public int solution(int n, int[][] computers) {
        this.n = n;
        this.computers = computers;
        this.visited = new boolean[n];
        
        for(int i = 0; i < n; i++){
            if(!visited[i]){
                dfs(i);
                answer++;
            }
        }
        
        return answer;
    }
}

 

단어 변환 (Lv3)

2021.11.02 - [Problem Solving/Programmers] - [프로그래머스] 단어 변환 (Java)

여행 경로 (Lv3)

2021.11.02 - [Problem Solving/Programmers] - [프로그래머스] 여행경로 (Java)

이분탐색

입국심사 (Lv3)

2021.10.29 - [Problem Solving/Programmers] - [프로그래머스] 입국심사 (Java)

징검다리 (Lv4)

2021.12.07 - [Problem Solving/Programmers] - [프로그래머스] 징검다리 (Java)

그래프

가장 먼 노드 (Lv3)

2021.11.06 - [Problem Solving/Programmers] - [프로그래머스] 가장 먼 노드 (Java)

순위 (Lv3)

2021.11.28 - [Problem Solving/Programmers] - [프로그래머스] 순위 (Java)

방의 개수 (Lv5)