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

링크

SWEA[4408]

문제설명

• 그리디

문제풀이

• 그리디

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.StringTokenizer;

class Range{
    int start;
    int end;
    public Range() {
    }
    public Range(int start, int end) {
        super();
        this.start = start;
        this.end = end;
    }
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("Range [start=").append(start).append(", end=").append(end).append("]");
        return builder.toString();
    }
}
public class Solution {
    public static void main(String[] args) throws NumberFormatException, IOException {
        //System.setIn(new FileInputStream("res/swea/4408.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T=Integer.parseInt(br.readLine().trim());
        for (int test_case = 1; test_case <= T; test_case++) {
            int ans=0;
            int N = Integer.parseInt(br.readLine().trim());
            LinkedList<Range> move = new LinkedList<>();
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine().trim());
                int a;
                int b;
                a=(Integer.parseInt(st.nextToken())-1)/2;
                b=(Integer.parseInt(st.nextToken())-1)/2;
                if(a<b) {
                    move.add(new Range(a,b));
                }
                else {
                    move.add(new Range(b,a));
                }
            }

            Collections.sort(move, new Comparator<Range>() {
                @Override
                public int compare(Range o1, Range o2) {
                    // TODO Auto-generated method stub
                    return o1.start-o2.start;
                }
            });
            Range now=null;
            while(!move.isEmpty()) {
                now = move.poll();    //얘 기준으로 안겹치는애들 하나씩 잡고 제거
                //System.out.println("pick"+now);
                for (int i = 0; i < move.size(); i++) {
                    if(now.end<move.get(i).start) {
                        now = move.get(i);
                        //System.out.println("remove"+now);
                        move.remove(i);
                        i--;    //지워졌으니 뒤에꺼가 다시 앞으로 밀려옴
                    }
                }
                ans++;
            }

            System.out.println("#"+test_case+" "+ans);
            /*
             * 초기화
             */
        }//end test_case
    }//end main
}

아쉬운점

• 인풋이 (시작 방 <끝나는 방) 일거라고 생각했었음.
  • 거꾸로 (시작 방> 끝나는 방)의 경우도 있음...
• 예외 케이스가 없나?
  • 최초의 한 명은 무조건 선택해야함-> 나머지 선택가능한사람중 최초의 한명은 무조건 선택해야 함.
  • [10,20] 이후 [30,100] OR [30,40]중 하나를 선택해야 하는데 뭐가 맞는가?
    • 둘 다 겹치기 때문에
    • 어차피 둘 중 하나는 무조건 선택돼야 하므로, 둘 중 아무거나 선택해도 됨

잘한점

• {0,1},{2,3}...번 방은 같은 방으로 취급함.
• 정렬 후 그리디
• comparator 사용한 sort 공부

다른풀이

• 길마다 겹치는 경로의 개수를 구하여, 그 중 최대값을 구하면 답이다.
• 왜냐하면 어차피 그 경로는 경로의 개수만큼 지나가야하는데, 그만큼 겹치고 있다는 뜻이므로.