[백준 / python] #13423: Three Dots

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

13423번: Three Dots

RESULT

"""pypy3"""
from collections import defaultdict
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    li = sorted(list(map(int, input().split())))
    ans = 0
    dd = defaultdict(int)
    for i in li: dd[i] = 1

    for i in range(n-1):
        for j in range(i+1, n):
            first = li[i]
            second = li[j]
            third = 2*li[j] - li[i]
            if dd[third] == 1: ans += 1
    print(ans)

PROGRESS

# 해석

최대 1,000개의 점이 할당되고, 이 점 중에서 3개의 점을 고른다.

3개의 점 중에서 가운데의 점을 기준으로 나머지 각 점까지의 거리가 동일한 경우의 개수를 구하라.

 

# 첫 번째 풀이

1. Combination을 활용하여 주어진 리스트로부터 점 3개를 선택한다.
2. 뽑은 점을 오름차순으로 정렬한 뒤,
3. 루프 안에서 각 점의 거리를 인덱싱으로 비교하여 같은 경우의 개수를 카운트한다.

from itertools import combinations as cb

for _ in range(int(input())*2):
    n = int(input()) # num of points
    li = list(map(int, input().split()))
    ans = 0
    
    for _li in cb(li, 3): # Combination을 활용하여 주어진 리스트로부터 점 3개를 선택한다.
        _li = sorted(list(_li)) # 뽑은 점을 오름차순으로 정렬한 뒤,
        if (_li[1] - _li[0]) == (_li[2] - _li[1]): ans += 1 # 거리를 비교하여 같은 경우의 개수를 카운트한다.
    print(ans)

 

결과: 시간 초과

 

이유: 시간복잡도를 계산하면, 최대 1,000개의 점 중에서 3개를 뽑는 과정에서 이미 컴퓨터는 1000C3 즉, 약 1,000의 세제곱 만큼의 연산을 수행해야 하므로 실행시간 1초를 넘기게 된다. 따라서 조합으로는 해당 문제를 풀 수 없다.

 

개선: 위 로직은 for문이 하나인 것으로 보이지만 cb함수 내부 로직상 시간을 초과하게 되므로 조합을 활용하는 로직을 버리고, for문 두개까지 중첩 가능한 걸 이용하여 동일 효과를 내는 로직을 구성하면 된다.

 

# 두 번째 풀이

1. 루프문 두 개를 중첩하여 완전탐색을 통해 점 두 개를 고른다.
2. 두 개의 간격만큼 가상의 세번째 점의 x값을 변수에 담고,
3. 가상의 세번째 점의 x값이 주어진 점 리스트에 있으면 카운트한다. 

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    li = sorted(list(map(int, input().split())))
    ans = 0
    li.sort()

    for i in range(n-1):
        for j in range(i+1, n): 루프문 두 개를 중첩하여 완전탐색을 통해 점 두 개를 고른다.
            first = li[i]
            second = li[j]
            third = 2*second - first 두 개의 간격만큼 가상의 세번째 점의 x값을 변수에 담고,
            if third in li[j+1:]: ans += 1 가상의 세번째 점의 x값이 주어진 점 리스트에 있으면 카운트한다. 
    print(ans)

 

결과: 시간 초과

 

이유: 알아보니 `in 예약어`가 연산하는 자료구조에 따라 시간복잡도가 달라지는 것을 알 수 있었다.

• list, tuple : 데이터를 하나하나 순회하므로 O(n)
• set, dictionary : hash 방식을 통해 데이터를 저장하기에 O(1)이 일반적이나, 해시 충돌이 많이 일어날 경우 O(n)으로 발생할 순 있다.

개선: in 연산자를 통해 검사하는 자료구조를 list가 아닌 dictionary를 선택한다. 여기서 편하게 defaultdict를 이용하고자 한다.

 

# 세 번째 풀이

1.  주어진 점을 딕셔너리 key에 할당하여, 그 key에 해당하는 value를 1을 준다.
2. 루프문 두 개를 중첩하여 완전탐색을 통해 점 두 개를 고른다.
3. 두 개의 간격만큼 가상의 세번째 점의 x값을 변수에 담고,
4. 가상의 세번째 점의 x값이 주어진 점 딕셔너리에 있으면 카운트한다.

from collections import defaultdict
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    li = sorted(list(map(int, input().split())))
    ans = 0
    dd = defaultdict(int)
    for i in li: dd[i] = 1

    for i in range(n-1):
        for j in range(i+1, n):
            first = li[i]
            second = li[j]
            third = 2*li[j] - li[i]
            if dd[third] == 1: ans += 1
    print(ans)

결과: 성공