[백준 25395] 커넥티드 카 실험 - JAVA

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

 

첫 코드 야매로 푼 것 같아서 총 두번 풀어봄

(왼쪽 오른쪽을 매 순간 비교해서 둘다 새로운 자동차가 연결되지 않았으면 탐색 종료)

 

이전 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int N = Integer.parseInt(st.nextToken());
    int S = Integer.parseInt(st.nextToken());

    List<int[]> l = new ArrayList<>();
    List<int[]> r = new ArrayList<>();
    List<Integer> ans = new ArrayList<>();

    int[] mid = new int[3];

    int[] atTmp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    int[] disTmp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

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

      int carNum = i + 1;
      int[] car = {carNum, atTmp[i], disTmp[i]};

      if (carNum < S) {
        l.add(car);
      } else if (carNum > S) {
        r.add(car);
      } else {
        mid = car;
      }
    }

    ans.add(mid[0]);
    Collections.sort(l, (a, b) -> a[1] - b[1]);
    Collections.sort(r, (a, b) -> a[1] - b[1]);

    int rScope = mid[1] + mid[2];
    int lScope = mid[1] - mid[2];

    int rIdx = 0;
    int lIdx = l.size() - 1;

    while (true) {

      boolean rChanged = false;
      boolean lChanged = false;

      if (rIdx < r.size()) {
        int[] rCar = r.get(rIdx);

        if (rCar[1] <= rScope) {
          ans.add(rCar[0]);
          rScope = Math.max(rScope, rCar[1] + rCar[2]);
          lScope = Math.min(lScope, rCar[1] - rCar[2]);
          rIdx++;
          rChanged = true;
        }
      }

      if (lIdx >= 0) {
        int[] lCar = l.get(lIdx);

        if (lCar[1] >= lScope) {
          ans.add(lCar[0]);
          rScope = Math.max(rScope, lCar[1] + lCar[2]);
          lScope = Math.min(lScope, lCar[1] - lCar[2]);
          lIdx--;
          lChanged = true;
        }
      }

      if (!rChanged && !lChanged) {
        break;
      }
    }

    Collections.sort(ans);
    StringBuilder sb = new StringBuilder();

    for (int i : ans) {
      sb.append(i).append(" ");
    }

    System.out.println(sb);
  }
}

 

---

최종 풀이

 

 

유의 사항

처음 연결된 자동차(mid)를 기준으로, left에 있는 자동차를 연결했을 때 범위가 충분히 넓다면 right에도 영향을 줄 수 있다.

=> l[], r[]로 나누면 안되며, 매 순간 right도 함께 비교해야 한다.

 

투 포인터로 풀이했다.

1. 현재 갈 수 있는 가장 왼쪽, 오른쪽 범위를 뜻하는 l,r을 갱신한다.

2. lPointer, rPointer에 있는 자동차가 l ~ r의 범위 내라면 큐에 넣고 포인터를 이동한다.

(문제에서 r + 1에 가기위해선 r을 무조건 거쳐야 하므로, for문으로 모든 인덱스를 비교할 필요는 없다.)

3. 포인터는 다음에 탐색할 값  을 가리키는 용도이므로, lPointer + 1 ~ rPointer - 1 까지의 값을 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

  static class Car {

    int at, dis;

    Car(int at, int dis) {
      this.at = at;
      this.dis = dis;
    }
  }

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int N = Integer.parseInt(st.nextToken());
    int S = Integer.parseInt(st.nextToken());

    int[] at = new int[N + 1];
    int[] dis = new int[N + 1];
    boolean[] vst = new boolean[N + 1];

    st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      at[i] = Integer.parseInt(st.nextToken());
    }
    st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      dis[i] = Integer.parseInt(st.nextToken());
    }

    Queue<Car> q = new ArrayDeque<>();
    q.offer(new Car(at[S], dis[S]));

    int lpt = S - 1;
    int rpt = S + 1;

    int l = at[S] - dis[S];
    int r = at[S] + dis[S];

    while (!q.isEmpty()) {
      Car car = q.poll();

      l = Math.min(car.at - car.dis, l);
      r = Math.max(car.at + car.dis, r);

      if (lpt > 0 && !vst[lpt] && at[lpt] >= l) {
        vst[lpt] = true;
        q.offer(new Car(at[lpt], dis[lpt]));
        lpt--;
      }

      if (rpt <= N && !vst[rpt] && at[rpt] <= r) {
        vst[rpt] = true;
        q.offer(new Car(at[rpt], dis[rpt]));
        rpt++;
      }
    }

    StringBuilder sb = new StringBuilder();
    for (int i = lpt + 1; i < rpt; i++) {
      sb.append(i).append(" ");
    }

    System.out.println(sb);
  }
}