그리디(Greedy) 자바 백준 1931, 1541

https://sh1mj1-log.tistory.com/130 글에서 이어지는 포스팅입니다.

 

 

백준 1931 회의실 배정

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

1. 문제 분석

1개의 회의실에 회의가 겹치지 않도록 최대한 많은 회의를 배정해야 합니다. 이 때는 그리디 알고리즘을 적용해야 합니다. 

현재 회의의 종료 시간이 빠를 수록 다음 회의와 겹치지 않게 시작하는 데 유리합니다.

종료 시간이 빠른 순서대로 정렬하면 겹치지 않는 회의실을 적절하게 선택하면 됩니다.

2. 손으로 풀기

1. 회의와 정보와 관련된 데이터를 저장한 후 종료 시간 순으로 정렬.
    종료 시간이 같다면 시작 시간을 기준으로 정렬.

 

2. 순차적으로 탐색하다가 시간이 겹치지 않는 회의가 나오면 선택.

 

 

1번의 '종료 시간이 같다면 시작 시간을 기준으로 정렬' 하는 것에 대한 추가 설명입니다.

예를 들어서 (2,2) (1,2) 2개의 회의가 있다고 가정했을 때 실제로는 2개의 회의가 겹치지 않게 할 수 있습니다.

그런데 만약 (2,2) 가 먼저 나오면 로직상 나중에 나온 (1,2) 회의가 불가능하게 됩니다.

그러므로 종료 시간이 같다면 항상 시작 시간이 빠른 순서로 정렬하는 로직도 추가해야 합니다.

 

3. 슈도코드

N: 회의 개수, A: 회의 정보
A 배열 정렬 수행. 종료 시간 기준 오름차순. 만약 종료 시간이 같다면 시간 기준 정렬

for(회의 개수만큼 반복){
    if(앞 회의의 종료 시간보다 시작 시간이 빠르거나 같은 회의가 나오면){
        현재 회의 종료 시간으로 종료 시간 업데이트
        정답(회의 수)++
    }
}
정답(회의 수) 출력.

4. 코드

public class BaekJun1931 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());

        int A[][] = new int[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            A[i][0] = Integer.parseInt(st.nextToken());
            A[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A, (o1, o2) -> {
            if (o1[1] == o2[1]) {
                return o1[0] - o2[0]; // 종료시간이 같으면 시작 시간 기준 오름차순 (시작 시간 빠른 순)
            }
            return o1[1] - o2[1]; // 종료 시간 기준 오름차순 (종료 시간 빠른 순)
        });

        int result = 0;
        int beforeEnd = -1;
        for (int i = 0; i < N; i++) {
            if (A[i][0] >= beforeEnd) {
                beforeEnd = A[i][1];
                result++;
            }
        }
        System.out.println(result);
    }
}

 

문제 풀이 실패와 원인

이 문제는 제가 처음 접근했던 방식으로 했을 때 메모리 초과가 일어났습니다.

처음에는 회의 시간 종료 기준이 아닌 회의에서 걸리는 시간을 기준으로 정렬했었습니다. 아래 처럼 풀었었습니다.

그래서 이런 식으로 풀었습니다.

슈도코드

N: 회의 개수
meetingRoomCal : 회의 시간표 배열 0 ~ 24 int
0 -> 회의가 아예 없음.
1 -> 회의가 시작 시간이거나 끝시간임.
2 -> 회의가 중간 시간임.

pQu: 우선순위 큐 - (회의 끝 시간 - 시작 시간) 값을 기준으로 오름차순 정렬한다.
for(N){ 회의를 우선순위 큐에 넣기 }
int cnt = 0;

while(큐가 빌 때까지){
    curMeeting = poll;
    curMeeting 의 시작 시간 ~ 종료 시간에 대해서 meetingRoomCal 배열의 값 중 2인 것이 있으면{
     현재 회의는 불가능함.
    } 1인 것이 있으면{
        회의의 중간값이라면 가능하고, 중간값이 아니라면 불가능함.
    } 없으면 {
        회의가 들어갈 수 있음.
        cnt++;
        meetingRoomCal 에 반영
    }
}
sout(cnt)

class Meeting{
    시작 시간,
    종료 시간
}

당연히 회의는 0시부터 24시에만 있을 줄 알랐습니다. 그런데 사실 회의는 문제 조건에서  '회의 시작 시간과 끝나는 시간은 2³¹-1보다 작거나 같은 자연수 또는 0 이다.' 라고 했네요...

 

그래서 회의시간표 배열 meetingRoomCal 이 0 ~ 2³¹-1 의 크기가 됩니다. 그래서 메모리 초과가 났습니다.

 

먼저 문제를 풀기 전에 입력 조건을 잘 살펴보는 습관을 들여야 겠네요.. 그리고 어떤 문제든 문제에서 원하는 답을 최대한 단순하고 쉽게 구하려고 노력해야 겠습니다..

 

백준  1541 잃어버린 괄호

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

1. 문제 분석

그리디 관점에서 생각하면 쉽게 풀 수 있습니다. 

가장 작은 최소값을 만들기 위해서는 뺄셈을 수행할 때 최대한 큰 수를 빼야 합니다.

식에서 - 가 한 번 등장하고 나서는 그 뒤에 있는 수들은 모두 뺄셈이 가능합니다. 괄호를 사용해서 말이죠. 

아래에서 그림으로 봅시다.

2. 손으로 풀기

여기서 수 하나만 나왔을 경우를 조심해야 합니다.

만약 식이 '1' 인 경우 그냥 1을 출력해야 합니다.

3. 슈도코드

정답 ans = 0;
식 입력받기 equ
현재 수 curNum = 0; 
while(equ 에 대해 끝까지){
    현재 입력값이 숫자이면 
        curNum = curNum * 10 + 현재 수 
        char 형으로 한글자씩 읽기 때문에 여러 문자가 연속으로 숫자이면 
        해당 숫자를 제대로 읽어야함.(121 같은 경우) // 
        현재 입력값이 마지막 값이라면
            이전에 - 가 나왔다면
                정답에 curNum 빼기
            아니라면
                정답헤 curNum 더하기
    continue;
    
    현재 입력값이 - 이면
        이전에 - 가 나왔으면
            정답에 curNum 빼기
        아니라면 
            정답에 curNum 더하기
        - 가 나왔음을 기록
        curNum = 0;
        continue;
    현재 입력값이 + 이면
        이전에 - 가 나왔으면
            정답에 curNum 빼기
        아니라면 
            정답에 curNum 더하기
    
정답 출력

4. 코드

public class BaekJun1541Self {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] equ = br.readLine().strip().toCharArray();
        br.close();

        int ans = 0;
        int curNum = 0;
        boolean isMinus = false;

        for (int i = 0; i < equ.length; i++) {
            int x = equ[i];
            if (x >= '0' && x <= '9') {
                curNum = curNum * 10 + x - '0';
                if (i == equ.length - 1) {
                    if (isMinus) {
                        ans -= curNum;
                    } else {
                        ans += curNum;
                    }
                }
                continue;
            }

            if (x == '-') {
                if (isMinus) {
                    ans -= curNum;
                } else {
                    ans += curNum;
                }
                isMinus = true;
                curNum = 0;
                continue;
            }
            if (x == '+') {
                if (isMinus) {
                    ans -= curNum;
                } else {
                    ans += curNum;
                }
                curNum = 0;
            }
        }
        System.out.println(ans);
    }
}

 

여기서 br.readLine().strip().toCharArray(); 의 strip() 에 조심해야 합니다. 

strip() 은 문자열의 앞 뒤에 공백을 제거해주는 메소드입니다.

처음에는 이를 넣지 않아서 틀렸는데 아마 이 문제 테스트 케이스에서 앞 뒤로 공백이 들어가 있는 경우가 있는 것 같네요..

(그런 말은 입력 조건에 없었는데....)