[백준] 알고리즘 분류(그리디 알고리즘,JAVA)19941번, 햄버거 분배

문제 링크

19941번: 햄버거 분배

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 사람들은 K이하의 거리에 있는 햄버거를 먹을 수 있습니다.

2. 'H' : 햄버거, 'P' : 사람을 뜻합니다.

3. 햄버거를 먹을 수 있는 최대 인원을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 사람이 햄버거를 먹는 최적의 경우를 탐색합니다.

 

3. 햄버거를 먹은 인원을 결과로 출력합니다.

 

 

햄버거를 먹는 최적의 경우

 

햄버거를 먹을 수 있는 범위 : 사람 위치 - K ≤ 범위 ≤ 사람위치 + K

 

햄버거를 먹는 최적의 경우 : 햄버거 먹는 범위에서 가장 왼쪽에 가까운 햄버거를 먹을 때

 

Why?

 

가장 왼쪽에 햄버거를 먹어야 다음 사람이 먹을 수 있는 햄버거의 경우가 늘어나기 때문이다.

 

예를 들어

 

HHPP, K = 2일 때

 

3번째 P가 2번째 햄버거를 먹으면 4번째 P는 먹을 수 있는 햄버거가 존재하지 않습니다.

 

H

H

P

P(먹을 수 있는 햄버거 X)

 

하지만 3번째 P가 왼쪽에 가장 가까운 1번째 햄버거를 먹으면 4번째 P는 2번째 햄버거를 먹을 수 있습니다.

 

H

H

P

P

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N = 20

K = 2

 

식탁 정보

 

HHPHPPHHPPHPPPHPHPHP

 

2. 사람이 햄버거를 먹는 최적의 경우를 탐색합니다.

사람들 햄버거 최적의 경우 탐색

※E : Eat의 약자로 먹을 수 있는 범위를 설명을 위해 표현한 것입니다.

 

3번째 사람

HHPHPPHHPPHPPPHPHPHP

범위 : 1 ≤ E ≤ 5 

가장 왼쪽 1번째 햄버거 먹기!

 

5번째 사람

HHPHPPHHPPHPPPHPHPHP

범위 : 3 ≤ E ≤ 7 

가장 왼쪽 4번째 햄버거 먹기!

 

6번째 사람

HHPHPPHHPPHPPPHPHPHP

범위 : 4 ≤ E ≤ 8

가장 왼쪽 7번째 햄버거 먹기!

 

9번째 사람

HHPHPPHHPPHPPPHPHPHP

범위 : 7 ≤ E ≤ 11

가장 왼쪽 8번째 햄버거 먹기!

 

10번째 사람

HHPHPPHHPPHPPPHPHPHP

범위 : 9 ≤ E ≤ 12

가장 왼쪽 11번째 햄버거 먹기!

 

12번째 사람

HHPHPPHHPPHPPPHPHPHP

범위 : 10 ≤ E ≤ 14

먹을 수 있는 햄버거 X

 

13번째 사람

HHPHPPHHPPHPPPHPHPHP

범위 : 11 ≤ E ≤ 15

가장 왼쪽 15번째 햄버거 먹기!

 

14번째 사람

HHPHPPHHPPHPPPHPHPHP

범위 : 12 ≤ E ≤ 16

먹을 수 있는 햄버거 X

 

16번째 사람

HHPHPPHHPPHPPPHPHPHP

범위 : 14 ≤ E ≤ 18

가장 왼쪽 17번째 햄버거 먹기!

 

18번째 사람

HHPHPPHHPPHPPPHPHPHP

범위 : 16 ≤ E ≤ 20

가장 왼쪽 19번째 햄버거 먹기!

 

20번째 사람

HHPHPPHHPPHPPPHPHPHP

범위 : 18 ≤ E ≤ 20

먹을 수 있는 햄버거 X

 

3. 햄버거를 먹은 인원을 결과로 출력합니다.

 

햄버거를 먹은 사람 : 3, 5, 6, 9, 10, 13, 16, 18 = 8명

8을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용하여 N, K을 띄어쓰기 기준 나누었습니다.
• String.toCharArray을 이용하여 식탁의 정보를 배열의 형태로 변경하였습니다.
• 식탁에 사람들이 먹을 수 있는 범위에서 왼쪽에 가까운 햄버거를 먹는 탐색을 진행합니다.
• 탐색 종료 후 햄버거를 먹은 인원수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bergerCheck함수는 식탁에 햄버거인지 확인 및 먹기를 진행합니다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main{
    static char[] info;	//식탁 정보 저장 배열
    static int answer = 0;	//먹은 인원수 저장 변수
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        info = br.readLine().toCharArray();		//식탁 정보 배열 형태로 저장
        //식탁 정보 탐색
        for(int i=0;i<N;i++){
            if(info[i] == 'P'){		//사람일 때 먹을 수있는 햄버거 탐색
                int index = Math.max(i - K, 0);
                boolean check = false;
                //먹을 수 있는 햄버거 왼쪽 범위 탐색
                //가장 먼저 발견한 햄버거가 범위 왼쪽에 가장 가까운 햄버거!
                for(int j=index;j<i;j++){
                    if(bergerCheck(j)){	//먹을 수 있는 햄버거 발견
                        check = true;
                        break;
                    }
                }
                //먹을 수 있는 햄버거 오른쪽 범위 탐색
                if(!check){
                    index = i + K >= N ? N-1 : i + K;
                    for(int j=i+1;j<=index;j++){
                        if(bergerCheck(j))	//먹을 수 있는 햄버거 발견
                            break;
                    }
                }
            }
        }
        bw.write(answer + "");	//햄버거 먹은 인원수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //범위 탐색할 때 먹을 수 있는 햄버거인지 확인하는 함수
    static boolean bergerCheck(int index){
        if(info[index] == 'H'){		//햄버거가 맞을 때
            info[index] = 'X';	//햄버거 먹었기 때문에 'X'로 변경
            answer++;		//먹은 인원수 증가!
            return true;	//먹기 성공 True
        }
        return false;		//먹기 실패 False
    }
}