100세까지 코딩
[프로그래머스] 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로도 결국 구할 수 있는 것이었다..
좀 더 열심히 해야겠다 ㅜ..
'코딩테스트 > 자바' 카테고리의 다른 글
[프로그래머스] Lv0.연속된 수의 합 (0) | 2023.08.13 |
---|---|
[프로그래머스] Lv0.분수의 덧셈 (0) | 2023.08.13 |
[프로그래머스] Lv0.평행 (0) | 2023.08.09 |
[프로그래머스] Lv0.다음에 올 숫자 (0) | 2023.08.08 |
[프로그래머스] Lv0.옹알이 (0) | 2023.08.08 |