[백준: Python] 5840 - Breed Proximity

[문제]

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

문제의 등급보다는 다소 생각을 해야 풀 수 있는 문제입니다. 문제를 요약하자면 ID가 부여된 소들 중, 동일한 ID를 가진 소들의 거리가 K 이하인 그룹 중에서 가장 큰 ID를 가진 그룹을 찾는 문제입니다.

 

단순하게 생각하면 n^2으로 문제를 풀어낼 수 있을 거 같지만, 소들의 수인 N의 최대는 50,000이고 시간 제한은 1초이므로 그렇게 풀어낼 수는 없습니다.

 

그렇기 때문에 문제를 선형 시간으로 풀어내는 방법으로 접근해야 합니다.

---

[초기화]

    def __init__(self):
        self.n, self.k = map(int, input().split())
        self.cows = [int(input()) for _ in range(self.n)]

---

[풀이]

    def solve(self):
        last_seen = {}
        answer = -1

        for i in range(self.n):
            breed_id = self.cows[i]  # 현재 소의 id
            if breed_id in last_seen and i - last_seen[breed_id] <= self.k:  # 현재 id와 같은 소를 이전에 봤다면
                answer = max(answer, breed_id)  # 현재 소와 마지막으로 본 소의 거리를 확인하고 id가 큰 소로 갱신
            last_seen[breed_id] = i  # 현재 소의 위치

        print(answer)

문제를 선형시간으로 풀어내기 위해 해시를 사용했습니다.

 

1. 소들의 ID를 순차적으로 가져옵니다.
2. 해당 ID를 가진 소를 이전에도 봤다면, 현재 소와 마지막으로 본 소와의 거리가 K 이하인지 확인하여 답을 갱신합니다.
   • 코드에서 i는 소의 위치를 나타내므로, 현재 소의 위치인 i와 마지막으로 본 소의 위치 i를 빼면 거리를 알 수 있음
3. 해시에는 항상 마지막으로 본 소의 위치를 저장합니다.

---

[전체 코드]

class Main:
    def __init__(self):
        self.n, self.k = map(int, input().split())
        self.cows = [int(input()) for _ in range(self.n)]

    def solve(self):
        last_seen = {}
        answer = -1

        for i in range(self.n):
            breed_id = self.cows[i]  # 현재 소의 id
            if breed_id in last_seen and i - last_seen[breed_id] <= self.k:  # 현재 id와 같은 소를 이전에 봤다면
                answer = max(answer, breed_id)  # 현재 소와 마지막으로 본 소의 거리를 확인하고 id가 큰 소로 갱신
            last_seen[breed_id] = i  # 현재 소의 위치

        print(answer)


problem = Main()
problem.solve()

---