백준 3009번 - 네 번째 점 [Python]

https://www.acmicpc.net/problem/3009

3009번: 네 번째 점

 

안녕하세요, 백준 3009번 문제 '네 번째 점' 문제 풀이 하겠습니다. 이 문제는 간단한 아이디어를 통해 풀 수 있는 문제이지만, 리스트나 문자열에서 특정 조건을 만족하는 요소를 찾는 기술을 연습하는 데에 좋습니다.

 

문제 이해

문제에서 직사각형의 세 꼭지점의 좌표를 알고 있습니다.  네 번째 점의 좌표를 찾는 것이 이 문제의 목표입니다. 각 좌표는 절대값이 1000보다 작거나 같은 정수입니다.

 

문제 접근 방식

이 문제를 풀기 위한 핵심 아이디어는 '직사각형의 꼭지점 중에서, 같은 x좌표를 가지는 점은 두 개이고, 같은 y좌표를 가지는 점도 두 개'입니다. 따라서, 세 점의 좌표를 알고 있다면, 누락된 네 번째 점의 x좌표와 y좌표는 각각 한 번만 등장하는 x좌표와 y좌표가 될 것입니다.

이를 위해, Python의 내장 함수인 list.count()를 사용하여 각 x좌표와 y좌표의 등장 횟수를 세고, 한 번만 등장하는 좌표를 찾습니다. 그런 다음, 이렇게 찾은 x좌표와 y좌표를 합쳐서 네 번째 점의 좌표를 만듭니다.

 

코드 작성

arr = [
    list(map(int, input().split()))
    for _ in range(3)
]

def solution(arr):
    # x, y 좌표를 각각 따로 저장하는 리스트를 만듭니다.
    x_num = [x for x, _ in arr]
    y_num = [y for _, y in arr]

    # 한 번만 등장하는 x, y 좌표를 찾는 함수를 만듭니다.
    def find_xy(xy_num):
        for i in xy_num:
            if xy_num.count(i) == 1:
                return i

    # 한 번만 등장하는 x, y 좌표를 찾습니다.
    x = find_xy(x_num)
    y = find_xy(y_num)

    # 찾은 x, y 좌표를 반환합니다.
    return x, y


print(solution(arr))

이렇게 구현한 함수를 테스트해보면, 주어진 세 점의 좌표로부터 네 번째 점의 좌표를 정확히 찾을 수 있습니다. 예를 들어, 세 점의 좌표가 [(5, 5), (5, 7), (7, 5)]라면, 네 번째 점의 좌표는 (7, 7)이 됩니다.

 

 

다른 풀이

위의 list.count() 방법은 주어진 점의 개수가 많아지면 비효율적일 수 있습니다. 이러한 경우에는 Python의 collections.Counter와 같은 더 효율적인 방법을 고려해볼 수 있습니다.

from collections import Counter

arr = [
    list(map(int, input().split()))
    for _ in range(3)
]


x_num = [x for x, _ in arr]
y_num = [y for _, y in arr]

x_cnt = Counter(x_num)
y_cnt = Counter(y_num)

x = next(x for x, count in x_cnt.items() if count == 1)
y = next(y for y, count in y_cnt.items() if count == 1)

print(x, y)

 "collections.Counter"는 Python의 내장 데이터 타입인 딕셔너리를 확장한 것입니다. 딕셔너리와 마찬가지로, Counter는 키와 값의 쌍을 저장합니다.

 Counter는 리스트나 문자열과 같은 반복 가능한 객체를 입력으로 받아, 각 요소의 등장 횟수를 세어 딕셔너리 형태로 저장합니다. 

 

예를 들어, 다음과 같이 리스트의 각 요소의 등장 횟수를 세는 Counter를 만들 수 있습니다:

from collections import Counter

nums = [1, 2, 2, 3, 3, 3]
counter = Counter(nums)

print(counter)  # 출력: Counter({3: 3, 2: 2, 1: 1})

여기서 counter는 {3: 3, 2: 2, 1: 1}이라는 딕셔너리와 비슷한 형태를 가집니다. 각 키는 리스트의 요소를, 각 값은 해당 요소의 등장 횟수를 나타냅니다. 따라서 Counter를 사용하면, 각 요소의 등장 횟수를 쉽게 세고, 이를 바탕으로 다양한 연산을 수행할 수 있습니다.

 

---

x = next(x for x, count in x_cnt.items() if count == 1)
y = next(y for y, count in y_cnt.items() if count == 1)

 

두 코드를 살펴보겠습니다.

먼저, x_cnt.items()와 y_cnt.items()는 Counter 객체에서 각 요소와 그 등장 횟수를 튜플로 만들어서 반환합니다.

예를 들어, x_cnt가 {5: 2, 7: 1}이라면, x_cnt.items()는 {(5, 2), (7, 1)}을 반환합니다.

다음으로, for x, count in x_cnt.items() 구문은 이 튜플들을 하나씩 꺼내서 x와 count에 할당합니다. 

예를 들어, 첫 번째 반복에서는 x는 5가 되고, count는 2가 됩니다.

if count == 1 구문은 count가 1인 경우, 즉 x좌표가 한 번만 등장하는 경우에만 x를 생성하는 조건입니다. 위의 예에서는 x가 7인 경우에만 해당합니다.

따라서, x for x, count in x_cnt.items() if count == 1는 한 번만 등장하는 x를 생성하는 generator 표현식입니다.

마지막으로, next() 함수는 이 generator에서 첫 번째 요소를 가져옵니다. 여기서는 한 번만 등장하는 첫 번째 x를 반환합니다.

y에 대해서도 동일한 과정을 거칩니다. 한 번만 등장하는 y를 찾기 위해 y_cnt에서 각 y와 그 등장 횟수를 꺼내서, count가 1인 y를 생성하고, 이 중 첫 번째 y를 가져옵니다.

 

generator 표현식이란?

제너레이터 표현식은 리스트 컴프리헨션과 비슷한 문법을 가지고 있지만, 대괄호 대신 괄호를 사용합니다. 제너레이터 표현식은 모든 데이터를 메모리에 미리 생성하는 대신, 데이터가 필요한 시점에만 생성합니다. 이 특성 때문에 큰 데이터셋을 다룰 때 메모리 사용량을 줄이고 프로그램의 효율성을 높일 수 있습니다.

예를 들어, 다음은 리스트 컴프리헨션과 제너레이터 표현식의 차이를 보여주는 코드입니다:

# 리스트 컴프리핸션
squares_list = [x**2 for x in range(10)]
print(squares_list)
print(type(squares_list))

# 제네레이터 표현식
squares_gen = (x**2 for x in range(10))
print(squares_gen)
print(type(squares_gen))

위 코드를 실행하면, squares_list는 10개의 제곱수를 모두 계산하여 리스트로 저장합니다. 그에 반해 squares_gen는 제너레이터 객체를 반환하며, 이 객체는 아직 어떤 계산도 수행하지 않았습니다.

제너레이터 객체에서 값을 꺼내기 위해선 next() 함수를 사용하거나, for 루프를 통해 순회할 수 있습니다. 이 때, 값은 필요한 시점에만 계산되고 메모리에 저장되지 않습니다. 모든 값이 소진되면 StopIteration 예외가 발생합니다.

print(next(squares_gen))  # 0
print(next(squares_gen))  # 1
print(next(squares_gen))  # 4
# 계속하면, 다음 값은 필요한 시점에 계산됩니다.

마치며

이 문제는 간단한 아이디어를 바탕으로 리스트에서 특정 조건을 만족하는 요소를 찾는 기술을 연습하는 데에 도움이 됩니다. 특히, list.count() 메소드를 이용하여 각 요소의 등장 횟수를 쉽게 세고, 이를 바탕으로 원하는 요소를 찾는 방법에 대해 알아보았습니다.!