구간 칠하기

안녕하세요. 오늘은 구간을 칠하는 알고리즘에 대해 알아보겠습니다.

 

두 구간을 합한 크기 구하기

A는 [2, 5] 구간을, B는 [3, 8] 구간을 청소했습니다.
총 몇 개의 칸을 청소했는지를 구해보세요.

 

위의 문제는 2개의 구간이 주어졌으므로, 2가지 케이스로 생각해볼 수 있습니다.

 

case 1. 두 구간이 겹치는 경우

각 구간의 크기에서 겹치는 부분을 제외해야 합니다.

 

case 2. 두 구간이 겹치지 않는 경우

각 구간의 크기를 합하면 됩니다.

 

💡접근 아이디어

하지만, 1차원 배열을 활용하면 더욱 간단히 해결할 수 있습니다.

각 구간을 배열에 1로 기록하면서 직접 시뮬레이션을 진행하면 됩니다.

총 몇 개의 칸을 청소했는지 구하려면 값이 1인 갯수만 세주면 됩니다.

만약 음수 구간을 포함한다면, 모든 좌표에 특정 OFFSET을 더해 모든 좌표를 양수로 만들어 진행하면 됩니다.

 

 

 

겹치는 지점과 구간 찾기

💡접근 아이디어

겹치는 지점을 찾는 것은 간단히 구할 수 있습니다.

[x1, x2] 구간에 해당하는 위치에 전부 1을 더해주고, 2 이상인 지점을 카운팅하면 됩니다.

 

하지만 겹치는 구간을 구하는 것은 조금 다릅니다.

[x1, x2]에 대해가 아닌 [x1, x2 - 1] 구간에 해당하는 위치에 전부 1을 더해주고, 2 이상인 구간의 크기를 구하면 됩니다. 

"[x1 , x1 + 1] 구간"은 "x1칸"으로 나타내는 것으로 이해하면 쉽습니다.

 

[1, 3] 과 [2,3] 의 겹치는 지점과 겹치는 구간을 찾아보겠습니다.

<겹치는 지점을 구하기 위해 기록한 일차원 배열>
[0, 1, 2, 2] -> 2

<겹치는 구간을 구하기 위해 기록한 일차원 배열>
[1, 1, 2] -> 1   ( [2,3] 구간은 2번째 칸(0-base)을 뜻함 )

 

 

겹치는 구간 찾기에서 주의해야할 점 - 구간이 왼쪽으로 진행하는 경우

겹치는 구간을 찾을 때에, 오른쪽에서 왼쪽으로 진행하는 구간 처리를 유의해야합니다.

 

만약 [1, 3]과 [3, 2]의 겹치는 구간을 구한다고 했을 때,

[3, 2]는 [2, 3] 구간으로 생각하여 처리해줘야합니다. 따라서 [1, 3] 와 [2, 3] 의 겹치는 구간을 구하는 것으로 생각하면 됩니다.

 

 

위의 케이스가 쓰이는 문제는 다음과 같습니다.

왔다 갔던 구역 2 - 코드트리

 

입력이 다음과 같이 주어졌다면,

6
2 R
6 L

 

좌표의 움직임은 다음과 같게 됩니다.

0 -> 2 (+2) -> -4 (-6)

 

처음에는 오른쪽으로 진행하는 경우처럼, 왼쪽으로 진행할 때도 구간의 끝을 포함하지 않으면 된다고 생각했습니다. ([x1, x2 - 1])
그래서 -4는 제외하고 [2, -3]만 기록하면 된다고 판단했죠.

하지만 실제로는 '구간의 끝을 제외하는 것'이 핵심이 아니라, [x1, x1+1] 구간이 x1에 매핑된다는 점이 중요하다는 것을 나중에야 이해했습니다.
이 점을 고려하면, [2, -3]가 아니라 [-4, 1]에 기록해야 올바르다는 걸 깨달았습니다.

 

위의 주의점을 고려한 풀이 코드는 다음과 같습니다.

// hyeblee
import java.io.*;
import java.util.*;


public class Main {

  public static final int MAX_SIZE = 1000;

  public static int N;
  public static int[] arr = new int[MAX_SIZE * 2 + 1];

  // 구간을 기록하는 메서드
  public static void write(int start, int end) {
    for (int i = start; i <= end; i++) {
      arr[i]++;
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    N = sc.nextInt();
    int cur = MAX_SIZE;

    for (int i = 0; i < N; i++) {
      int x = sc.nextInt();
      char ch = sc.next().charAt(0);
      if (ch == 'L') {
        write(cur - x, cur - 1);
        cur -= x;
      } else if (ch == 'R') {
        write(cur, cur + x - 1);
        cur += x;
      }
    }
    
    int count = 0;
    
    for (int i = 0; i <= MAX_SIZE * 2; i++) {
      if (arr[i] >= 2) {
        count++;
      }
    }

    System.out.println(count);
  }
}

 

위 풀이에서 주의해야할 점은, 배열의 크기를 MAX_SIZE + 1이 아닌 MAX_SIZE * 2 + 1로 설정해야 한다는 것입니다.

왜냐하면 음의 방향으로도 움직일 수 있으므로, 가능한 좌표의 전체 범위가 -1000 ~ 1000이 되기 때문입니다.