[프로그래머스, Java] Level0: 겹치는 선분의 길이

 

 

Level0 이지만, 학습할 점이 많은 문제라서 가져왔습니다.

문제분석:

 

목표: [start,end] 로 구분이된 선분들의 겹치는 선분의 길이 구하기

 

 

First Try:  모든 선분 [Start ~ End] 까지 +1을 한뒤,

 2가 넘으면 answer++ 증가 

 

-> 보자마자 이 전략이 떠올랏습니다. 하지만,  윗 그림과 같은 케이스에서 문제가 일어납니다.

 

[[0, 2], [-3, -1], [-2, 1]] 와 같이  중간이 파여버린 부분은 해당로직이 인식을 못하여 4를반환합니다.

 

2를 반환해야 하는데 말이죠, 그렇다고 정확히 파악할수있는 0.5점을 파악하기도 힘듭니다.

 

Second Try:  Start가 낮은 선분부터 선분을그려 +1을한뒤, 실시간으로 2가 넘으면 answer++ 증가

(단, 이미 체크한 점 (방문한 점)은 제외)

import java.util.*;
class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
 
        int[] arr= new int[202]; 
        boolean[] visited= new boolean[202];
 
        Arrays.sort(lines,(a,b)->a[0]-b[0]);
 
        for(int[] line : lines){
            int start= line[0]+100;
            int end= line[1]+100;
 
            for(int i=start;i<=end;i++){
                if(arr[i+1]>0&&i!=end&&!visited[i]){
                    answer++;
                    visited[i]=true;
                }
                arr[i]+=1;
            }
        }
 
        return answer;
    }
}

 

Third Try:  모든 선분 [Start ~ End-1] 까지 +1을 한뒤,

  2가 넘으면 answer++ 증가 

 

전략을보면 첫번째 전략과 종이 한장차이입니다. 

이 코드가 정확하게 해당문제에 적합한 코드입니다.

import java.util.*;
class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        
        int[] arr= new int[202]; 
        
        for(int[] line : lines){
            int start= line[0]+100;
            int end= line[1]+100;
            
            for(int i=start;i<end;i++){
                arr[i]+=1;
            }
        }
        
        for(int num:arr){
            if(num>1){
                answer++;
            }
        }
 
        return answer;
    }
}

 

허나, 이 코드가 어떻게 예제처럼 중간이 빈 부분까지 체크를 정확하게 할수있을까요?

 

앞서 말햇듯이, "선분이 겹치는 부분"을 정확히 판단하려면

점과 점을 이은, 0.5부분을 판단하는게 현명합니다.

 

그렇지만, 0.5부분을 판단하거나,

끝점과 시작점의 연속됨을 판단하는등.. 로직이 좀 복잡해집니다.

 

하지만, [시작점은 포함하고  끝점은 포함하지 않으며] 값을 올리면

0.5부분만 점을 찍는것과 같습니다.

한번 직접 테스트케이스를 그려보고 찍히는점들을 0.5씩 밀어보면 똑같습니다.