백준 5002 - 도어맨 (자바 - 그리디)

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

5002번: 도어맨

 

* 문제 요약

정인이는 강남의 유명 클럽 Top Root 의 도어맨이다. 클럽의 사장은 정인이에게 클럽이 꽉 찼을 때, 클럽에 있는 남자와 여자의 수는 거의 비슷해야 한다고 말해주었다.

사람들은 클럽이 문을 열기 전부터 줄을 서 있는다. 클럽이 문을 열면, 한 명씩 직접 정인이가 입장시켜 준다.

정인이는 줄의 순서를 바탕으로 입장시켜 준다.

이때, 항상 첫번째에 있는 사람을 입장시켜야 하는 것은 아니다. 정인이는 재량을 발휘하여 두번째로 줄 서 있는 사람을 첫번째 사람보다 먼저 입장을 시켜줄 수 있다.

물론 이런 상황이 자주 발생하면 앞 사람이 매우 짜증이 날 것이고, 정인이에게 시비를 걸 수도 있다.

하지만 정인이는 모든 싸움을 이길 수 있는 사람이기 때문에 이런 걱정은 하지 않아도 된다.

 

안타깝게도, 정인이는 이렇게 싸움은 잘 하지만 숫자 계산은 잘 하지 못한다. 정인이는 항상 클럽에 들어가있는 남자와 여자의 차이를 머릿속에 계산하고 있어야 한다. 이 차이가 정인이가 기억할 수 있는 값 보다 크게 된다면 남은 사람들은 클럽에 입장할 수 없게 된다.

줄을 서 있는 순서와 정인이가 기억할 수 있는 차이의 최댓값이 주어졌을때, 클럽에 있는 사람의 수의 최댓값을 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 정인이가 기억할 수 있는 가장 큰 차이 X < 100 이 주어진다.

둘째 줄에는 줄을 서 있는 순서가 주어진다. W 는 여성, M 은 남성을 나타내며, 길이는 최대 100 이다.

가장 왼쪽에 있는 글자가 줄의 가장 앞에 서 있는 사람의 성별이다.

 

* 출력

클럽에 있는 사람 수의 최댓값을 출력한다.

 

* 예시

 

* 해결 과정

반드시 줄 맨앞에 있는 사람만 들여보낼 수 있는 것이 아니라 필요할 경우 바로 뒤에 있는 사람도 들여보낼 수 있으므로 앞에 있는 사람보다 뒷 사람을 먼저 들여보내기 쉽게 하기 위해 덱 자료구조를 활용했다.

(덱은 맨앞에 있는 데이터를 대상으로도 삽입과 추출을 할 수 있기 때문)

 

그리고 Math.abs() 메소드를 통해 절댓값으로 남녀 숫자차이를 구해서 어느쪽 성별이 더 크든 상관없이 현재 도어맨이 기억할 수 있는 최대 차이를 계산할 수 있게끔 하였다.

반복 로직은 아래와 같이 수행하였다.

1. 줄 맨앞에 서 있는 성별을 덱에서 추출한다. (firstGender)

1-1. 만약 해당 성별이 남성일 경우 남자쪽 숫자를 1 늘린 상태에서 남녀간 숫자 차이의 절댓값을 구하고 난 다음, 만약 기억할 수 있는 차이를 넘지 않으면 남자쪽 숫자를 1 늘려준다.

1-2. 만약 남자쪽 숫자를 1 늘렸을 때 기억할 수 있는 차이를 넘을 경우, 바로 뒤에 있는 사람의 성별은 무엇인지 확인하기 위해 현재 덱의 맨앞에 있는 데이터를 다시 한 번 추출한다. (secondGender)

1-3. 만약 해당 성별이 여자일 경우 남녀 숫자차이를 계산하지 않고 즉시 여자쪽 숫자를 1 늘려준 다음, 기존에 먼저 꺼냈던 성별을(firstGender) 덱의 가장 앞에 다시 집어넣어준다.

1-4. 만약 해당 성별이 남자일 경우 맨앞에 있는 사람, 바로 뒤에 있는 사람 둘 중 하나를 클럽에 입장시켜도 똑같이 남녀 숫자 차이의 절댓값이 기억할 수 있는 숫자를 초과하게 되므로 즉시 반복문을 종료한 다음, 현재 클럽에 입장해 있는 숫자 (남자쪽 숫자 + 여자쪽 숫자) 를 출력해준다.

 

2. 만약 덱의 맨앞에서 꺼낸 성별이 여성일 경우 (firstGender) 1 에서의 절차와 정반대의 로직을 수행해준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int x = Integer.parseInt(br.readLine());
        String str = br.readLine();
        Deque<Character> people = new LinkedList<>();
        for (int i = 0; i < str.length(); i++) {
            people.offerLast(str.charAt(i));
        }

        int manCount = 0;
        int womanCount = 0;
        char firstGender = ' ';
        char secondGender = ' ';
        while (Math.abs(manCount - womanCount) <= x && !people.isEmpty()) {
            firstGender = people.pollFirst();

            if (firstGender == 'M') {
                if (Math.abs((manCount + 1) - womanCount) <= x) {
                    manCount++;
                } else {
                    if (!people.isEmpty()) {
                        secondGender = people.pollFirst();
                        if (secondGender == 'W') {
                            womanCount++;
                            people.offerFirst(firstGender);
                        } else {
                            break;
                        }
                    } else {
                        break;
                    }
                }
            } else if (firstGender == 'W') {
                if (Math.abs(manCount - (womanCount + 1)) <= x) {
                    womanCount++;
                } else {
                    if (!people.isEmpty()) {
                        secondGender = people.pollFirst();
                        if (secondGender == 'M') {
                            manCount++;
                            people.offerFirst(firstGender);
                        } else {
                            break;
                        }
                    } else {
                        break;
                    }

                }
            }
        }
        bw.write((manCount + womanCount) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 현재 가장 앞에 있는 사람을 입장시킬 시 남녀 숫자 차이의 절댓값이 기억할 수 있는 숫자를 초과하는지 검사하고, 만약 초과하지 않는 경우 입장 허가.

만약 초과하는 경우 바로 뒤에 있는 사람의 성별까지 확인해보고, 그 사람이 기존에 맨앞에 있던 사람과 반대 성별이라면 그 사람을 입장 허가, 그렇지 않다면 반복문을 종료시킨다.

선택된 해답이 조건을 만족하는지 검사한다. -> 남녀간의 숫자 차이 절댓값이 기억할 수 있는 숫자를 초과하거나, 줄을 서 있는 사람이 모두 다 입장하기 전 까지는 현재까지 클럽에 입장 가능한 사람들의 숫자가 최대값에 가까이 근접했는지 알 수 없으므로 위의 2가지 조건 중 하나가 만족 될 때까지 반복문을 계속한다.

 

위의 과정을 통해 문제를 해결하였으므로 그리디 알고리즘에 해당된다.