2024.05.28 ( Java )

changi123·2024년 5월 28일

알고리즘-codingTest

알고리즘 ( Java ) - codingTest

목록 보기

3/77

1. 베스트앨범 ( 프로그래머스 )

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

GitHub -> https://github.com/changi123/programmers/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/3/42579.%E2%80%85%EB%B2%A0%EC%8A%A4%ED%8A%B8%EC%95%A8%EB%B2%94/%EB%B2%A0%EC%8A%A4%ED%8A%B8%EC%95%A8%EB%B2%94.java

3LV 문제 너무 어렵다..

package problem_solving.hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class Programmers_42579 {

	public static void main(String[] args) {
		String [] genres = {"classic", "pop", "classic", "classic", "pop"};
		int [] plays = {500, 600, 150, 800, 2500};

		System.out.println(Arrays.toString(solution(genres, plays)));

	}
	public static int[] solution(String[] genres, int[] plays) {
		int[] answer = {};

		HashMap<String,Integer> playHm = new HashMap<>();
		HashMap<String, HashMap<Integer, Integer> >  keyVal= new HashMap<>();

		for(int i = 0 ; i < genres.length;i++) {
			if( !playHm.containsKey(genres[i])) {
				playHm.put(genres[i], plays[i]);
			}else {
				int play = playHm.get(genres[i]);
				playHm.put(genres[i], play+plays[i]);
			}

			if( keyVal.containsKey(genres[i])) {
				HashMap<Integer,Integer> hm= keyVal.get(genres[i]);
				hm.put(i, plays[i]);				
				keyVal.put(genres[i], hm);
			}else {
				HashMap<Integer,Integer> hm= new HashMap<>();
				hm.put(i, plays[i]);
				keyVal.put(genres[i], hm);
			}

		}

		TreeMap<Integer,String> sortPlay = new TreeMap<>(Collections.reverseOrder());
		for(String s : playHm.keySet()) {
			int num = playHm.get(s);
			sortPlay.put(num, s);
		}

        HashMap<String, List<Map.Entry<Integer, Integer>>> sortedKeyVal = new HashMap<>();
        for (String genre : keyVal.keySet()) {
            List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(keyVal.get(genre).entrySet());
            entries.sort((a, b) -> {
                if (b.getValue().equals(a.getValue())) {
                    return a.getKey().compareTo(b.getKey());
                } else {
                    return b.getValue().compareTo(a.getValue());
                }
            });
            sortedKeyVal.put(genre, entries);
        }


        ArrayList<Integer> list = new ArrayList<>();
        for(int num : sortPlay.keySet()) {
        	String g = sortPlay.get(num);
        	List<Entry<Integer, Integer>> m = sortedKeyVal.get(g);
        	int cnt = 0 ;
        	for(int i= 0 ; i < m.size() ; i++) {
        		if( cnt  == 2) {
        			break;
        		}
        		cnt++;
        		list.add(m.get(i).getKey());
        	}
        	
        }
		
        answer = new int[list.size()];
        for(int i= 0 ; i <list.size();i++) {
        	answer[i]=list.get(i);
        }

		return answer;
	}
}

2. 프로세스 ( 프로그래머스 )

Queue ( https://school.programmers.co.kr/learn/courses/30/lessons/42587 )

GitHub -> https://github.com/changi123/programmers/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/42587.%E2%80%85%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4/%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4.java

package problem_solving.queue;

import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Programmers_42587 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] priorities = {2, 1, 3, 2};
		int location = 2;
		System.out.println(solution(priorities, location));
	}
	public static int solution(int[] priorities, int location) {
		int answer = 0;
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		Queue<HashMap<Integer,Integer>> q = new LinkedList<>();
		int checkNum = priorities[location];
		for(int i= 0 ; i < priorities.length;i++) {
			pq.offer(priorities[i]);
			HashMap<Integer,Integer> h = new HashMap<>();
			if( i ==  location) {				
				h.put(priorities[i], 1);
			}else {
				h.put(priorities[i], 0);				
			}
			q.offer(h);
		}

		while(!pq.isEmpty()) {
			HashMap<Integer,Integer> h = q.peek();
			for(int num : h.keySet()) {
				int key = num;
				int value = h.get(key);
				int max = pq.peek();
				if( max == checkNum && value == 1) {
					answer++;
					return answer ; 
				}
				
				if( key == checkNum && key != max ) {
					q.offer(q.poll());
					break;
				}
				
				if( key != checkNum && key == max) {
					pq.poll();
					answer++;
					q.poll();
					break;
				}
				
				if( key == checkNum && max == key && value == 0 ) {
					q.poll();
					answer++;
					break;
				}
				if( key != checkNum && key != max) {
					q.offer(q.poll());
					break;
				}
			}

		}


		return answer;
	}
}

3. 크게 만들기 ( 백준 )

Stack ( https://www.acmicpc.net/problem/2812 )

GitHub -> https://github.com/changi123/Algorithm-And-Data_structure/blob/main/Algorithm/src/problem_solving/greedy/BaekJoon_2812.java

package problem_solving.greedy;

import java.util.Scanner;
import java.util.Stack;

public class BaekJoon_2812 {

	public static void main(String[] args) {
		Scanner sc  = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int r = Integer.parseInt(sc.next());

		StringBuilder sb = new StringBuilder(sc.next());

		Stack<Character> st = new Stack();
		for(int i= 0 ; i < sb.length(); i++) {
			char now = sb.charAt(i);
			while(!st.isEmpty() && now > st.peek() && r > 0 ) {
				st.pop();
				r--;
			}
			
			st.push(now);
			
		}
		
		while(r>0) {
			st.pop();
			r--;
		}
		StringBuilder result = new StringBuilder();
		while(!st.isEmpty()) {
			result.append(st.pop());
			
		}
		System.out.println(result.reverse());
	}

}