[코드트리 조별과제] 1회차(0715 ~ 0721)

1주 차는 구간 칠하기 유형에 대해 학습을 진행하였습니다.

 

작년 봄쯤에 해당 유형 문제를 독특하게 해결했던 기억이 납니다. 아래 문제의 경우 각 선분의 영역을 포함하는 집합을 생성해, 합집합 연산을 통해 공통되는 부분을 추려 총길이를 구하는 방식으로 해결하였습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/120876

프로그래머스

 

해당 유형을 딱히 접해본 적이 없어서 아예 유형으로 정형화 되어있는지 몰랐기 때문에 이번 기회에 학습을 진행하였습니다.

[블럭쌓는 명령2]

https://www.codetree.ai/missions/5/problems/block-stacking-commands2?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

해당 유형의 문제 해결 컨셉은 다음과 같습니다.

1. 주어진 영역 입력
2. 주어진 영역을 순회하며 문제에 따른 액션 수행
3. 모든 영역에 대한 순회 종료 후 결과 처리

n, k = map(int, input().split())
arr = [0] * (n + 1)  # 블럭의 길이, n이 아니라면 처음부터 최대 범위(100)로 초기화 가능

for _ in range(k):
    s, e = map(int, input().split())  # 순회 영역 입력
    for i in range(s, e+1):  # 순회하며
        arr[i] += 1  # 블럭 쌓기

print(max(arr))  # max 연산을 통해 리스트의 값 중 최댓값(최대 높이의 블럭) 탐색

 0  1  2  3  4  5  6  7
[0, 0, 0, 0, 0, 0, 0, 0] → n = 7
[0, 0, 0, 0, 0, 1, 0, 0] → s = 5, e = 5
[0, 0, 1, 1, 1, 1, 0, 0] → s = 2, e = 4
[0, 0, 1, 1, 2, 2, 1, 0] → s = 4, e = 6
[0, 0, 1, 2, 3, 3, 1, 0] → s = 3, e = 5

[최대로 겹치는 구간]

https://www.codetree.ai/missions/5/problems/maximum-overlapped-segments&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

해당 문제는 머릿속으로 한 번 매핑 단계가 필요했던 거 같습니다.

가령 (2, 6)의 범위를 가지는 선분을 표현할 때 인덱스 상으로 2, 3, 4, 5로 x1 ~ x2 - 1로 표현할 수 있습니다. 이는 Python의 range 표시와 동일합니다.

또 다르게 생각할 수 있는 방법은 표현되는 영역 중 시작 영역이 인덱스로 표현된다고 할 수 있습니다.

(2, 3) → 2
(3, 4) → 3
(4, 5) → 4
(5, 6) → 5

이러한 접근 방식으로 해당 문제는 다음과 같이 풀이할 수 있습니다.

n = int(input())
cmd = [list(map(int, input().split())) for _ in range(n)]
arr = [0] * 201  # x의 표현 범위는 -100 ≤ x1 < x2 ≤ 100 이므로 200개의 공간이 필요

for s, e in cmd:
    for i in range(s + 100, e + 100):  # 리스트는 0번부터 시작하므로 값을 보정
        arr[i] += 1

print(max(arr))

1. 표현 범위에 따라 리스트 초기화
2. 주어진 영역 입력
3. 주어진 영역을 순회하며 문제에 따른 액션 수행
   • 제약 사항에 따라 값 보정
   • 음수의 최솟값에 맞춰 보정 수행
4. 모든 영역에 대한 순회 종료 후 결과 처리