[프로그래머스] 겹치는 선분의 길이 - 문제 해석 및 Java풀이

백준 문제만 풀어봤는데 예전에 동료가 기업 코딩테스트를 프로그래머스에서 많이들 한다고 해서 가입만 해놓고 풀어보지 않았던 것이 생각나 풀어보게 되었다. 바로바로 실행해 볼 수 있다는 점과 직관적인 것이 되게 장점이라고 생각이 되었다.

  

겹치는 선분의 길

선분 3개가 평행하게 놓여 있습니다. 세 선분의 시작과 끝 좌표가 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를 return 하도록 solution 함수를 완성해보세요.

lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다.

제한사항

• lines의 길이 = 3
• lines의 원소의 길이 = 2
• 모든 선분은 길이가 1 이상입니다.
• lines의 원소는 [a, b] 형태이며, a, b는 각각 선분의 양 끝점 입니다.
• -100 ≤ a < b ≤ 100

 

입출력 예

 

입출력 예 설명

입출력 예 #1

• 두 번째, 세 번째 선분 [2, 5], [3, 9]가 [3, 5] 구간에 겹쳐있으므로 2를 return 합니다.

입출력 예 #2

• 겹친 선분이 없으므로 0을 return 합니다.

입출력 예 #3

• 첫 번째와 두 번째 선분이 [3, 5] 구간에서 겹칩니다.
• 첫 번째와 세 번째 선분 [1, 5] 구간에서 겹칩니다.
• 두 번째와 세 번째 선분 [3, 9] 구간에서 겹칩니다.
• 따라서 [1, 9] 구간에 두 개 이상의 선분이 겹쳐있으므로, 8을 return 합니다.

 

문제 풀이

처음에 문제를 파악할 때 잘못 파악해서 입출력 예 3에서 오답이 나왔다. 

 

위 사진과 같이 선분이 있을 때

노란선분과 빨간선분이 겹치는 부분의 길이 6,

노란선분과 검정선분이 겹치는 부분의 길이 2,

빨간선분과 검정선분이 겹치는 부분의 길이 4

이렇게 각각의 겹치는 부분들의 합을 구하는 것으로 파악하고 코드를 작성하여, 12의 return값을 출력하게 되었다. 

 

하지만 실제 문제에서는 단순히 겹치는 길이의 합을 구하는 것이 아니라, 겹친 부분들의 전체 길이, 즉 교집합을 구하는 것이었다. 이를 그림으로 표현하면 아래와 같다.

"교집합? 중복을 제거한 겹친 부분의 길이를 구하라는 뜻인가?"라는 생각이 들어, 중복을 허용하지 않는 Set을 활용하여 겹치는 좌표들을 저장했다. 그리고 최종적으로 Set의 크기를 겹친 선분의 총 길이로 판단했다.

 

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int[][] lines) {
        Set<Integer> pointSet = new HashSet<>();
        
        for (int i = 0; i < lines.length; i++) {
            for (int j = i + 1; j < lines.length; j++) {
                int startPoint = Math.max(lines[i][0], lines[j][0]); // 두 선분의 시작점 비교
                int endPoint = Math.min(lines[i][1], lines[j][1]);   // 두 선분의 종료점 비교
                
                // 겹치는 건지 확인 
                if (startPoint < endPoint) {
                    for (int k = startPoint; k < endPoint; k++) {
                        pointSet.add(k); // 겹치는 지점 저장 Set이니깐 중복 허용x
                    }
                }
            }
        }
        return pointSet.size();
    }
}

 

마무리

난이도가 쉬운 문제였지만 처음에 문제의 의도를 잘못 파악하고, 조금 많은 시간을 소비하였다. 문제를 푼 후 다른 사람들의 풀이를 보았는데 나와 같이 Set을 사용한 사람도 있었지만 정말 다양한 풀이들이 있었다. Map을 사용한 사람이 있는가 하면 문제에 주어진 -100부터 100까지 for문을 돌린 사람도 있었다.

 

프로젝트가 바쁘기도 하고, 게을러서 최근에 문제를 안 풀었는데 여유가 될 때 블로그 글도 작성하고 문제도 틈틈이 풀어야겠다고 생각했다.