[프로그래머스] Lv0.겹치는 선분의 길이

문제 설명

 

 

풀기 전 생각

• 솔직히 너무 막막했다... 수학적으로 풀어야 되는 건지..
• 일단 해보자는 생각으로 선분 a-b, a-c, b-c를 비교
• 두 점 중 start는 더 큰 숫자로, end는 더 작은 숫자로 하면 겹치는 부분 나옴
• end - start를 해서 음수면 안 겹쳐지는 것이므로 양수일 때만 더함

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        int[][] duplicate = new int[3][2]; // 겹친 선분 [start, end] 저장
        int k = 0;  // duplicate 차례로 넣기 위한 변수
        int sum = 0;  //겹친 부분 합하기 위한 변수

        for(int i = 0; i < lines.length-1;i++) {
            for (int j = i + 1; j < lines.length; j++) {  // 선분 a-b, a-c, b-c 비교
                int start = lines[i][0] > lines[j][0] ? lines[i][0] : lines[j][0];
                // 두 start 점 중에 더 큰것
                int end = lines[i][1] > lines[j][1] ? lines[j][1] : lines[i][1];
                // 두 end 점 중에 더 작은것
                duplicate[k][0] = start;
                duplicate[k++][1] = end;
            }
        }
        for (int i=0; i < duplicate.length;i++){
            if(duplicate[i][1] - duplicate[i][0] > 0){ // 음수면 안겹치는 것
                sum += duplicate[i][1] - duplicate[i][0];  // end - start 한것 더해줌
            }
        }
        answer = sum;
        return answer;
    }
}

오류 및 개선

• 입출력 예 1,2번은 통과했지만 3번에서 막힘
• 선분 3개가 겹치거나 아예 포함되어 있으면 중복을 빼줘야 함
• min, max까지 추가하여 4시간 고민했지만 안 풀려 결국 질문을 참고..

프로그래머스 질문게시판에서 가져온 글

최종

class Solution {
    public int solution(int[][] lines) {
        int answer = 0;
        int[] duplicate = new int[201];   // -100~100까지 값을 저장하기위한 배열

        for(int i = 0; i < 201; i++){   // 음수는 배열에서 오류가 나므로 0부터시작
            int cnt = 0;  // 배열마다 개수를 체크하기 위한 변수
            for(int j = 0; j < lines.length;j++){
                if(lines[j][0] <= i - 100 && i - 100 < lines[j][1]){ //정수 구간은 (i <= x < i+1)
                    //해당 선분안에 포함되어있는 정수인지 확인
                    duplicate[i] = ++cnt; // 포함되어있으면 ++cnt
                }
            }
        }

        for(int i = 0 ; i <201;i++){
            if( duplicate[i] >= 2 ) {
                answer++;  //cnt가 2이상이면 선분 2개이상 겹친것이므로 answer+1;
            }
        }
        return answer;
    }
}

참고

def solution(lines):
    overlaps = []  # 겹치는 부분을 저장할 리스트
    for i in range(len(lines)):
        for j in range(i+1, len(lines)):
            if lines[i][1] >= lines[j][0] and lines[i][0] <= lines[j][1]:
                # 두 선분이 겹치는 경우
                overlap_start = max(lines[i][0], lines[j][0])
                overlap_end = min(lines[i][1], lines[j][1])
                overlap_length = overlap_end - overlap_start

                # 중복 계산 방지 및 중첩되는 부분 제거
                for start, end in overlaps:
                    if overlap_start <= end and overlap_end >= start:
                        overlap_start = min(overlap_start, start)
                        overlap_end = max(overlap_end, end)
                        overlap_length = overlap_end - overlap_start
                        overlaps.remove((start, end))

                overlaps.append((overlap_start, overlap_end))

    # 겹치는 부분들의 길이 합산
    total_length = sum([end - start for start, end in overlaps])

    return total_length

효율성은 떨어지지만 min, max로도 결국 구할 수 있는 것이었다.. 

좀 더 열심히 해야겠다 ㅜ..