문제:

평면상에 n개의 점이 있다. 이 점들 중에 서로 다른 두 점을 선택하면 하나의 직선이 만들어진다. 이와 같이 직선을 만들었을 때, x축 또는 y축에 평행한 직선이 몇 개나 되는지 알아내는 프로그램을 작성하시오.

입력:

첫째 줄에 n(1<=n<=100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 int 범위에서 주어진다. 만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다.

출력:

첫째 줄에 답을 출력한다.

풀이방법:

 x좌표가 일치하는 두 점들이나 y좌표가 일치하는 두 점들이 축과 평행을 이루기 때문에 정렬을 통해서 쉽게 찾을 수 있을 것 같았다. 하지만 문제 이해를 잘못해서 처음에 조금 헤매었고, 질문에 있는 글을 보면서 겨우 이해했다.

 '만약 입력에 서로 같은 두 점이 주어지면, 그 두점을 이용하여 직선을 만들 수 있다.' 라는 문구때문에 많이 헷갈렸다. 처음에는 (0,0)_1 (0,0)_2 (0,10) 이렇게 있으면 (0,0)_1, (0,0)_2을 (0,0)_1, (0,10)을 (0,0)_2, (0,10)을 연결할 수 있어서 3개라고 생각했지만 아니였다.

 문제에서 원하는 것은 위와 같은 경우에는 (0,0)_1 (0,0)_2의 두 점을 통해 x=0, y=0이라는 두 직선을 만들 수 있었고, (0,0)_1, (0,10)을 (0,0)_2, (0,10) 이것들은 x=0인 직선에 포함되는 것이므로 카운트를 하지 않는다는 것이였다. 그래서 답은 2가 되는 것이였다.

 그래서 x축과 평행하게 만들 수 있는 직선의 숫자값, y축과 평행하게 만들 수 있는 직선의 숫자값을 각각 담는 배열을 만들어서 그 길이를 더하도록 했다.

하지만 매우 비효율적으로 구성했기 때문에 시간초과가 발생하였고 PyPy3로 통과할 수 있었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
points=[]
answer=0
n=int(input())
for _ in range(n):
    point=tuple(map(int,input().split()))
    points.append(point)
    
points=sorted(points)
xs=[]
for i in range(len(points)):
    for j in range(i+1,len(points)):
        if points[i][0]==points[j][0]:
            if not points[i][0in xs:
                xs.append(points[i][0])
                answer+=1
            break
        else:
            break
        
ys=[]
points=sorted(points,key=lambda x:x[1])
for i in range(len(points)):
    for j in range(i+1,len(points)):
        if points[i][1]==points[j][1]:
            if not points[i][1in ys:
                ys.append(points[i][1])
                answer+=1
            break
        else:
            break
print(answer)
cs

문제링크:

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

 

2358번: 평행선

첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 int 범위에서 주어진다. 만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다.

www.acmicpc.net

 

'Algorithm > Python' 카테고리의 다른 글

[Programmers]2020 Kakao.괄호 변환  (0) 2019.11.15
[Programmers]2020 Kakao. 문자열 압축  (0) 2019.11.14
[BOJ]GIT- 정리  (0) 2019.11.12
[BOJ]1937. 욕심쟁이 판다  (0) 2019.11.11
[BOJ]6359. 만취한 상범  (0) 2019.11.09

+ Recent posts