문제:
평면상에 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][0] in 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][1] in 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 |