[JAVA] 4408. 자기 방으로 돌아가기 - SWEA

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {
    static StringTokenizer st;
    static boolean[] visited;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= tc; t++) {
            sb.append("#").append(t).append(" ");
            int N = Integer.parseInt(br.readLine());
            PriorityQueue<Student> pq = new PriorityQueue<>();
            while (N-- > 0) {
                st = new StringTokenizer(br.readLine());
                pq.add(new Student(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            }
            sb.append(getAnswer(pq)).append("\n");
        }
        System.out.println(sb);
    }
    private static int getAnswer(PriorityQueue<Student> pq) {
        int time = 0;
        Queue<Student> tmpQueue = new LinkedList<>();
        while (!pq.isEmpty()) {
            Student standard = pq.poll();
            visited = new boolean[201];
            time++;
            changeVisited(standard.t1, standard.t2, visited);

            while (!pq.isEmpty()) {
                Student s = pq.poll();
                if (goTogether(s, visited)) {
                    changeVisited(s.t1, s.t2, visited);
                    continue;
                }
                tmpQueue.add(s);
            }
            pq.addAll(tmpQueue);
            tmpQueue.clear();
        }
        return time;
    }

    private static boolean goTogether(Student s, boolean[] visited) {
        int start = s.t1 % 2 == 0 ? s.t1 / 2 - 1 : (s.t1 + 1) / 2 - 1;
        int end = s.t2 % 2 == 0 ? s.t2 / 2 - 1 : (s.t2 + 1) / 2 - 1;
        for (int i = start; i <= end; i++) {
            if(visited[i])
                return false;
        }
        return true;
    }

    private static void changeVisited(int start, int end, boolean[] visited) {
        start = start % 2 == 0 ? start / 2 - 1 : (start + 1) / 2 - 1;
        end = end % 2 == 0 ? end / 2 - 1 : (end + 1) / 2 - 1;
        for (int i = start; i <= end; i++) {
            visited[i] = true;
        }
    }
    private static class Student implements Comparable<Student>{
        int t1, t2;

        Student(int t1, int t2) {
            this.t1 = Math.min(t1, t2);
            this.t2 = Math.max(t1, t2);
        }

        @Override
        public int compareTo(Student o1) {
            return this.t1 - o1.t1; //t1기준 오름차순 정렬
        }
    }
}

💡 구현

풀이

• '복도를 공유하면 안된다'라는 것에 초점을 맞췄다. 1-2, 3-4, 5-6 ... 이렇게 복도를 공유한다
  
  • 따라서 짝수/홀수에 구분 없이 '어느' 복도를 공유하는지에 초점을 맞춘다. 
    -> 이러면 복도가 총 200개이므로 이것 기준으로 체크
  • 이 구역이 겹치면 안되기 때문에 들어온 번호를 복도 idx로 변환해 체크하며 겹친다면 해당 이동은 패스
• 출발 방, 도착 방 번호를 별도의 객체 Student로 정의해 저장함
  • 출발 방 > 도착 방 번호 인 경우가 존재하므로, 처리의 편의성을 높이기 위해 객체 저장 시 start에는 작은 값, end에는 큰 값을 넣어 저장한다 (출발, 도착 순서가 바뀌어도 딱히 문제 없으므로)
• 해당 객체들을 저장하고 꺼내 쓸 우선순위 큐를 정의(start 기준 오름차순)
  • 처음에 하나 꺼내고, 이번 턴에 사용할 visited 배열 초기화 후, 지나다니는 복도 true로 변환
  • 이후 이 visited 배열을 가지고 다음 객체들을 꺼내며 겹치면 다시 넣고, 안겹치면 뺀뒤 visited에 체크한다
• 방 번호에서 복도 번호를 도출하는 방법은 아래와 같다
  • 방 번호가 짝수인 경우 == idx / 2 -1 
  • 방 번호가 홀수인 경우 == (idx + 1) / 2 - 1