[Python] 특정 구간의 개수 구하기 - 겹치는 지점, 겹치는 구간

1. 겹치는 지점 구하기

- 3개의 선분은 각각 [2, 6], [3, 8], [6, 9] 구간에 놓여 있다.

- 가장 많이 겹치는 지점과 개수를 구하기 위해서 어떻게 해야 할까?

 

 

- 위 그림에서 겹치는 개수는 1개이고 지점은 6이다.

- 코드로 나타내면 다음과 같다.

 

n = int(input())
max_point = -1
arr = []

# 구간을 입력. 끝점의 최대값을 구함. 구간들을 리스트에 삽입
for _ in range(n):
    x, y = map(int, input().split())
    max_point = max(max_point, y)
    arr.append((x, y))

# 끝점의 최대값의 크기만큼 0인 원소의 리스트를 생성
points = [0 for _ in range(max_point+1)]

# 선분의 시작점부터 끝점까지 각 index에 1을 더함
for x, y in arr:
    for i in range(x, y+1):
        points[i] += 1

# 겹치는 구간의 최대 개수
max_val = max(points)

# 가장 많이 겹치는 지점, 개수 출력
print('가장 많이 겹치는 지점은 ', end='')
for i in range(len(points)):
    if max_val == points[i]:
        print(f'{i} ', end=' ')
print(f'이고 가장 많이 겹치는 개수는 {max_val}입니다.')

 

>> 3
>> 2 6
>> 3 8
>> 6 9
가장 많이 겹치는 지점은 6  이고 가장 많이 겹치는 개수는 3입니다.

- 선분의 개수인 n을 입력하고 지점의 겹치는 개수를 구하기 위해 끝점의 최댓값을 구한다.

- n개의 선분의 구간을 입력하고 끝점의 최댓값을 구하고 구간을 리스트에 저장한다. (arr)

- 끝점의 최댓값의 크기만큼 원소가 0인 리스트를 생성한다. (points)

- arr을 순회하여 points의 index인 시작점에서 끝점까지 각 원소에 1을 더한다.

- 이를 통해 각 지점마다 선분의 개수를 구할 수 있다.

- max를 사용해 겹치는 지점의 최대 개수를 구한다. (max_val)

- points에 있는 원소들을 비교하며 max_val과 같은 값의 index를 구해 지점을 출력한다.

 

- 가장 많이 겹치는 구간을 구하기 위해 while을 사용한다.

- 구간의 index인 j를 1씩 증가시켜 points [j]가 겹치는 최대 개수인지 판단한다.

- isbool의 bool 타입을 정의하여 True면 가장 많이 겹치는 구간을 의미한다.

- False이면 가장 많이 겹치는 구간이 아닌 것을 의미한다.

- points [j]가 최대 개수일 때 isbool이 False면 j부터 최대 구간이므로 시작점을 j로 설정하고 isbool을 True로 갱신한다.

- points [j]가 최대 개수일 때 isbool이 True면 j가 최대 구간에 속한다는 것을 의미한다.

- points [j]가 최대 개수가 아닐 때 isbool이 False면 최대 구간이 속하지 않음을 의미한다.

- points [j]가 최대 개수가 아닐 때 isbool이 True면 현재 index인 j 전까지 가장 많이 겹치는 구간이므로 시작점과 j-1을 리스트에 저장한다.

 

 

2. 겹치는 구간 구하기

- 위와 동일하게 3개의 선분이 각각 [2, 6], [3, 8], [6, 9] 구간에 놓여 있다.

- 이번엔 지점이 가장 많이 겹치는 구간과 개수를 구하여라.

 

- 그림에서와 같이 가장 많이 겹치는 구간의 개수는 2이다.

- 2개가 겹치는 구간은 [3, 4], [4, 5], [5, 6], [6, 7], [7, 8] 이므로 [3, 8]이다.

 

- 이를 코드로 작성하면 다음과 같다.

n = int(input())
max_point = -1
arr = []

# 구간을 입력. 끝점의 최대값을 구함. 구간들을 리스트에 삽입
for _ in range(n):
    x, y = map(int, input().split())
    max_point = max(max_point, y)
    arr.append((x, y))

# 끝점의 최대값의 크기만큼 0인 원소의 리스트를 생성
points = [0 for _ in range(max_point+1)]

# 선분의 시작점부터 끝점-1까지 각 index에 1을 더함
for x, y in arr:
    for i in range(x, y):
        points[i] += 1

# 겹치는 구간의 최대 개수
max_val = max(points)

# 가장 많이 겹치는 구간 구하기
j = 1  # index
range_arr = []  # 많이 겹치는 구간의 리스트
isbool = False  # True면 가장 많이 겹치는 지점. False면 그렇지 않은 지점.
first_point = -1  # 가장 많이 겹치는 구간의 시작점
while j != max_point+1:
    if points[j] == max_val:
        if not isbool:  # 가장 많이 겹치는 구간의 시작점을 고정
            first_point = j
            isbool = True
    else:
        if isbool:  # True이면 시작점부터 현재 지점-1의 구간을 리스트에 저장
            range_arr.append((first_point, j))
            isbool = False

    j += 1

print(f'가장 많이 겹치는 구간은 ', end='')
for x, y in range_arr:
    print(f'({x}, {y}) ', end='')
print(f'이고, 개수는 {max_val}')

 

>> 3
>> 2 4
>> 3 8
>> 6 9
가장 많이 겹치는 지점은 (3, 4) (6, 8) 이고, 구간은 2

 

- 겹치는 지점 구하기 문제와 비슷하지만 points 리스트에 값을 더하는 것에서 차이점이 있다.

- 겹치는 구간 구하기에서는 시작점에서 끝점-1까지의 index에 points 각각의 원소에 1을 더한다.

- 즉, 이 문제에서 points는 겹치는 구간의 개수를 나타내는 리스트이다.

- points [i]는 i지점에서 i+1까지 선분의 개수를 나타낸다.

- points에서 max를 사용해 구간의 최대 개수를 구할 수 있다.

 

- 가장 많이 겹치는 구간을 구하기 위해 while을 사용한다.

- 구간의 index인 j를 1씩 증가시켜 points [j]가 겹치는 최대 개수인지 판단한다.

- isbool의 bool 타입을 정의하여 True면 가장 많이 겹치는 구간을 의미한다.

- False이면 가장 많이 겹치는 구간이 아닌 것을 의미한다.

- points [j]가 최대 개수일 때 isbool이 False면 j부터 최대 구간이므로 시작점을 j로 설정하고 isbool을 True로 갱신한다.

- points [j]가 최대 개수일 때 isbool이 True면 j가 최대 구간에 속한다는 것을 의미한다.

- points [j]가 최대 개수가 아닐 때 isbool이 False면 최대 구간이 속하지 않음을 의미한다.

- points [j]가 최대 개수가 아닐 때 isbool이 True면 현재 index인 j 전까지 가장 많이 겹치는 구간이므로 시작점과 j-1을 리스트에 저장한다.

 

 

3. 겹치는 지점과 구간의 차이점

 

- 위 그림과 같이 구간 [2, 6]까지의 선분이 1개 놓여 있다.

- 선분이 놓여 있는 지점은 각각 2, 3, 4, 5, 6이므로 5개이다.

- 구간은 [2, 3], [3, 4], [4, 5], [5, 6]이므로 4개이다.

- 따라서 지점의 개수가 구간의 개수보다 1개 많은 것을 알 수 있다.

- 이를 통해 구간 [x, y]까지 겹치는 지점을 구할 때는 x부터 y까지, 겹치는 구간을 구할 때는 x부터 y-1까지 구한다.

 

 

Q) 좌표가 음수가 존재할 때 최대로 겹치는 구간을 구하기

- 입력할 개수 n을 입력하고 n개의 시작점과 끝점의 좌표를 입력한다.

- 최대로 겹치는 구간과 개수를 출력하라.

 

import sys

n = int(input())
max_point = -sys.maxsize
min_point = sys.maxsize
arr = []
offset = 0

# 구간을 입력. 끝점의 최대값과 시작점의 최소값을 구함. 구간들을 리스트에 삽입
for _ in range(n):
    x, y = map(int, input().split())
    max_point = max(max_point, y)
    min_point = min(min_point, x)
    arr.append((x, y))

# 시작점의 최솟값이 음수일 때, 음수 좌표를 양수로 변경
if min_point < 0:
    offset += min_point*(-1)
    max_point += offset

# 끝점의 최대값의 크기만큼 0인 원소의 리스트를 생성
points = [0 for _ in range(max_point+1)]

# 선분의 시작점부터 끝점-1까지 각 index에 1을 더함
for x, y in arr:
    for i in range(x, y):
        points[i+offset] += 1

# 겹치는 구간의 최대 개수
max_val = max(points)

# 가장 많이 겹치는 구간 구하기
j = 1  # index
range_arr = []  # 많이 겹치는 구간의 리스트
isbool = False  # True면 가장 많이 겹치는 지점. False면 그렇지 않은 지점.
first_point = -1  # 가장 많이 겹치는 구간의 시작점
while j != max_point+1:
    if points[j] == max_val:
        if not isbool:  # 가장 많이 겹치는 구간의 시작점을 고정
            first_point = j
            isbool = True
    else:
        if isbool:  # True이면 시작점부터 현재 지점-1의 구간을 리스트에 저장
            range_arr.append((first_point, j))
            isbool = False

    j += 1

print(f'가장 많이 겹치는 구간은 ', end='')
for x, y in range_arr:
    print(f'({x-offset}, {y-offset}) ', end='')
print(f'이고, 개수는 {max_val}')

 

>> 3
>> -2 5
>> -4 3
>> 1 4
가장 많이 겹치는 구간은 (1, 3) 이고, 개수는 3

 

- max_point는 끝점의 최댓값이고, min_point는 시작점의 최솟값이다.

- sys 모듈을 import 하여 maxsize를 이용해 최대 정수값을 구할 수 있다.

- 최대 정수값에 -를 붙여 최소 정수값으로 나타낼 수 있다.

- offset은 만약 입력한 좌표에 음수가 있다면 offset만큼 더해 0 이상의 수로 바꿔준다.

- max_point는 겹치는 구간의 리스트 (points)를 구하기 위해 사용된다.

- min_point는 좌표값에서 음수가 있으면 offset을 이용하도록 사용된다.

- min_point가 음수이면 offset은 -min_point이 되고, max_point도 offset만큼 추가되어 points 크기를 늘려준다.

- 구간을 구하므로 시작점부터 끝점-1까지 points의 값에 1씩 증가한다.

- 겹치는 구간의 최대 개수와 구간을 구하고 구간을 출력할 때 offset을 빼서 원래 좌표로 출력한다.

 

 

Q) 좌우로 이동하여 겹치는 최대 구간 구하기

- 입력할 개수 n을 입력

- 이동할 수와 R 또는 L을 입력 (R은 오른쪽, L은 왼쪽)

- 시작점은 0부터 시작한다.

- 최대로 겹치는 구간과 개수를 출력하라.

 

import sys

n = int(input())  # 입력 개수
arr = []  # (시작점, 도착점) 리스트
point = 0  # 현재 이동하는 점
max_point = -sys.maxsize  # 도착점의 최대값
min_point = sys.maxsize  # 시작점의 최소값

# 왼쪽 또는 오른쪽에 따라 시작점과 도착점을 arr에 저장
for _ in range(n):
    distance, direction = input().split()
    distance = int(distance)
    if direction == 'R':
        arr.append([point, point+distance])
        point += distance
        max_point = max(max_point, point)
    else:
        arr.append([point-distance, point])
        point -= distance
        min_point = min(min_point, point)

# 시작점의 최소값이 음수이면 max_point를 증가
# max_point만큼 각 시작점과 도착점에 -min_point만큼 더함.
if min_point < 0:
    max_point += min_point*(-1)
    arr = list(map(lambda x: [x[0]+min_point*(-1), x[1]+min_point*(-1)], arr))

# 겹치는 구간의 개수 리스트
# section[i] = i번째부터 i+1번째까지 겹치는 개수
section = [0 for _ in range(max_point+1)]
for x, y in arr:
    for i in range(x, y):
        section[i] += 1

max_section = max(section)  # 가장 많이 겹치는 개수

# 가장 많이 겹치는 개수의 범위 구하기
max_section_range = []  # 가장 많이 겹치는 개수의 범위
isbool = False  # True이면 가장 많이 겹치는 범위에 속함.
start_point = -1  # max_section이 시작되는 시작점

for i in range(max_point+1):
    if section[i] == max_section:
        if not isbool:
            start_point = i
            isbool = True
    else:
        if isbool:
            max_section_range.append((start_point, i))
            isbool = False

# 개수와 구간을 출력
print(f'겹치는 개수의 최대 구간은 {max_section}개, 최대 구간은 ', end='')
max_section_range_msg = str()
for x, y in max_section_range:
    max_section_range_msg += f'({x+min_point}, {y+min_point}), '

max_section_range_msg = max_section_range_msg[:-2]
print(f'{max_section_range_msg}이다.')

 

>> 4
>> 3 R
>> 5 L
>> 2 L
>> 4 R
겹치는 개수의 최대 구간은 2개, 최대 구간은 (-4, 3)이다.

 

- 이동한 거리 (distance)와 방향 (direction)을 n번 입력한다.

- 초기 시작점을 0으로 설정하고 방향이 R일 때, 리스트 (arr)에 (현재 위치, 현재 위치+거리)를 삽입한다.

- 방향이 L일 때, arr에 (현재 위치-거리, 현재 위치)를 삽입한다.

- 현재 위치인 point는 R일 때 point+distance로 L일 때 point-distance로 갱신한다.

- 시작점의 최솟값 (min_point)를 구해 음수가 있는지 확인한다.

- 도착점의 최댓값 (max_point)를 구해 겹치는 구간의 길이를 설정한다.

- min_point가 음수이면 max_point를 -min_point를 더해 늘린다.

- 또한 arr에 있는 시작점과 도착점을 각각 -min_point를 더한다.

- 겹치는 구간을 구하고 가장 많이 겹치는 구간과 개수를 구한다.

 

 

Q) 용사의 색깔 게임.

- 일직선으로 되어 있는 여러 개수의 블록이 있다.

- 용사는 명령을 통해 블록을 이동하면서 블록에 색깔을 칠하게 된다.

- 명령은 m L 또는 m R로 입력하게 된다. (m은 숫자, L은 왼쪽, R은 오른쪽)

- m L은 현재 위치의 블록을 포함하여 왼쪽으로 m칸 이동하며 블록에 빨간색을 칠한다.

- m R은 현재 위치의 블록을 포함하여 오른쪽으로 m칸 이동하며 블록에 파란색을 칠한다.

- 블록의 색을 덧칠하면 마지막으로 칠한 색으로 바뀐다.

- 블록을 빨간색, 파란색으로 각각 2번 이상 칠하면 노란색으로 칠하게 된다.

- 빨간색, 파란색, 노란색의 블록 수를 출력하라.

 

import sys

n = int(input())
curr = 0
max_size = -sys.maxsize
min_size = sys.maxsize
arr = []

# max_size와 min_size 설정.
for _ in range(n):
    a, b = input().split()
    a = int(a)
    arr.append((a, b))
    if b == 'R':
        max_size = max(max_size, curr+a-1)
        curr += a-1
    else:
        min_size = min(min_size, curr-a+1)
        curr -= a-1

# 현재 위치 재설정.
curr = 0
if min_size < 0:
    max_size += abs(min_size)
    curr = abs(min_size)

# 블록 색칠
# [red 개수, blue 개수, 최근 색칠된 색깔]
# 개수를 구하는 것은 노란색으로 바꿀지 말지를 생각하기 위함.
color_check = [[0, 0, _] for _ in range(max_size+1)]

for x, y in arr:
    if y == 'R':
        for i in range(curr, curr+x):
            color_check[i][1] += 1
            color_check[i][2] = 'b'
        curr += x-1
    else:
        for i in range(curr-x+1, curr+1):
            color_check[i][0] += 1
            color_check[i][2] = 'r'
        curr -= x-1

# 색깔 개수 구하기. 조건에 따른 노란색 개수 구하기
red, blue, yellow = 0, 0, 0
for x, y, z in color_check:
    if x >= 2 and y >= 2:
        yellow += 1
    else:
        if z == 'b':
            blue += 1
        else:
            red += 1

print(f'빨간색의 블록 수는 {red}개이다.')
print(f'파란색의 블록 수는 {blue}개이다.')
print(f'노란색의 블록 수는 {yellow}개이다.')

 

>> 5
>> 8 R
>> 3 L
>> 5 L
>> 6 R
>> 4 L
빨간색의 블록 수는 1개이다.
파란색의 블록 수는 3개이다.
노란색의 블록 수는 4개이다.

 

 

- n개의 명령을 입력한다.

- curr은 현재 위치를 의미한다.

- max_size는 색칠할 블록의 개수를 정의하는 데 사용한다.

- min_size는 음수일 경우 배열로 표현할 수 없기 때문에 배열의 크기를 조절하는 데 사용된다.

- arr은 명령을 삽입하기 위한 리스트이다.

 

- 명령에서 오른쪽으로 이동하면 현재 위치는 이동한 값 - 1을 더해준다.

- 현재 위치가 가장 큰 값을 max_size로 설정한다.

- 왼쪽으로 이동하면 현재 위치는 이동한 값 - 1을 빼준다.

- 현재 위치가 가장 작은 값을 min_size로 설정한다.

 

- min_size가 음수이면 max_size, 현재 위치인 curr은 min_size의 양수 크기만큼 더한다.

 

- color_check 리스트를 설정한다. [빨간색 색칠된 개수, 파란색 색칠된 개수, 최근 색칠된 색깔]

- 명령 리스트인 arr을 순회하여 R이면 curr에서 curr+이동한 블록-1까지의 index에 파란색으로 색칠한 개수를 1 증가하고 최근 색칠된 색깔을 b (파란색)로 설정한다.

- L이면 curr-이동한 블록-1에서 curr까지의 index에 빨간색으로 색칠한 개수를 1 증가하고 최근 색칠된 색깔을 r (빨간색)로 설정한다.

- 또한 R이면 현재 위치를 이동한 블록-1을 더하고 L이면 이동한 블록-1을 뺀다.

 

- color_check를 순회하며 빨간색과 파란색으로 색칠된 개수가 2 이상이면 노란색 개수를 1 증가한다.

- 빨간색과 파란색으로 색칠된 개수가 2 미만이면 최근 색칠된 개수에 따라 빨간색 또는 파란색 개수를 1 증가한다.