✔️문제
✅문제 설명
선분 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
입출력 예
lines result [[0, 1], [2, 5], [3, 9]] 2 [[-1, 1], [1, 3], [3, 9]] 0 [[0, 5], [3, 9], [1, 10]] 8
✔️풀이
🙋♀️나의 풀이
1,2,8,9번의 테스트 케이스를 통과하지 못한 코드
def solution(lines):
a1 = []
a2 = []
## 가장 작은 곳에서 시작하는 선분순으로 정렬
lines = sorted(lines, key = lambda x:x[0])
## 첫번째 선분과 두번째 선분을 모두 지나는 점을 a1에 추가
for i in range(lines[1][0], lines[1][1]+1) :
if i in range(lines[0][0], lines[0][1]+1):
a1.append(i)
## 두번째 선분과 세번째 선분을 모두 지나는 점을 a2에 추가
for i in range(lines[2][0], lines[2][1]+1) :
if i in range(lines[1][0], lines[1][1]+1):
a2.append(i)
## a1과 a2를 모두 지나는 점을 a3에 추가
a3 = [i for i in a2 if i in a1]
print(a1)
print(a2)
print(a3)
## 점이 1개만 들어가있는 경우 겹치는 선분이 만들어지지 않으므로 0으로 계산
a1_len = max(a1) - min(a1) if len(a1)>1 else 0
a2_len = max(a2) - min(a2) if len(a2)>1 else 0
a3_len = max(a3) - min(a3) if len(a3)>1 else 0
## 2개의 선분이 겹치는 길이를 더하고 3개의 선분이 겹치는 길이는 1번 빼서 계산
return a1_len + a2_len - a3_len어느 부분을 놓쳤는지 모르겠지만, 겹치는 선분을 찾는 문제이니 점이 아니라 선으로 카운트 해야겠다고 생각했다. 배열의 길이가 1인것으로 점을 판단하지 않고 처음부터 좌표선에서 겹치는 횟수를 카운트하는 코드로 다시 작성했다.
def solution(lines):
dic = {}
## 가장 작은 곳에서 시작하는 선분순으로 정렬
lines = sorted(lines, key = lambda x:x[0])
for x,y in lines:
while x<y:
if (x,x+1) not in dic:
dic[(x, x+1)] = 1
else :
dic[(x, x+1)] += 1
x += 1
count = 0
for v in dic.values():
if v>1:
count += 1
return count각 선분이 그어지는 선 : 해당 선이 겹치는 횟수로 딕셔너리를 만들었다.
lines = [[-3, -1], [0, 2], [-2, 1]] 라면
첫번째 선분으로 만들어진 딕셔너리는 다음과 같다
{ (-3, -2) : 1, (-2, -1) : 1 }
반복문을 다 돌고 나서 value가 1보다 큰 선의 수를 리턴한다.
🤔다른 사람의 풀이
def solution(lines):
sets = [set(range(min(l), max(l))) for l in lines]
return len(sets[0] & sets[1] | sets[0] & sets[2] | sets[1] & sets[2])집합으로 각 선분 안의 값을 불러온다.
나는 마지막 end까지 불러오기 위해 range(start, end+1)로 했는데 이렇게 했을 때, 점끼리 연결되어있는지 여부와 상관없이 계산되어 오류가 발생했다. 위 코드는 range(start, end)로 풀이하여 해당 오류를 발생하지 않는다. 즉, 점으로 계산하면 시작점과 끝점의 구분이 필요하므로, 시작점이 같은 것만 계산해준다.
각 선분끼리의 교집합을 구하고 각각의 교집합의 합집합의 길이를 반환한다.
👍오늘의 배운 점
💡set() 함수
그동안 set() 함수를 중복 제거에만 사용했다.
set() 함수를 사용하면 중복 제거뿐 아니라 & 교집합과 | 합집합의 사용하여 간단한 풀이를 할 수 있다.
