DS : "()" 문제 ArrayList 말고 Deque (스택 과 큐) ,PriorityQ

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

프로그래머스

 

 

1 차 적으로는 다음과 같이 구현을 했고 모든 테스트 케이스는 통과를 했지만 , 효율성을 놓쳤다.

@Test
void sol_test2() {
    //22:09
    String s = "()()";
    solution(s);
}
boolean solution(String s) {
    boolean answer = true;
    String[]  given = s.split("");
    List<String> stack = new ArrayList<>();
    for(String item: given) {
        if(item.equals("(")){
            stack.add(item);
        }else{
            if(stack.size() == 0 ) return false;
            if(stack.get(stack.size()-1).equals(")")) return false;
            stack.remove(stack.size()-1);
        }
    }

    if(stack.size() == 0)
        return answer;
    return false;
}

 

2 차 작성한 코드 

 

import java.util.*;

class Solution {
    boolean solution(String s) {
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char item = s.charAt(i);
            if (item == '(') {
					stack.addLast(item);
            } else {
                if (stack.isEmpty() || stack.peekLast() != '(') {
                    return false;
                }
                stack.removeLast();
            }
        }

        return stack.isEmpty();
    }
}

 

Deque :  Double-Ended Queue  : 스텍과 queue  두가지 모두로 사용이 가능하다.

 

 

 

프로그래머스 프로세스 문제 

 

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

프로그래머스

 

1차 코드 

 

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        Deque<List<Integer>> deque = new LinkedList<>();
        Map<Integer, Integer> priorityCount = new HashMap<>();

        int count = 1;

        for (int i = 0; i < priorities.length; i++) {
            int priority = priorities[i];
            priorityCount.put(priority, priorityCount.getOrDefault(priority, 0) + 1);

            List<Integer> item = new ArrayList<>();
            item.add(i);
            item.add(priority);
            deque.add(item);
        }

        while (!deque.isEmpty()) {
            List<Integer> item = deque.poll();
            int priority = item.get(1);
            int index = item.get(0);

            boolean flag = true;
            for (int i = priority + 1; i <= 9; i++) {
                if (priorityCount.containsKey(i) && priorityCount.get(i) > 0) {
                    deque.add(item);
                    priorityCount.put(priority, priorityCount.get(priority) + 1);
                    count--;
                    flag = false;
                    break;
                }
            }

            if (flag) {
                if (index == location) {
                    return count;
                }
            }
            priorityCount.put(priority, priorityCount.get(priority) - 1);
            count++;
        }

        return count;
    }
}

 

 

 

 

다른 사람의 풀이  : 적절한 자구조를 쓰면 코드가 단순해지고 실수도 줄어든다.

 

PriorityQueue 의 기본은  min heap 이며 우리는  우선순위가 큰게 필요하는 reverseOrdder 를 해준다.

 

예시) 

@Test
void sol_test_11(){
    PriorityQueue<Integer> p = new PriorityQueue<>();
    p.add(10);
    p.add(15);
    p.add(16);
    System.out.println(p.peek()); // re : 10


    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    pq.add(10);
    pq.add(15);
    pq.add(16);
    System.out.println(pq.peek()); // re : 16
}

 

 

public int solution_others(int[] priorities, int location) {
    int answer = 1;
    PriorityQueue<Integer> p = new PriorityQueue<>(Collections.reverseOrder());;

    for(int i=0; i<priorities.length; i++){
        p.add(priorities[i]);
    }

    while(!p.isEmpty()){
        for(int i=0; i<priorities.length; i++){
            if(priorities[i] == p.peek()){
                if(i == location){
                    return answer;
                }
                p.poll();
                answer++;
            }
        }
    }

    return answer;
}

 

 1 문제만 더 보자

 

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

프로그래머스

 

강의실 배정 문제 ? pin 꽂기 문제와 유사하다.

 

Level 3 로 적절한 자료구조를 생각하는것이 오래 걸렸고, 해설을 찾아봤다.

 

이중 배열일때 , 정렬을 하는 방식은 다음과 같다  , 

 

[작업이 요청되는 시점, 작업의 소요시간] 

int[][] given = {{0, 3}, {1, 9}, {2, 6}, {1, 7}, {3, 6}, {4, 5}, {2, 6}};

 

작업이 요청되는 시점을 기준으로 정렬 후 작업의 소유 시간기준으로 정렬했다.

Arrays.sort(jobs, Comparator.comparingInt((int[] o) -> o[0]).thenComparingInt(o -> o[1]));

 

 

우선순위 큐이며 정렬 기준은 작업의 소유시간이다. 

PriorityQueue<int[]> queue =  new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));

 

 

public int solution(int[][] jobs) {

    int sumTime = 0;
    int numTask = jobs.length;  // > 0
    // 요청시간으로 오름차순  , 요청시간이 같다면  처리기간으로 오름차순
    Arrays.sort(jobs, Comparator.comparingInt((int[] o) -> o[0]).thenComparingInt(o -> o[1]));
    int count  = 0 ;
    int jobIdx = 0 ;
    int currentTime = 0;

    PriorityQueue<int[]> queue =  new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
    while (count < numTask) {
        while(jobIdx < numTask && jobs[jobIdx][0] <= currentTime){
            queue.add(jobs[jobIdx]);
            jobIdx++;
        }
        if(queue.isEmpty()){
            currentTime = jobs[jobIdx][0];
        }else{
            int[] tmp = queue.poll();
            sumTime += (tmp[1] + currentTime) - tmp[0];
            currentTime += tmp[1];
            count++;
        }
    }

    return (int) Math.floor(sumTime/numTask);
}