[SWEA] 10580. 전봇대 (Python/D3)

---

[문제 링크] 👇

SW Expert Academy

---

풀이 방법

💡 전선이 교차하려면 서로 다른 두 전선 (x, y)와 (i, j)에 대해, 다음 조건이 성립해야 한다.

• x < i 이면서 y > j (왼쪽 끝점은 더 왼쪽에 있지만, 오른쪽 끝점은 더 아래쪽에 있음)
• 또는 x > i 이면서 y < j (왼쪽 끝점은 더 오른쪽에 있지만, 오른쪽 끝점은 더 위쪽에 있음)

 

입력 받기

• 각 전선의 (A, B) 좌표를 리스트 a, b에 각각 저장한다.

교차 조건 체크

• 각 전선 (x, y)와 다른 전선 (i, j)의 좌표를 비교하여, 교차 조건이 성립하는지 확인한다.
• 교차 조건이 성립할 때마다 result 값을 증가시킨다.

출력하기

• 각 테스트 케이스에 대한 result 값을 출력한다.

Solution

T = int(input())  # 테스트 케이스 수
for test_case in range(1, T + 1):
    N = int(input())  # 전선 개수
    a, b = [], []
    for _ in range(N):
        A, B = map(int, input().split())
        a.append(A)
        b.append(B)

    result = 0
    for x, y in zip(a, b):
        for i, j in zip(a, b):
            if x < i and j < y:
                result += 1
    print(f"#{test_case} {result}")

 

 

개선할 점

위 코드는 O(N^2) 복잡도로 모든 전선 쌍을 비교하고 있다. 입력이 커질 경우 이 방식은 시간 초과 가능성이 있으므로, 효율적인 정렬이나 스위핑 기법을 고려해볼 수 있다.

교차 전선 문제를 효율적으로 해결하기 위해, 전선을 시작점 A에 대해 오름차순으로 정렬한 후, 끝점 B에 대해 역순으로 정렬하면서 교차를 확인할 수 있다. 이 방법은 A를 기준으로 오름차순 정렬을 수행해 순서를 고정하고, 이후에 B 값을 비교하면서 전선을 비교하는 것으로, 중복된 비교를 줄여 효율을 높일 수 있다.

• 전선 정렬
  • 전선의 시작점 A에 대해 오름차순 정렬한다. 이렇게 하면 같은 순서에서 시작하는 전선들이 한 번만 계산되도록 만들 수 있다.
• 끝점 리스트 관리
  • 끝점 B는 새로운 끝점을 계속 추가해가며 교차 수를 계산한다.
  • 교차 조건이 충족되면 result를 증가시킨다.

 

개선된 코드

T = int(input())  # 테스트 케이스 수
for test_case in range(1, T + 1):
    N = int(input())  # 전선 개수
    wires = []
    
    for _ in range(N): # 전선 입력 받기
        A, B = map(int, input().split())
        wires.append((A, B))
   
    wires.sort() # 시작점 A 기준으로 정렬
    result = 0
    ends = []
    
    for _, B in wires: # 끝점 B 비교를 위한 리스트
        # 현재 끝점보다 큰 끝점 중 오른쪽에 있는 끝점을 찾아 교차 수 확인
        result += sum(1 for end in ends if end > B)
        ends.append(B) # 끝점 리스트에 추가
    
    print(f"#{test_case} {result}")

 

---