[Algo] 백준 21967 세워라 반석 위에 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/21967

메모리 : 178808KB

시간 : 828ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        // 최솟값과 최댓값을 찾아줄 treemap
        TreeMap<Integer, Integer> num = new TreeMap<>();
        int ans = 0;
        int a = 0;
        int b = 0;
        while (a < N && b < N) {
            num.put(arr[a], a); // 값, idx 넣기
            // 차이가 2 초과면 그 돌은 아니네.
            if (num.lastKey() - num.firstKey() > 2) {
                for (Map.Entry<Integer, Integer> entry : num.entrySet()) {
                    if (entry.getValue() == b) {
                        num.remove(entry.getKey());
                        break;
                    }
                }
                b++;
            } else {
                // 최대 길이
                ans = Math.max(ans, a - b + 1);
                a++;
            }
        }
        System.out.print(ans);
    }
}

풀이

반석이 되는지 하나씩 체크하며 진행해나간다.
범위를 변경하면서 min와 max를 다시 체크해야하기때문에 TreeMap을 사용해 최소, 최대값을 항상 가져올 수 있게 했다.
범위를 변경할 때 entryset으로 map을 돌아서 해당 값을 가진 idx를 찾아 지워준다.

문제를 풀고보니 내 풀이가 시간이 길더라!
문제를 볼 때 반석의 높이가 1~10이라는 걸 못봤다ㅜㅜ 이 점을 이용하면 문제를 더 빠르게 풀 수 있었다.

다른풀이 : 최소 최대 값을 고정하고 최소값이 1일때 최댓값이 3일수밖에 없는 점을 이용한다.

최솟값 1 최댓값 3인경우 배열을 하나씩 돌며 반석의 값이 이 사이에 위치한 경우만 cnt를 더해준다 최소 최대 범위를 벗어난 경우 cnt를 초기화해주고 계속 진행한다.