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

<문제 제시>

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

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

<예시 입출력>

---

<문제 해결 과정>

다양한 조건을 모두 만족하는 코드를 짜는것이 목표였다.

Try 1) 

int answer = 0;
        
int min = lines[0][0]; // 첫요소의 x값 
int max = lines[0][1]; // 첫요소의 y값

// 가장 좌측과 우측에 해당하는 인덱스를 구함
int min_index = 0;
int max_index = 0;

// 가장 좌측의 직선을 구하는 로직 (x값 (시작점) 비교)
for(int i = 0; i < lines.length; i++) {
    if(lines[i][0] < min) {
        min = lines[i][0];
        min_index = i;
    }
}

// 가장 우측의 직선을 구하는 로직 (y값 (끝점) 비교)
for(int i = 0; i < lines[0].length; i++) {
    if(lines[i][1] > max) {
        max = lines[i][1];
        max_index = i;
    }
}

// 겹치는 선분 구하기
int overlap_index = 0;
for(int i = 0; i < lines.length; i++) {
    if(i != min_index && i != max_index) {
        overlap_index = i;
    }
}

System.out.println("가장 좌측 선분 [" + lines[min_index][0] + ", " + lines[min_index][1]
        + "], 그 직선의 위치 = " + min_index + "번째 직선");
System.out.println("가장 우측 선분 [" + lines[max_index][0] + ", " + lines[max_index][1]
        + "], 그 직선의 위치 = " + max_index + "번째 직선");
System.out.println("겹치는 선분  [" + lines[overlap_index][0] + ", " + lines[overlap_index][1]
        + "], 그 직선의 위치 = " + overlap_index + "번째 직선");

System.out.println("----------");
// 겹치는지 검사
// 1. 겹치는 선분(overlap_index)의 시작점이 좌측 선분의 끝점보다 작으면, = 겹친다고 판단
if(lines[0][min_index] > lines[overlap_index][0]) {
    answer += Math.abs(lines[min_index][1] - lines[overlap_index][0]);

    // 진행과정을 보기위한 프린트문
    System.out.println("좌표 [" + lines[min_index][0] + ", " + lines[min_index][1]
            + "]에서 끝점인 " + lines[min_index][1]
            + "에서  좌표 [" + lines[overlap_index][0] + ", " + lines[overlap_index][1]
            + "] 의 시작점 " + lines[overlap_index][0] + "을 차감(절대값 차이)하면, \n길이 = "
            + Math.abs(lines[min_index][1] - lines[overlap_index][0]) + "를 answer에 누적 = " + answer);
}

System.out.println("----------");

// 2. 겹치는 선분(overlap_index)의 끝점이 우측 선분의 시작점보다 크면, = 겹친다고 판단  
if(lines[overlap_index][1] > lines[max_index][0]) {
    answer += Math.abs(lines[overlap_index][1] - lines[max_index][0]);

    // 진행과정을 보기위한 프린트문
    System.out.println("좌표 [" + lines[overlap_index][0] + ", " + lines[overlap_index][1]
            + "]에서 끝점인 " + lines[overlap_index][1]
            + "에서  좌표 [" + lines[max_index][0] + ", " + lines[max_index][1]
            + "] 의 시작점 " + lines[max_index][0] + "을 차감(절대값 차이)하면, \n길이 = "
            + Math.abs(lines[overlap_index][1] - lines[max_index][0]) + "를 answer에 누적 = " + answer);
}

System.out.print("겹치는 부분의 길이 = ");
return answer;

진행과정을 프린트하여 직관적으로 풀어보고자 하였으나, 모두 겹치는 경우의 조건을 구현하지 못하여 오답이었다.

가장 좌측의 직선 min을 업데이트해나가고, 가장 우측의 직선 max를 업데이트해나가며,

가장 넓은 범위를 제한시키고, 그 안에서 겹치는 선분을 구하기위해

overlap_index 를 선언하였다. 

if문에서 lines[N] 값을 비교하여 절대값으로 answer에 누적시켜 답을 구해보고자하였으나, 모든 조건을 만족하지 못하였다.

Try 2)

int answer = 0;
        
// 점 [-100] 에서 점 [100]까지 모두 0으로 되어있을때,
// 각 선분 (0,5), (3,9), (1, 10)을 lineArr에 1로 표시
int[] lineArr = new int[200];

for (int[] line : lines) {
    int tempMin = Math.min(line[0], line[1]);
    int tempMax = Math.max(line[0], line[1]);
    System.out.println("가장 좌측 시작점 = " + tempMin);
    System.out.println("가장 우측 끝점 = " + tempMax);
    for (int i = tempMin; i < tempMax + 1; i++) {
        lineArr[i + 100]++;
    }
}


//         1로만 표시되는 건 그 점을 지나갔다는 의미,
//         1이상 표시되는 것이 겹치는 부분을 뜻하므로
//                      조건문을 x > 1로 달아주어 검사, 점(0)이 1이상이라면 그 다음인 점(1)도 1이상이어야하기때문에 
//         lineArr[i-1]을 시작점으로 두어 인덱스 범위 예외가 발생하지 않도록 처리

for (int i = 1; i < lineArr.length; i++) {
    if (lineArr[i - 1] > 1 && lineArr[i] > 1) {
        answer++;
        //System.out.println("점 (" + lineArr[i-1] + ") 부터, 점 (" + lineArr[i] + ")까지 겹치는 지점이므로 answer값 증가 (" + answer + ")");
    }
}

return answer;

>> 1. 선분의 길이는 -100 ~ 100 까지 주어지므로, 1차원 배열에 길이 200을 선언하여 받아옴
>> 2. for(int [] line : lines)로 각 요소를 1차원배열로 받아와서 최소값과 최대값을 구함     
>> 몇몇 테스트케이스에서 오답이었다.

 

 

 

Solution 1)

for (int[] line : lines) {
    int tempMin = Math.min(line[0], line[1]);
    int tempMax = Math.max(line[0], line[1]);

    for (int i = tempMin + 1; i < tempMax + 1; i++) {
        String str = (i - 1) + "/" + i;
        System.out.println(str);

        /*
        map.getOrDefault : 찾는 키가 존재한다면 키의 값을 반환하고
        존재하지 않는다면 기본 값을 반환 (키, 기본값)을 인자로 가짐

        HashMap의 경우 동일 키 값을 추가할 경우 Value의 값이 덮어쓰기되므로
        기존 키 값의 value를 유지하고자할때 getOrDefault 메서드 사용
        */
        map.put(str, map.getOrDefault(str, 0) + 1);
    }
}

// Try2)와 마찬가지로 map의 값들 중 정수형 값으로 value로 받아와
// value가 2이상일 경우(겹치는 것이므로) 카운트하여 반환한다.
for (Integer value : map.values()) {
    if (value > 1) answer++;
}

 

HashMap<String, Integer> 를 선언하여 HashMap의 getOrDefault() 메서드를 활용하였다.

Math.min()과 Math.max()의 메서드를 통해 선분의 범위를 구하고,

N / M 방식의 String값을 Hashmap에 넣어가며, 이 키가 ((K, V) 순서에서 Key 에 String이 선언되었으므로) String과 일치한다면, N / M 과 동일한 값을 가진다면 V 값이 증가 (+1)된다.

for-each문을 통해 map의 value()들 즉 Integer값들을 받아와, 그 값이 1 초과이면 (=2이상) 겹치는 선분이므로

answer++로 answer값을 구하게 된다.

---

<전체코드>

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

public class overlap_line {

	public static int solution(int[][] lines) {
        int answer = 0;

        Map<String, Integer> map = new HashMap<String, Integer>();

        for (int[] line : lines) {
            int tempMin = Math.min(line[0], line[1]);
            int tempMax = Math.max(line[0], line[1]);
            
            for (int i = tempMin + 1; i < tempMax + 1; i++) {
                String str = (i - 1) + "/" + i;
                System.out.println(str);
                
                /*
             	map.getOrDefault : 찾는 키가 존재한다면 키의 값을 반환하고
             	존재하지 않는다면 기본 값을 반환 (키, 기본값)을 인자로 가짐
             	
            	HashMap의 경우 동일 키 값을 추가할 경우 Value의 값이 덮어쓰기되므로
            	기존 키 값의 value를 유지하고자할때 getOrDefault 메서드 사용
                */
                map.put(str, map.getOrDefault(str, 0) + 1);
                System.out.println(map);
            }
        }

        // Try2)와 마찬가지로 map의 값들 중 정수형 값으로 value로 받아와
        // value가 2이상일 경우(겹치는 것이므로) 카운트하여 반환한다.
        for (Integer value : map.values()) {
            if (value > 1) answer++;
        }

        return answer;
    }
	
	public static void main(String[] args) {
		// 예시
//		int[][] lines = {{0, 2}, {-3, -1}, {-2, 1}};
		
		// 테스트케이스
//		int[][] lines = {{0, 1}, {2, 5}, {3, 9}};
		int[][] lines = {{0, 5}, {3, 9}, {1, 10}};
		
		System.out.println(solution(lines));
	}

}

---

HashMap의 getOrDefault()메서드를 활용할 수 있었다. 겹치는 선분을 단순히 그림으로만 생각하지 않고,

누적되는 데이터로 생각한다면 2이상 값을 count하는 부분을 통해 구해낼 수 있는 문제였다.

 

---

문제링크)
https://school.programmers.co.kr/learn/courses/30/lessons/120876

프로그래머스