[JAVA] 알고리즘 고득점 kit 스택 / 큐 + 정렬

 

 

또 오랜만에 자바다

 

 

 

정렬

 

문제 들어가기 전에 자바 정렬 정리

// 배열 오름차순
Arrays.sort(arr);

// 배열 내림차순 (객체만)
Arrays.sort(arr, Collections.reverseOrder());

// 배열 커스텀 정렬
Arrays.sort(arr, (a, b) -> a - b);

// 두개 key로
Arrays.sort(arr, (a, b) -> {
		if (a[0] == b[0]) return a[1]-b[1]
        return a[0] - b[0]
	}
);


// 리스트 오름차순
Collections.sort(list);
list.sort(Comparator.naturalOrder());

// 리스트 내림차순
Collections.sort(list, Collections.reverseOrder());
list.sort(Comparator.reverseOrder());

// 2차원 배열
Arrays.sort(arr, (a, b) -> a[0] - b[0]);

// 문자열 길이순
Arrays.sort(arr, (a, b) -> a.length() - b.length());

 

 

 

 

K번째 수

https://school.programmers.co.kr/learn/courses/30/lessons/42748?language=java

간단한 정렬 문제 + substring

기억할 포인트

- 배열 자르기는 Arrays.copyOfRange(arr, i, j)

   -> i부터 j-1까지 복사

 

- 정렬 Arrays.sort(arr);

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        
        for(int idx=0; idx<commands.length; idx++){
            int i = commands[idx][0];
            int j = commands[idx][1];
            int k = commands[idx][2];
            
            int[] copy = Arrays.copyOfRange(array, i-1, j);
            Arrays.sort(copy);
            answer[idx] = copy[k-1];
        }
        
        
        return answer;
    }
}

 

 

 

 

 

가장 큰 수

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=java

붙이면 더 큰수를 찾는문제

문자열로 더했을 때 뭐가 더 큰지 비교하면 된다

 

기억할 포인트

- int 배열을 String 배열로 바꿔주는 부분

   String.valueOf(num);

- 문자열로 비교할때 Comparator 사용하는 부분

   Arrays.sort(arr, (a, b) -> (b+a).compareTo(a+b));

 

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        
        String[] arr = new String[numbers.length];
        for(int i=0; i<numbers.length; i++){
            arr[i] = String.valueOf(numbers[i]);
        }
        
        
        Arrays.sort(arr, (a,b) -> (b+a).compareTo(a+b));
        
        
        if(arr[0].equals("0")) return "0";

        
        StringBuilder sb = new StringBuilder();
        for(String el : arr) {
            sb.append(el);
        }
        
        
        return sb.toString();
    }
}

 

 

 

 

 

스택 큐

 

같은 숫자는 싫어

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

 

기억할 포인트

- list -> array

 answer.stream().mapToInt(Integer::toIntValue).toArray();

기억 안나면 배열 생성하고 하나씩 넣어주기

 

int[] arrayAnswer = new int[answer.size()];

for문 돌면서 arrayAnswer[i] = answer.get(i);

 

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        ArrayList<Integer> answer = new ArrayList<>();
        
        Integer prev = null;
        for(int el : arr) {
            if(prev == null) {
                answer.add(el);
                prev = el;
            }
            
            if (prev != null) {
                if(prev != el){
                    answer.add(el);
                }
                prev = el;
            }
        }
        // return answer.stream().mapToInt(Integer::intValue).toArray();
        
        int[] returnAnswer = new int[answer.size()];
        for (int i=0; i<answer.size(); i++){
            returnAnswer[i] = answer.get(i);
        }
            
            
        return returnAnswer;
    }
    
    public void print(Object o){
        System.out.println(o);
    }
}

 

 

 

 

기능개발

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

큐로도 할 수 있을 것 같은데 인덱스로 했다

 

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        
        List<Integer> answer = new ArrayList<>();
        
        int date = 1;
        int complete = 0;
        
        for(int i=0; i<progresses.length; i++){
            int progress = progresses[i];
            int speed = speeds[i];
            
            int finishDate = dayLeft(progress, speed);
            
            // 남았을때 이전꺼 기록, 초기화, date 움직이기
            if(finishDate > date){
                
                if(complete != 0){
                    answer.add(complete);
                    complete = 0;
                }
                
                date = finishDate;
                complete++;
                
                continue;
            }
            // 이미 처리 완료이면 date 그대로 complete++
            complete++;
        }
        if(complete != 0){
            answer.add(complete);
        }
        
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
    
    public int dayLeft(int progress, int speed){
        int result = (100 - progress) / speed;
        int left = (100 - progress) % speed;
        if (left > 0){
            result++;
        }
        return result;
    }
    
}

 

 

 

 

프로세스

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

os 프로세스 우선순위 실행을 구현해보는 문제

 

기억할 포인트

 

- 큐2개를 쓰는 방법이 처음에 잘 생각이 안났다

지금보니 우선순위큐에는 인덱스를 저장할 필요는 없는 것 같다

   pq에 배열을 안넣고 Integer를 넣어주면

   Collections.reverseOrder()로 Comparator를 넣어줄 수 있어서 더 간결하다

 

- 우선순위큐는 pq.peek()하면서 꺼내지 않기

 

import java.util.*;


class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        
        Queue<int[]> q = new ArrayDeque<>();
        Queue<int[]> pq = new PriorityQueue<>((a,b) -> b[1] - a[1]);
        
        for(int i=0; i<priorities.length; i++){
            q.add(new int[] {i, priorities[i]});
            pq.add(new int[] {i, priorities[i]});
        }
        
        while (! q.isEmpty()){
            int[] current = q.poll();
            
            if(current[1] < pq.peek()[1]){
                q.add(current);
            } else{
                pq.poll();
                // 실행
                answer++;
                if (current[0] == location) return answer;
            }
            
        }
        
        return answer;
    }
    
    public void print(Object o){
        System.out.println(o);
    }
    
}