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

 

❤️ Problem

• 문제
  빨간색, 초록색, 파란색 선분이 x축 위에 있습니다. 세 선분의 x좌표 시작과 끝이 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를return 하도록 solution 함수를 완성해보세요.
  
  lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다.

 

• 제한 사항
  • lines의 길이 = 3
  • lines의 원소의 길이 = 2
  • 모든 선분은 길이가 1 이상입니다.
  • lines의 원소는 [a, b] 형태이며, a, b는 각각 양 끝점 중 하나입니다.
  • -100 ≤ a < b ≤ 100

 

• 입출력 예 & 설명

no	lines	result
1	[[0, 1], [2, 5], [3, 9]]	2
2	[[-1, 1], [1, 3], [3, 9]]	0
3	[[0, 5], [3, 9], [1, 10]]	8

1. 초록색과 파란색 선분이 [2, 5], [3, 9]로 [3, 5]만큼 겹쳐있으므로 2를 return 합니다.
2. 겹친 선분이 없으므로 0을 return 합니다.
3. 빨간색과 초록색 선분 [3, 5]부분이 겹칩니다.
   빨간색과 파란색 선분 [1, 5]부분이 겹칩니다.
   초록색과 파란색 선분이 [3, 9]부분 겹칩니다.
   따라서 8을 return 합니다.

 

---

 

💛 Solution

풀이

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

        int[] line0 = countLines(countDots(lines[0][0], lines[0][1]));
        int[] line1 = countLines(countDots(lines[1][0], lines[1][1]));
        int[] line2 = countLines(countDots(lines[2][0], lines[2][1]));

        for(int i=0; i<line0.length; i++) {
            if(line0[i]+line1[i]+line2[i]>1) {
                answer++;
            }
        }

        return answer;
    }

    public static int[] countDots(int start, int end) {

        int[] cntDots = new int[201];

        for(int i=start+100; i<=end+100; i++) {
            cntDots[i]++;
        }

        return cntDots;
    }


    public static int[] countLines(int[] cntDots) {

        int[] cntLines = new int[200];
        for(int i=1; i<cntDots.length; i++) {
            if(cntDots[i-1]==1 && cntDots[i]==1) {
                cntLines[i-1]++;
            }
        }
        return cntLines;
    }
}

 

처리속도 Very Good

 

---

 

💜 Comment

처음 작성한 코드는 다음과 같다.

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

        int[] cnt = new int[201];
        for(int i=0; i<lines.length; i++) {
            int start = lines[i][0];
            int end = lines[i][1];

            for(int j=start; j<=end; j++) {
                cnt[100+j]++;
            }
        }

        for(int i=1; i<cnt.length; i++) {
//            System.out.println(i+" = "+cnt[i]);
            if(cnt[i-1]>1 && cnt[i]>1) {
                answer++;
            }
        }

        return answer;
    }
}

 

선분이라 함은 점끼리의 연결이니, 점의 총 개수를 모두 포함할 수 있는 배열을 만들어서 start(a점)와 end(b점) 사이의 숫자를 인덱스로 하는 값에 +1을 하는 반복문을 만들었다.

여기서 " -100 ≤ a < b ≤ 100 " 라는 조건이 걸려있었다. 인덱스는 0보다 큰 수만 가능하므로 -100을 상쇄하기 위해 a점과 b점 사이의 숫자에 100을 더한 값이 인덱스가 되도록 구성하였다. 0부터 200까지의 숫자가 인덱스에 해당하므로 int[] cnt = new int[201];가 되었다.

하지만 실행해보니 다음과 같이 테스트 3번과 테스트 7번을 실패하는게 아닌가

 

내가 고려하지 않은 부분이 무엇인지 한참 고민했는데, 의외로 반례는 문제 설명에 들어있었다.

lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다.

 

여기서 보면 [-3, -1]는 종료점이 -1이고 [0, 2]는 시작점이 0이다. 내가 처음 구상한대로 코드를 짜게되면 점마다 +1을 하게 되므로 -1과 0에 1이 추가되므로 선분이 아닌 것이 마치 선분처럼 보이는 결과가 일어난 것이다!

for문으로 cnt[i]를 출력해보면 99번째와 100번째가 각각 서로 다른 선분의 종료점과 시작점인데도 구분이 불가능하다. cnt[i-1]>1 && cnt[i]>1라는 조건만으로는 선분인지를 판단하기가 어려웠다. 사실 의미 자체는 연속된 점의 값이 각각 1이상인지에 지나지 않았으니까.

그래서 풀이에 쓴 방식은 점의 개수를 구한 다음에 선분으로 치환하는 작업을 추가한 것이다.

먼저 countDots 메서드를 만들었다. 여기서는 인수로 각 선분의 시작점과 종료점을 전달하면 그 값에 100을 더한 뒤, 해당 범위 내에 있는 숫자를 인덱스로 하는 배열 cntDots의 값에 1을 더하도록(cntDots[i]++;) 만들었다. 이때, 배열은 공통으로 사용하지 않고 선분마다 다르게 가진다. 여기까지는 점의 개수를 세는 방식이므로 이전 코드와 동일해보인다. 다른 점은 하나의 배열에 그 값을 누적하는 방식을 택하지 않았다는 점이다.

그런 다음에 countLines 메서드를 만들어서 각 선분의 점 배열을 기반으로 " cnt[i-1]==1 && cnt[i]==1 "인 경우에 새로 생성한 배열의 i-1인덱스의 값이 1씩 증가하도록(cntLines[i-1]++;) 구현했다. 여기서 cntLines[i-1]이 의미하는 바는 "시작점을 cnt[i-1]로 가지는 길이가 1인 선분"이다. 제시된 선분 하나를 시작점을 기준으로 길이를 1로 가정하여 동강동강 잘라둔 것.

그런 다음 반복문을 사용해서 lines0[i]+lines1[i]+lines2[i]한 값이 1보다 크면 겹쳐있다는 의미이므로 answer++;를 수행해주면 끝!!

 

8점!!!!!!!!! 고생한 보람이 있다 헿❤ 현재 순위 12216위 💪