[코딩테스트연습] 코딩테스트 입문 > Lv.0 겹치는 선분의 길이

문제 설명

---

문제 풀이

주어진 세 개의 선분들 중 두 개 이상의 선분이 겹친 곳을 출력하는 문제이다.

가장 먼저 떠오른 생각은 배열의 원소에 하나씩 접근하면서, count를 해나가는 것이다.

 

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        int[] first = lines[0];
        int[] second = lines[1];
        int[] third = lines[2];
        
        for(int i=first[0]; i<=first[1];i++){
            if(second[0]<i & i<second[1]) answer ++;
            if(third[0]<i & i<third[1]) answer ++;  
        }
        System.out.println(answer);
        for(int i=second[0]; i<=second[1];i++){
            if(first[0]<i & i<first[1]) answer ++;
            if(third[0]<i & i<third[1]) answer ++;  
        }
        System.out.println(answer);

        for(int i=third[0]; i<=third[1];i++){
            if(second[0]<i & i<second[1]) answer ++;
            if(first[0]<i & i<first[1]) answer ++;  
        }
                     System.out.println(answer);
 
        return answer;
    }
}

출력을 확인해본 결과, 겹치는 부분이 여러번 세어지고 있는 것 같다..!

 

선분을 하나씩 순서대로 접근하다보니, 여러번 숫자가 count되고 있었다.

이를 해결하기 위해 중간에 주어진 선분으로부터 좌우 선분을 확인해야 한다고 깨달았다.

 

[try2]

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        int[] first = lines[0];
        int[] second = lines[1];
        int[] third = lines[2];
        
        for(int i=second[0]; i<=second[1]; i++){
            if(i<first[1] || third[0]<i) answer++;
            System.out.println(answer);
        }
 
        return answer;
    }
}

 

이번에는 1,3번 선분이 겹치는 부분은 인식하지 못하는 경우가 발생하고 있었다...

음....~

그럼 2번을 기준으로 1번, 3번 선분과 겹치는 부분을 찾아낸 것이므로

그 이후에 1번과 3번 선분이 겹치는지 유무를 파악한 후 그 부분까지 찾아내면 될 것 같았다.

 

[try3]

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        int[] first = lines[0];
        int[] second = lines[1];
        int[] third = lines[2];
        
        for(int i=second[0]; i<=second[1]; i++){
            if(i<first[1] || third[0]<i) answer++;
        }
        System.out.println(answer);
        if(third[0]<first[1]){
            for(int i=third[0]; i<=third[1]; i++){
                if(i<first[1] & i<second[0]) answer++;
            }
        }
    
        return answer;
    }
}

 

이번에도 마지막 테스트에서 실패했다.

어딘가 경계 값이 잘못 더해지고 있는 것 같았다..

살펴보니 2번째 선분과 3번째 선분이 겹치는 부분에서 잘못 계산이 되는 것 같았다.

 

[try4]

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        int[] first = lines[0];
        int[] second = lines[1];
        int[] third = lines[2];
        
        for(int i=second[0]; i<second[1]; i++){
            if(i<first[1] || third[0]<=i) answer++;
        }
        if(third[0]<first[1]){
            for(int i=third[0]; i<=third[1]; i++){
                if(i<first[1] & i<second[0]) answer++;
            }
        }
    
        return answer;
    }
}

이번에는 2번째, 3번째 선분의 겹치는 부분을 제대로 계산한 이후, 나머지 1번째, 3번째 선분과의 계산을 추가로 더한 코드이다. 이 결과는 다행히 테스트를 성공했다.

!!!근데 정확성 테스트에서 실패했다..

사실 코드를 작성하면서도 너무 체계적이지 못하다는 느낌이 자꾸만 들었다..

이번에는 선분 하나씩 하나씩 다시 계산해보기로 했다.

 

[try5]

class Solution {
    public int solution(int[][] lines) {
        int overlap = 0;

        // 첫 번째 선분과 두 번째 선분의 겹치는 부분을 찾음
        int start1 = lines[0][0] < lines[1][0] ? lines[1][0] : lines[0][0];
        int end1 = lines[0][1] < lines[1][1] ? lines[0][1] : lines[1][1];
        int overlap1 = end1 - start1 > 0 ? end1 - start1 : 0;

        // 첫 번째 선분과 세 번째 선분의 겹치는 부분을 찾음
        int start2 = lines[0][0] < lines[2][0] ? lines[2][0] : lines[0][0];
        int end2 = lines[0][1] < lines[2][1] ? lines[0][1] : lines[2][1];
        int overlap2 = end2 - start2 > 0 ? end2 - start2 : 0;

        // 두 번째 선분과 세 번째 선분의 겹치는 부분을 찾음
        int start3 = lines[1][0] < lines[2][0] ? lines[2][0] : lines[1][0];
        int end3 = lines[1][1] < lines[2][1] ? lines[1][1] : lines[2][1];
        int overlap3 = end3 - start3 > 0 ? end3 - start3 : 0;

        // 모든 선분이 겹치는 부분을 찾음
        int startAll = start1 > start2 ? start1 : start2;
        startAll = startAll > start3 ? startAll : start3;
        int endAll = end1 < end2 ? end1 : end2;
        endAll = endAll < end3 ? endAll : end3;
        int overlapAll = endAll - startAll > 0 ? endAll - startAll : 0;

        // 겹치는 부분의 길이를 더함
        overlap = overlap1 + overlap2 + overlap3 - overlapAll * 2;

        return overlap;
    }
}

class Solution {
    public int solution(int[][] lines) {
        int overlap = 0;

        // 첫 번째 선분과 두 번째 선분의 겹치는 부분을 찾음
        int start1 = Math.max(lines[0][0], lines[1][0]);
        int end1 = Math.min(lines[0][1], lines[1][1]);
        int overlap1 = Math.max(0, end1 - start1);

        // 첫 번째 선분과 세 번째 선분의 겹치는 부분을 찾음
        int start2 = Math.max(lines[0][0], lines[2][0]);
        int end2 = Math.min(lines[0][1], lines[2][1]);
        int overlap2 = Math.max(0, end2 - start2);

        // 두 번째 선분과 세 번째 선분의 겹치는 부분을 찾음
        int start3 = Math.max(lines[1][0], lines[2][0]);
        int end3 = Math.min(lines[1][1], lines[2][1]);
        int overlap3 = Math.max(0, end3 - start3);

        // 모든 선분이 겹치는 부분을 찾음
        int startAll = Math.max(start1, Math.max(start2, start3));
        int endAll = Math.min(end1, Math.min(end2, end3));
        int overlapAll = Math.max(0, endAll - startAll);

        // 겹치는 부분의 길이를 더함
        overlap = overlap1 + overlap2 + overlap3 - overlapAll*2;

        return overlap;
    }
}

 

겹친 부분을 겹쳐진 선분 모두에서 총 2번 빼야 하는데 이 부분을 놓쳐서 꽤 오래 걸렸다.

이번 문제를 풀면서 삼항 연산자대신 조금 더 빠른 Math함수를 사용해보기도 했고

다른 사람들의 풀이를 보면서 되게 많은 접근 방법이 있을 수 있구나를 또 한번 깨달았다 😭