[백준] 5588. 별자리 찾기 - Python3

문제 설명

찾고자 하는 별자리의 별들의 좌표(1)와, 사진에 찍힌 별들의 좌표(2)가 주어졌을 때, (1)에서 얼만큼 이동해야 (2)에서 나타난 별자리 위치가 되는지를 구하는 문제

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

5588번: 별자리 찾기

• 알고리즘 분류 - 자료구조, 브루트포스 알고리즘, 해시를 사용한 집합과 맵
• 난이도 - 골드4

---

관련 개념

Collections().most_common()

https://infinitt.tistory.com/183

파이썬(Python) Collections 모듈 - counter , most_common

---

접근 방법

1. 리스트

가장 단순하게 접근할 수 있는 방법이 두 가지 있다.

 

1) 별자리를 한 칸 씩 일일이 이동해보며 사진 속 위치와 비교해 보는 방법 => X

x와 y의 범위가 둘 다 1000000이기 때문에 시간 초과가 날 것이다.

 

2) 별자리의 별들 중 하나를 원점에 고정시키고(1), 사진 속 별들을 원점으로 고정시켜보며 (1)과 비교하는 방법 => O

m과 n의 범위가 각각 200이하, 1000이하기 때문에 브루트포스가 가능하다.

 

원점 고정 후 처음엔 Collection으로 차집합을 이용하려고 했는데, 이차원리스트라 그런지 오류가 나서 브루트포스를 직접 구현하여 해결했다.

 

+) 원점으로 고정시킬 별을 정하기 위해, 별자리 좌표와 사진 좌표를 정렬하여 가장 왼쪽 상단에 있는 점 순서로 고정하면 실행 속도가 훨씬 빨라진다.

 

2. Collections().most_common()

다른 분 답안 참고) https://www.acmicpc.net/source/53961042

로그인

모든 사진 좌표와 별자리 좌표에 대해 (사진 좌표 - 별자리 좌표)를 했을 때, 가장 많이 나오는 값이 평행이동 했다는 근거 및 평행이동 한 정도를 의미하므로 정답이 된다.

---

답안 코드

1. 리스트

메모리: 34184 KB , 시간: 1408 ms, 코드 길이: 1036 B

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

m = int(input())
constellation = []
for i in range(m):
    constellation.append(list(map(int,input().split())))
constellation.sort(key=lambda x:(x[0],x[1]))

# 별자리의 첫 별을 원점으로 만들기
origin = [constellation[0][0], constellation[0][1]]
for star in constellation:
    star[0] -= origin[0]
    star[1] -= origin[1]

n = int(input())
stars = []
for i in range(n):
    stars.append(list(map(int,input().split())))
stars.sort(key=lambda x:(x[0],x[1]))

# 사진 속 각 별을 원점으로 만들어보기
for std in stars:
    copy = [std[0],std[1]]
    for star in stars:
        star[0] -= copy[0]
        star[1] -= copy[1]
    
    intersection = []
    for star in constellation:
        if star in stars:
            intersection.append(star)
            
    if intersection == constellation:
        print(copy[0]-origin[0], copy[1]-origin[1])
        break
    
    for star in stars:
        star[0] += copy[0]
        star[1] += copy[1]

 

2. Collections().most_common()

메모리: 82728 KB , 시간: 196 ms, 코드 길이: 349 B

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

m = int(input())
data = [list(map(int, input().split())) for i in range(m)]
n = int(input())
star = [list(map(int, input().split())) for i in range(n)]
print(*Counter([(star[j][0] - data[i][0], star[j][1] - data[i][1]) for i in range(m) for j in range(n)]).most_common()[0][0])