[인프런/greedy/결혼식]

<<풀이>>

 

-1차 나의 풀이-

 

흠 ~~ 일단은 greedy 문제이지만 그냥 단순하게 풀리는 느낌이 있어서 일반적인 구현을 했고,

 

실제로도 답은 맞았다!!

 

근데 전체 풀이는 오답으로 나왔다 ??

 

근데 조금만 생각해보니까 바로 틀린 이유가 보인다 ㅋㅋㅋ

 

일단 나는 이 특정 구간 하나만을 비교해서 count++; 를 해줬다. 이렇게 되면 특정 구간에서는 겹치는 사람이 n명이 있더라고 해도

n명끼리는 또 안 겹칠 수 있기 때문이다.

 

import java.util.ArrayList;
import java.util.Scanner;

class Data {
     int start;
     int end;

    public Data(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

class Main {

    private int solution(int n, ArrayList<Data> list) {
        int answer = 0;

        for (int i = 0; i < n-1; i++) {
            int count = 0;
            for (int j = i+1; j < n; j++) {
                if(!(list.get(i).start >= list.get(j).end || list.get(i).end <= list.get(j).start)) {
                    count++;
                }
            }
            answer = Math.max(count, answer);
        }
        return answer;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        ArrayList<Data> list = new ArrayList<>();

        for (int i=0; i<n; i++) list.add(new Data(in.nextInt(), in.nextInt()));

        System.out.println(T.solution(n, list));
    }
}

 

 

-강사님 풀이 및 나의 풀이-

 

역시 Greedy 문제였고 강사님은 이를 활용해서 구했다. 

 

S에 진입을 하면 count++ 해주고 end가 나오면 count-- 를 해주면 되는 원리이다.

 

그렇게 하기 위해서는 ssese 이런식으로 한줄로 정렬이 되어 있으면 효율적이다.

 

그래서 ArrayList에 넣을 때 S따로 E따로 넣어줌으로써 list에 들어갈 때 SE 세트가 아니고 따로 들어가게 된다.

 

그러면 sesse 같은 나열식으로 만들 수 있다.

 

이후 숫자를 대상으로 오름차순 정렬을 하면 효율적으로 나열 된 값들을 보면서 count 증감을 할 수 있다.

 

근데 여기서 조심할 부분은 e와 s가 같은 시간대 인 부분인데, 같을 때는 e s를 오름차순 정렬해서 e가 먼저 실행이 되도록 해야한다.

 

그렇지 않고 s를 먼저 해버리게 되면 논리적으로는 2명이 최대인데 3명까지 들어오고 2로 변경이 됨으로 정답이 3이 최대가 되는 오류가 난다.

 

즉, 나가서 없어야 할 사람인데 추가 되어 있는 것이다. 

 

이까지 고려한다면 문제없이 풀 수 있는 greedy 문제이다.

 

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Time implements Comparable<Time> {
    int time;
    char state;

    public Time(int time, char state) {
        this.time = time;
        this.state = state;
    }

    @Override
    public int compareTo(Time o) {
        if(this.time==o.time) return this.state - o.state;
        else return this.time - o.time;

    }
}


class Main {
    private int solution(ArrayList<Time> list) {
        int answer = Integer.MIN_VALUE;
        int cnt  = 0;
        for(Time x : list) {
            if (x.state=='S') cnt++;
            else cnt--;

            answer = Math.max(cnt, answer);
        }
        return answer;
    }


    public static void main(String[] args) {
        Main T = new Main();
        ArrayList<Time> list = new ArrayList<Time>();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i=0; i<n; i++) {
            int start = in.nextInt();
            int end = in.nextInt();
            list.add(new Time(start, 'S'));
            list.add(new Time(end, 'E'));
        }
        Collections.sort(list);

        System.out.println(T.solution(list));
    }
}

 

 

<<추가 공부>>

 

매번 까먹는

 

Comparable<T>  인터페이스와 compareTo(T o) 추상 메서드

 

return this.x - o.x 이렇게 빼기를 했을 때 오른쪽에 o.x가 있다면 오름차순이고 그 반대이면 내림차순이다.

 

또한 생성자 메서드 등 생성하는 단축키는 CMD + N 이다.