[프로그래머스] (Java) 겹치는 선분의 길이

 

 

📑 1. 문제설명

---

💡 2. 풀이과정

선분이 겹치는 구간을 계산하려면, 각 좌표마다 선분이 몇 개 겹쳤는지 알아야 하므로, 좌표를 인덱스로 변환해서 카운팅 배열로 관리하는 방식으로 풀었다. 이 때 선언한 배열을 line[] 이라고 명명했는데 배열 크기 201인 이유는 문제에서 좌표의 범위가 -100부터 100까지이기 때문이다. 총 201개의 좌표가 존재한다. (0포함)

자바 배열 인덱스는 0부터 시작하기 때문에 만약에 200칸만 선언하면 199번째 인덱스밖에 표현하지 못한다.

그래서 크기 201짜리 int 형 배열을 선언해준다. 여기서 배열에서 선분을 표시힐 영역은 실제 lines에 들어있는 요소에서 각각 +100을 해주어야 한다. 왜냐면 배열에 마이너스 인덱스가 없기 때문에 -100+100을 해서 -100을 배열에서는 0번 인덱스로 가정하고 시작하기 때문이다.

• -100 → -100 + 100 = 0
• 100 → 100 + 100 = 200

for (int i = start; i < end; i++) {
    line[i]++;
}

이후 위 코드처럼  line에서 해당 선분이 있는 영역은 1씩 카운트한다. 

카운트가 2 이상인 부분만 리턴하면 선분이 겹치는 영역이 된다.

여기서 중요한 점은  for 문의 범위가 `[start, end)`라는 것이다.

즉 start(시작점)은 포함하고 end(끝점)은 포함하지 않는다는 것이다. 
그래야 겹치는 길이를 정확히 셀 수 있기 때문인데 예를 들면 [0, 2]는 0~1 두 칸만 포함해야 길이 2로 반환된다.

선분이 두 개 이상 겹치는 좌표 칸의 개수 = 겹치는 총 길이

---

👨‍💻 3. 정답코드

class Solution {
    public int solution(int[][] lines) {
        int[] line = new int[201];
        
        for(int[] l : lines) {
            int start = l[0] + 100;
            int end = l[1] + 100;
            for (int i = start; i < end; i++) {
                line[i]++;
            }
        }
        int answer = 0;
        for (int cnt : line) {
            if (cnt >= 2) answer++;
        }
        return answer;
    }
}

---

👏🏻 4. 좋아요 가장 많이 받은 코드

배열은 무조건 201칸 필요하지만, 아래 방식은 실제 사용된 좌표만 쓴다.

나처럼 배열을 쓰는 대신 Map<Integer, Integer>을 이용해서 선분의 각 위치를 카운팅하는 방식인데 배열 방식과 원리는 같지만, 구현 방식이 더 유연한 것 같다.

import java.util.*;
class Solution {
    public int solution(int[][] lines) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] line : lines) {
            int from = Math.min(line[0], line[1]);
            int to = Math.max(line[0], line[1]);
            for (int i = from; i < to; i++) {
                map.merge(i, 1, Integer::sum);
            }
        }

        return (int) map.values().stream().filter(i -> i > 1).count();
    }
}

 

 

아래는 별도의 배열이나 map은 선언하지 않고 푸는 방식이다.

이건 선분이 많지 않을 때 유용한 방법이다. 전체 좌표를 -100부터 99까지 훑으면서, 각 좌표가 선분에 포함되는지 직접 확인하고,
2개 이상 선분이 겹치는 구간의 길이만 누적하는 방식이다. 

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        for (int i = -100; i < 100; i++) {
            int line = 0;
            if (lines[0][0]<=i && lines[0][1]>i) line++;
            if (lines[1][0]<=i && lines[1][1]>i) line++;
            if (lines[2][0]<=i && lines[2][1]>i) line++;

            if(line > 1) answer++;
        }

        return answer;
    }
}