[백준] 18513. 샘터 (Java)

수직선 상의 실제 위치를 구현하는 것이 아닌 가상 위치를 지정하는 것이 핵심!

18513번: 샘터

풀이

3달전엔 실패했지만 다시 마음을 다잡고 풀어보니 의외로 간단한 문제였다.

샘터 위치가 -1억~1억이기 때문에 배열로 수직선을 구현할 생각을 하지 말고 map을 써서 해당 위치에 값이 있는지 없는지만 검사하면 메모리 상에서 효율적인 문제풀이가 가능하다.

• final int LOWER_BOUND, UPPER_BOUND 변수를 통해 미리 boundary를 지정해줬다.
• offset: 샘터 위치를 전부 돌았을 때마다 1씩 증가시키는 변수
• Map<Integer, Integer> map: 집이나 샘터 위치를 저장

Logic

• 샘터 위치를 입력받을 때 큐에도 전부 넣는다.

코드

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

public class Main {
    static final int LOWER_BOUND = -100000000;
    static final int UPPER_BOUND = 100000000;
    static int N, K, offset;
    static long unhappiness;
    static Queue<Integer> q = new LinkedList<>();
    static Map<Integer, Integer> map = new HashMap<>();

    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());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int spring = Integer.parseInt(st.nextToken());
            map.put(spring, -1);
            q.offer(spring);
        }

        outer:
        while(K > 0) {
            int size = q.size();
            offset += 1;
            for (int i = 0; i < size; i++) {
                int current = q.poll();
                if (current - offset == LOWER_BOUND || current + offset == UPPER_BOUND) continue;
                if (map.get(current - offset) != null && map.get(current + offset) != null) continue;
                if (map.get(current - offset) == null) {
                    map.put(current - offset, offset);
                    unhappiness += offset;
                    K--;
                }
                if (K == 0) break outer;

                if (map.get(current + offset) == null) {
                    map.put(current + offset, offset);
                    unhappiness += offset;
                    K--;
                }
                if (K == 0) break outer;

                q.offer(current);
            }
        }

        bw.write(String.valueOf(unhappiness));
        br.close();
        bw.close();
    }
}

 

실행 결과