[BOJ] 5002. 도어맨(Greedy, 문자열).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  

문제의 핵심은

줄을 서 있는 순서와 정인이가 기억할 수 있는 차이의 최댓값이 주어졌을 때, 

클럽에 있는 사람의 수의 최댓값을 구하는 프로그램이다.

해결하는 방법은 여러 가지가 있을 수 있지만,

N의 범위가 100 미만이라서 Arraylist의 remove()로 

입장시킬 수 있는 사람들을 입장시키면서 해결하였다.

생각보다 단순하게

첫 번째 서있는 사람을 입장시킬 수 있다면 입장!

두 번째 서있는 사람을 입장시킬 수 있다면 입장!

두 사람 모두 입장시킬 수 없다면 종료!

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList;   public class BOJ5002 {       static int X, M, W;     static ArrayList<Character> line;       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));           X = Integer.parseInt(br.readLine());         line = new ArrayList<>();         String str = br.readLine();         for (int i = 0; i < str.length(); i++) {             line.add(str.charAt(i));         }           System.out.println(process());       }       private static int process() {           // 남/여 차이가 기억할 수 있는 값보다 클 때까지         while (!line.isEmpty()) {               // 첫 번째 서있는 사람을 입장시킬 수 있다면             if(check(0)) continue;                          // 첫 번째 서있는 사람을 입장시킬 수 없는 경우,                          // 두 번째에 서있는 사람이 없다면 종료             if (line.size() == 1) return M + W;                          // 두 번째 서있는 사람을 입장시킬 수 있다면             if(check(1)) continue;               // 첫 번째, 두 번째 서있는 사람 모두 입장이 안된다면 종료             return M + W;         }                  return M + W;     }       private static boolean check(int th) {                  char gender = line.get(th);                  // 성별이 M일 경우         if (gender == 'M' && Math.abs((M + 1) - W) <= X) {             line.remove(th);             M++;             return true;         }         // 성별이 W일 경우         else if (gender == 'W' && Math.abs(M - (W + 1)) <= X) {             line.remove(th);             W++;             return true;         }                  return false;     }   } Colored by Color Scripter

cs