백준 자바1위 - 17611 직각다각형 [누적합][이모스]

 

17611번: 직각다각형

java 전체 1위 했습니다!

1. 문제 요약

다각형의 좌표가 주어지고 수직선과, 수평선에 대하여 해당 다각형의 수직선분과, 수평선분이 가장 많이 교차하는 횟수를 구하라.

 

2. 접근 방법

백준 - 3020 개똥벌레 [누적합][이모스]

해당 문제 다각형의 좌표가 주어집니다만, 다각형으로 생각하지 않으면(?)

이모스 알고리즘을 사용하면 쉽게 풀이할 수 있습니다. (위 링크 참조)

 

12
0 0
0 3
1 3
1 1
2 1
2 3
5 3
5 0
4 0
4 2
3 2
3 0

위 다각형은 위 좌표를 다각형으로 표현한 것입니다.

 

해당 다각형을 수직과, 수평 선분으로 분리를 하면, 다음과 같은 형태를 얻을 수 있습니다.

이런 식으로 주어진 좌표를 다각형으로 생각하지 않고, 두 가지 케이스의 이모스 장애물이 주어졌다고 생각하시면 굉장히 쉽습니다.

이모스 알고리즘 두 번 적용해서 두 가지 케이스 중 큰 값을 출력하면 됩니다.

 

3. 파이썬

def solution(arr: list, n: int):
    # 보정
    temp = min(arr)
    if temp != 0:
        for i in range(n):
            arr[i] -= temp
    
    # 계산
    result = [0] * (max(arr)+1)
    for i in range(n-1, -1, -1):
        result[min(arr[i], arr[i-1])] += 1
        result[max(arr[i], arr[i-1])] -= 1
    
    # 누적합 계산
    for i in range(1, len(result)-1):
        result[i] += result[i-1]

    return max(result[:-1])

 

4. 자바

static int solution(int[] arr, int n) {
    // 보정
    int temp = min(arr);
    if (temp != 0) {
        for (int i = 0; i < n; i++) {
            arr[i] -= temp;
        }
    }

    // 계산
    int[] result = new int[max(arr) + 1];
    for (int i = 0; i < n - 1; i++) {
        result[Math.min(arr[i], arr[i + 1])] += 1;
        result[Math.max(arr[i], arr[i + 1])] -= 1;
    }
    // 계산 - 맨처음 요소와 맨마지막 요소 추가 계산
    result[Math.min(arr[0], arr[n - 1])] += 1;
    result[Math.max(arr[0], arr[n - 1])] -= 1;

    // 누적합 계산
    for (int i = 1; i < result.length - 1; i++) {
        result[i] += result[i - 1];
    }

    return max(result);
}

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/17611.%E2%80%85%EC%A7%81%EA%B0%81%EB%8B%A4%EA%B0%81%ED%98%95