자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Stack,Queue_응급실_Queue)

 

 

 

8. 응급실

 

예시 입력 1 

5 2
60 50 70 80 90

예시 출력 1

3

예시 입력 2 

6 3
70 60 90 60 60 60

예시 출력 2

4

 

 

내가 푼 틀린 풀이

문제를 제대로 이해 못했다.나는 해당 문제를 큐를 안써도 내림차순으로 정렬한뒤 3번째인 환자의 카운팅횟수만 넘겨주면 되는거 아닌가? 생각했는데 ,대기목록에 있는 환자의 순서는 그대로 둬야한다. 내림차순하면 대기목록 환자 순서들까지 바뀌어버려서 이렇게 하면 m번째 환자의 우선순위만 고려되는 것이다. 

import java.util.*;


// 틀린 문제
public class Main {

    public int solution(int n, int m, int[] arr) {
        int target = arr[m];
        System.out.println(target);
        Integer[] integerArr = Arrays.stream(arr)
                .boxed()
                .toArray(Integer[]::new);

        Arrays.sort(integerArr, Comparator.reverseOrder());
        System.out.println(Arrays.toString(integerArr));
        int cnt = 0;
        for (int x : integerArr) {
            cnt++;
            if (x == target) {
                return cnt;
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n, m, arr));
    }
}

// 입력
6 3
70 60 90 60 60 60
// 출력
60
[90, 70, 60, 60, 60, 60]
3

 

강의 풀이 (Time: 174ms Memory: 27MB)

 

큐라는 자료구조에 대기목록 순서대로 집어 넣습니다. 이때 자료구조를 클래스형으로 만듭니다.

큐에 클래스 객체를 넣어서 구현합니다.

이때 person이라는 클래스에서 인스턴스 변수를 Id와 priority로 잡고 객체형태로 큐에 넣겠습니다.

맨 앞에 있는 60은 우선순위가 다른 것보다 낮기 때문에 뒤로 넣어줍니다. 계속 우선순위가 제일 높은걸 만날때 까지 뒤로 넣어줍니다.

제일 높은 우선순위를 만나면 answer에 값을 누적해줍니다. 그리고 90의 id값이 m번째 인지 확인합니다. 아니면 카운팅만하고 poll하고 지나갑니다. 이어서 계속 우선순위가 제일 높고 id값이 m과 같은걸 만날때 까지 반복해줍니다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Person {
    int id;
    int priority;

    public Person(int id, int priority) {
        this.id = id;
        this.priority = priority;
    }
}

public class Main {
    public int solution(int n, int m, int[] arr) {
        int answer = 0;
        Queue<Person> Q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            // 객체를 생성해서 큐에 넣겠습니다.
            Q.offer(new Person(i, arr[i]));
        }

        while (!Q.isEmpty()) {
            // 하나 꺼내서 변수로 담고 진료를 받을 수 있는지 Q를 for each 돌면서 확인합니다.
            Person tmp = Q.poll();
            for (Person x : Q) {
                // 다른 우선순위 높은걸 발견하면 다시 큐에 tmp를 넣어줍니다
                if (x.priority > tmp.priority) {
                    Q.offer(tmp);
                    // 첫번째 반복문에서 다시 새로운 Q객체를 넣어주기 위함
                    // cnt = 0;이랑 똑같은 원리
                    tmp = null;
                    // 우선순위 높은 사람을 발견해서 더 비교할 필요없어서 break;
                    break;
                }
            }
            // 2번째 반복문에서 null로 재할당하면 - 우선순위 높은거 발견했다는 의미
            // answer을 누적시키고 Person의 id값이 m이랑 같은지 확인
            if (tmp!=null) {
                answer++;
                if(tmp.id==m) return answer;
            }
        }
        // m번째는 분명히 있기 때문에, 여기까지 올 일은 없지만, 리턴값 컴파일 에러 안나게 하기위함
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n, m, arr));
    }
}

 

 

다른 풀이(Time: 176ms Memory: 27MB)

클래스 대신 해쉬맵을 큐에 객체로 넣어서 사용했다. key값에 String문자열로 구분짓고 하는게 인상적이다. 인스턴스 변수를 이렇게 문자열 키값으로 만드는것 같다.

import java.util.*;
// 클래스대신 해쉬맵 사용
public class Main {

    public int solution(int n, int m, int[] arr) {
        Queue<Map<String, Integer>> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            Map<String, Integer> person = new HashMap<>();
            person.put("id", i);
            person.put("priority", arr[i]);
            queue.offer(person);
        }

        int answer = 0;
        while (!queue.isEmpty()) {
            Map<String, Integer> tmp = queue.poll();
            int tmpPriority = tmp.get("priority");

            boolean canPrint = true;
            for (Map<String, Integer> x : queue) {
                if (x.get("priority") > tmpPriority) {
                    canPrint = false;
                    break;
                }
            }

            if (canPrint) {
                answer++;
                if (tmp.get("id") == m) {
                    return answer;
                }
            } else {
                queue.offer(tmp);
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n, m, arr));
    }
}