문제
선분 3개가 평행하게 놓여 있습니다. 세 선분의 시작과 끝 좌표가 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를 return 하도록 solution 함수를 완성해보세요.
lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다.
선분이 두 개 이상 겹친 곳은 [-2, -1], [0, 1]로 길이 2만큼 겹쳐있습니다.
- 제한사항
- lines의 길이 = 3
- lines의 원소의 길이 = 2
- 모든 선분은 길이가 1 이상입니다.
- lines의 원소는 [a, b] 형태이며, a, b는 각각 선분의 양 끝점 입니다.
- -100 ≤ a < b ≤ 100
풀이
- 오답
세 번째 케이스인 [0, 5], [3, 9], [1, 10]를 통과하지 못했다. 입출력 예시를 살펴 보니, 다음과 같았다.
첫 번째와 두 번째 선분이 [3, 5] 구간에서 겹칩니다.
첫 번째와 세 번째 선분 [1, 5] 구간에서 겹칩니다.
두 번째와 세 번째 선분 [3, 9] 구간에서 겹칩니다.
따라서 [1, 9] 구간에 두 개 이상의 선분이 겹쳐있으므로, 8을 return 합니다.
쯧.. 두 개씩 따로 겹칠 때와 달리 두 개 이상의 선분이 함께 겹칠 경우 중복된 건 제하고 반환해야 했다.
class Solution {
public int solution(int[][] lines) {
int answer = 0;
for(int i=0; i<lines.length; i++){
for(int j=i+1; j<lines.length; j++){
int f1 = lines[i][0];
int f2 = lines[j][0];
int s1 = lines[i][1];
int s2 = lines[j][1];
int overlap1 = Math.max(f1, f2);
int overlap2 = Math.min(s1, s2);
if(overlap1 < overlap2) answer += (overlap2 - overlap1);
}
}
return answer;
}
}- 정답
기존에 작성한 코드를 조금만 바꾸어 계산해 보려고 했는데, 세 개의 선분이 겹치는 구간을 체크하려면 배열 형태로 lines의 원소들을 받아야 해서 다 바꿔야 했다.
그래서 안전지대 문제를 풀었을 때처럼 -100 ~ 100 조건을 활용해 값의 전체 범위를 길이로 갖는 정수형 배열 int[] lineCount = new int[201];을 만들었다.
다음으로는 루프를 돌며 lines에서 일차원 배열을 받은 뒤, 0번 인덱스의 값과 1번 인덱스의 값을 저장한다. 이때, 값 자체를 인덱스로 사용하기 위해 +100을 더해 음수 값을 보정해 준다. -100 ~ 100이 0 ~ 200이 되는 것이다. 이렇게 정해진 범위의 값을 바꾸어 주어도 문제가 되지 않는 이유는 겹치는 범위가 아닌 길이를 반환하는 문제이기 때문이다.
그렇게 값을 받아 보정한 뒤, 해당 변수 start와 end를 범위 삼아 루프를 돌며 반복자에 해당하는 인덱스 값을 +1 한다. 그렇게 lines의 원소 3개에 해당하는 값들을 전부 체크한 다음, 루프를 돌며 lineCount 원소의 값이 1보다 클 경우 answer에 +1을 해주면 된다.
이렇게 풀이할 경우, 3개의 선분이 겹쳐 lineCount[i]의 값이 3 이상이 되어도 answer에 +1을 한 번만 해줄 수 있게 된다.
class Solution {
public int solution(int[][] lines) {
int[] lineCount = new int[201];
for(int[] line : lines){
int start = line[0] + 100;
int end = line[1] + 100;
for(int i=start; i<end; i++){
lineCount[i]++;
}
}
int answer = 0;
for(int i=0; i<lineCount.length; i++){
if(lineCount[i] > 1) answer++;
}
return answer;
}
}결과
