[Programmers] 입문) 겹치는 선분의 길이

 

이번 문제는 읽기에 쉬운 문제 같았지만 직접 풀이를 시작하니 생각보다 복잡하여 갈피를 못 잡았다.

결국 질문하기를 확인하여 다른 분들이 어떻게 문제에 접근하는지 확인하였고 그중 가장 다수가 사용하는 방식을 보았다.

 

크기가 200인 정수형 배열을 만들어 선분이 존재하는 위치를 증가시키는 것이다.

아주 간단하지만 효과적인 방법으로 보였고 여기서 조금 더 욕심을 냈다면 모든 선분의 최대/최소 크기를 받아 필요한 만큼의 크기의 배열을 만들고 안에서 계산하는 방식으로 바꾸기로 했다.

 

using System;

public class Solution {
    public int solution(int[,] lines) {
        int answer = 0;
        int minNumber = lines[0,0];
        int maxNumber = lines[0,1];
        
        for (int k = 1; k < lines.GetLength(0); k++) {
            if (lines[k,0] < minNumber) minNumber = lines[k,0];
            if (lines[k,1] > maxNumber) maxNumber = lines[k,1];
        }
        
        int[] lineCounter = new int[Math.Abs(maxNumber - minNumber) + 1]; // Including 0
        
        for (int k = 0; k < lines.GetLength(0); k++) {
            int start = lines[k,0] - minNumber;
            int end = start + (lines[k,1] - lines[k,0]);
            
            for (int j = start; j < end; j++)
                lineCounter[j]++;
        }
        
        for(int j = 0; j < lineCounter.Length; j++) {
            if (lineCounter[j] > 1)
                answer++;
        }
        
        return answer;
    }
}

 

이번 문제는 다른 분들의 기막힌 해결방법에 도움을 많이 받았다.

이외에도 리스트와 Distinct를 활용하여 해결하는 분도 확인했고 생각보다 어려운 문제의 난이도에 정답의 다양성도 넓었다.