https://www.acmicpc.net/problem/1700
시간 2초, 메모리 128MB
input :
- N K(1 ≤ N, K ≤ 100)
- 전기용품의 이름이 K 이하의 자연수로 사용 순서대로
output :
- 하나씩 플러그를 빼는 최소의 횟수를 출력하시오.
플러그를 빼는 경우를 최소로 만들어야 한다.
예제를 보았을 때 우선적으로 보이는 조건들을 생각해보자.
- 플러그를 아직 꽂을 수 있을 때.
- 플러그 중에 현재 물건이 꽂혀 있을 때
위의 두 가지 경우에는 무시하고 지나가도 상관이 없다.
for idx, item in enumerate(data):
if item in temp:
continue
if len(temp) < n:
temp.append(item)
continue그렇다면 새로운 물품이 들어올 때 어떻게 해야하는가가 중요한데...
- 첫 번째로 했던 생각 : 우선순위 큐를 사용해서 총 사용횟수를 저장하게 하는 방법은 어떠한가?
-> 이 방법의 경우
2 15
3 2 1 2 1 2 1 2 1 3 3 3 3 3 3
아래의 예제를 제대로 확인 할 수 없다.
정답은 2인데.
3, 2 가 꽂혀 있던 플러그를 3을 빼고 1을 꽂아 계속 쓰다가 다시 3을 꽂는 2번의 행동을 하도록 할 수 있는 것이다.
위의 경우를 통해 우리는 뽑을 때 한 가지 해야 하는 행동을 알 수 있다.
바로 새로운 물품이 들어왔을 때: 현재 플러그 꽂혀 있는 것들이 data에서 현재의 idx 이후로 슬라이싱 한 배열에서. 어디에 존재하는지를 확인해야 한다.
그리고 가장 나중에 다시 꽂는 플러그의 경우 얘가 나가는 것이 다른 물품들을 중복적으로 사용하기에 이득이기 때문에 가장 나중에 오는 놈을 뽑자.
그래서 이를 나타내기 위해
-
나중에 나오는 idx들을 모두 모아서 저장을 하게 하려 했는데 이 경우엔 너무 많은 조건들이 생기고 코드를 구현하는 본인이 헷갈리기 쉬워 포기했다.
그리고 이 방법을 쓸 때는 데이터가 아주 많은 경우에 써야 한다.
그러나, 현재의 문제는 데이터 풀이 아주 작기 때문에 plug 배열을 계속 반복해도 감당이 가능할 정도의 크기이다. -
결국 이용하는 방법은 배열.index(temp[i])를 이용하는 것이다.
plug배열을 temp로 만들었고 이때에 찾은 index를 모두 모아서 가장 큰 놈을 찾는다.
그리고 이 놈을 temp에서 pop해주고 새로운 물품을 추가하자.
다시 나타나지 않을 때에는 101을 넣게 해서 가장 크게 만들어 버린다. 다시 등장하지 않는 놈을 뽑는게 더 효율적이기에 이렇게 한다.
idx_list = []
for i in range(len(temp)):
try:
index = data[idx:].index(temp[i])
except:
index = 101
idx_list.append((index, temp[i]))
idx_list.sort(key=lambda x:-x[0])
index = temp.index(idx_list[0][1])
temp.pop(index)
temp.append(item)
ans += 1역시 데이터를 잘 눈 여겨 봐야 할거 같다.
import sys
n, k = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
temp = []
ans = 0
for idx, item in enumerate(data):
if item in temp:
continue
if len(temp) < n:
temp.append(item)
continue
idx_list = []
for i in range(len(temp)):
try:
index = data[idx:].index(temp[i])
except:
index = 101
idx_list.append((index, temp[i]))
idx_list.sort(key=lambda x:-x[0])
index = temp.index(idx_list[0][1])
temp.pop(index)
temp.append(item)
ans += 1
print(ans)
