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

문제

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

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

 

선분이 두 개 이상 겹친 곳은 [-2, -1], [0, 1] 로 길이 2만큼 겹쳐있습니다.

제한사항

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

입출력 예

lines	result
[[0, 1], [2, 5], [3, 9]]	2
[[-1, 1], [1, 3], [3, 9]]	0
[[0, 5], [3, 9], [1, 10]]	8

 

---

코드(Java) - 내 코드

class Solution {
    public int solution(int[][] lines) {
        int[] count = new int[201];
        for(int i=0; i<3; i++) {
            for(int j=lines[i][0]+100; j<lines[i][1]+100; j++) {
                count[j]++;
            }
        }
        
        int answer = 0;
        for(int i=0; i<count.length; i++) {
            if(count[i] > 1) {
                answer++;
            }
        }
        return answer;
    }
}

코드(Java) - 다른 사람 코드

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(int[][] lines) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i=0; i<lines.length; i++) {
            for(int j=lines[i][0]; j<lines[i][1]; j++) {
                map.put(j, map.getOrDefault(j, 0)+1);
            }
        }
        
        int answer = 0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue() > 1) {
                answer++;
            }
        }
        return answer;
    }
}

풀이 과정

처음 문제를 봤을 때는 규칙을 찾아내기 위한 노력을 했다. 1시간이 넘게 매달렸는데 실행을 시켜보니 일부의 테스트케이스에서 실패라는 결과가 나왔다. 반례를 찾으면 찾을수록 새로운 반례가 계속해서 생기는것을 보고 접근방법이 잘못되었다는 생각을 하게되었다.

코드를 전부 지우고 새로 접근한 방법은 배열을 활용하는 방법이었다.

 

1. 배열을 만들어 선의 점에 해당하는 인덱스의 값을 1씩 증감해준다.

   ex) 겹치는 구간이 [3, 5] 라면, 해당 구간의 점은 3과 4 이므로 배열 count[3]과 count[4]를 1씩 증감한다.

2. 1번을 그대로 적용했을 때 발생하는 문제는 음수에 해당하는 인덱스는 존재할 수 없다는것이다. 입력값이 -100과 100사이에 존재한다는 제약사항이 있기 때문에 모든 값에 +100 을 하여 모든 인덱스를 0 이상의 값으로 만들어준다.

3. 배열의 값이 1보다 큰 값의 개수가 겹치는 선의 길이임을 확인할 수 있다.

 

코드가 정상적으로 실행된 후, 다른 사람의 코드를 찾아보니 HashMap 을 사용하여 코드를 짜는 방법이 있었다.

코드의 흐름 자체는 내가 작성한 코드와 비슷하다. 두 코드의 차이라 하면, HashMap을 사용하면 배열로 작성했을 때처럼 201개의 배열 공간을 낭비할 필요가 없고 음수에 대한 인덱스를 고려할 필요가 없다는 장점이 있다.

 

알고리즘 문제를 풀다보면 생각보다 HashMap 을 활용하여 성능 좋고 깔끔한 코드를 작성할 수 있는 경우가 많다.

HashMap 사용법에 대해 공부를 더 해보고 앞으로 코드에 적용을 해야겠다는 생각을 했다.

 

---

알게된 내용

1. 실제 코드에서 사용을 하진 않았지만, 이차원 배열을 정렬하는 방법을 찾아보다 알게된 내용을 기록해두려고 한다.

아래 코드는 람다식을 활용하여 이차원 배열을 정렬하는 방법이다.

//Lambda 사용 (Java 8 이상)
int[][] arr = new int[][] {{5, 3}, {2, 4}, {6, 1}, {5, 2}};
//1. 첫번째 값 기준 오름차순 정렬
Arrays.sort(arr, (o1, o2) -> o1[0]-o2[0]); //{{2, 4}, {5, 3}, {5, 2}, {6, 1}}

//2. 두번째 값 기준 내림차순 정렬
Arrays.sort(arr, (o1, o2) -> o2[1]-o1[1]; //{{6, 1}, {5, 3}, {5, 2}, {2, 4}}

//3. 첫번째 값 기준 오름차순 정렬 (두번째 값도 정렬)
Arrays.sort(arr, (o1, o2) -> o1[0]==o2[0] ? o1[1]-o2[1] : o1[0]-o2[0]); //{{2, 4}, {5, 2}, {5, 3}, {6, 1}}

2. HashMap 코드를 분석하다가 getOrDefault 의 의미에 대해 찾아보게 되었다.

getOrDefault 란, 찾는 키가 존재한다면 찾는 키의 값을 반환하고 키가 존재하지 않는다면 기본 값을 반환하는 메서드이다.

 

아래 코드는 위에 작성된 코드 활용한 사용방법이다.

for(int j=lines[i][0]; j<lines[i][1]; j++) {
    map.put(j, map.getOrDefault(j, 0)+1);
}
//j라는 Key에 매핑된 값이 없는 경우 디폴트값(0)을 map에 put
//j라는 Key에 매핑된 값이 있는 경우 (매핑되어있는 값+1)을 map에 put