23-07-25 TIL

문제

• 백준 19941
  • 처음이 문제를 받고 들었던 생각은 슬라이딩 윈도우 기법을 사용하자는 것이었다. 시간 제한이 0.5초 밖에 되지 않았기 때문에 반복문을 중첩해서 사용하기는 어려울 것이라는 생각이 들었기 때문이다.
  • 헌데 슬라이딩 윈도우 기법을 사용해서 풀었지만 제대로 된 답이 나오지 않아서, 일단은 그냥 되는 대로 풀어보고자 했다.

시도

• 백준 19941
  • 해당 String 값을 입력받고 들었던 생각은 이 String과 같은 크기를 갖는 boolean 배열을 만들어서 문제를 해결하면 좋겠다는 것이었다.
  • count를 한 경우라면 해당 배열의 값을 true로 바꾸어주면 된다라는 생각이 어렴풋이 들었다.
  • 하지만 생각하기 어려웠던 문제는 시작 인덱스와 종료 인덱스의 인덱스 값을 구하는 부분이었다.
  • 앞 뒤로 햄버거를 고를 수 있었기 때문에 0보다 작거나, 혹은 인덱스 값을 넘어갈 수 있었기 때문이다.
  • 인덱스 값을 넘어서는 부분은 -K를 해주면 될 거 같은데 0보다 작은 부분은 반복문을 두 부분으로 나누어서 풀어야하나 싶은 생각이 들었다.

해결

• 백준 19941
  • 조금 고민을 해보자 자바의 메서드 중에 Math.max, Math.min 이 떠올랐다.
  • 해당 인덱스가 0보다 작으면 0을, 아니면 해당 인덱스를 시작 인덱스로 설정하면 되고, 인덱스 값을 넘어선다면 마지막 인덱스를, 아니면 해당 인덱스를 종료 인덱스로 설정하면 된다.
  • 중첩 반복문을 사용했는데도 시간초과가 나지 않고 넘어간 것으로 보아 test 예시들의 크기가 별로 크지 않았던 모양이다.
  • 하지만 test 예시의 크기가 크면 시간초과가 날 가능성이 높으므로 같은 문제라면 슬라이딩 윈도우 기법을 사용해서 다시 풀어봐야겠다.

코드

• 백준 19941 (햄버거 분배) - Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());

        // 두번째 줄 받기
        String req = br.readLine();

        // 햄버거를 먹을 수 있는 최대 사람 수
        int count = 0;

        // boolean으로 처리해서 햄버거가 남아있는지 아닌지 체크 (부울 배열은 초기화하면 전부 false)
        boolean[] tmp = new boolean[N];

        for(int i = 0; i < N; i++){

            // 현재 자리가 사람 자리면
            if(req.charAt(i) == 'P') {

                // 시작위치와 끝위치를 정해야하는데
                // 처음이 0보다 작으면 안되고
                // 마지막이 N - 1 보다 크면 안된다. (인덱스 범위까지)
                int start = Math.max(i - K, 0);
                int end = Math.min(i + K, N - 1);

                for(int j = start; j <= end; j++){
                    // 인덱스 j가 햄버거이고, true로 바뀌지 않은 상태라면 -> count되지 않은 상태라면
                    if(req.charAt(j) == 'H' && !tmp[j]){

                        tmp[j] = true;
                        count++;
                        break;

                    }

                }

            }

        }

        bw.write(count + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}