대부분의 그리디 문제와 같이, 그리디 문제임을 파악하는 것과
구현방법이 문제가 되는 문제입니다.
1. 알고리즘 설계
이 문제에서 가장 중요한 부분은, 플러그의 교체 시기입니다.
플러그의 교체는 언제 일어날까요?
당연히 멀티탭에 남은 자리가 없는 상태여야 합니다.
그렇다면 최대한 플러그 빼는 횟수를 줄인다는 규칙을 지키려면, 무엇을 빼야 할까요?
가장 먼저, 미래에 더 이상 쓰지 않을 플러그입니다. 이건 당연하죠?
그런데 쓰지 않을 플러그가 없다면?? 가장 나중에 쓸 플러그를 빼야 합니다.
최적해임을 어떻게 판단할 수 있을까요?
제가 생각한 과정은 다음과 같습니다.
- 어떤 플러그를 뽑는 행위가 문제해결에 방해가 된다면 이유는 뭘까?
- 그 플러그를 쓰는 상황이 빠르게 돌아오면 손해가 될수 있다.
- 위 상황은 알고리즘 설계상 발생할 수 없다.
- 뽑고 그 다음부터는 어떻게 진행될까?
- 같은 동작을 반복한다면 문제가 생길까?
까지 고려한 후에 그리디를 적용할 수 있겠다고 생각하였고 구현을 시작했습니다.
2. 구현과정
먼저 자료의 크기인 멀티탭 구멍 개수, 사용계획의 수가 모두 100이하로 작고 입력이 순서대로 들어오므로 정렬은 필요없으니, 그냥 리스트에 순서대로 넣겠습니다.
멀티탭을 나타낼 리스트를 만들어서 리스트에 요소를 넣으면 꽂는 것, 제거하는 것을 빼는 것으로 하는 게 좋을 것 같습니다. 결과를 저장할 변수도 하나 있어야 합니다.
그러면 변수는 아래와 같이 사용해야 되겠네요.
scd = list(map(int,input().split())) #입력된 사용계획
mulTap = [] #멀티탭
result = 0 #뽑은 횟수 = 결과일단 여러번 실행할 일은 없으니 함수화하지 않고, for문으로 짜보겠습니다.
증감자 i는 scd의 인덱스로 하는 것이 좋겠네요.
인덱스 번호가 계속 필요할 것 같으니 for-each 문은 쓰지 않는 게 좋을 것 같습니다.
반복해야 할 조건문들을 생각해볼까요?
1번. 이미 현재 기기가 꽂혀있다면 -> continue
2번. 멀티탭에 빈자리가 있다면 -> 꽂고, continue
코드로는 아래같이 구현할 수 있겠네요.
if scd[i] in mulTap : continue
#빈자리가 있다면
if len(mulTap) < N :
mulTap.append(scd[i])
continue이제 가장 중요한 부분입니다. 사용하지 않을 or 가장 늦게 사용할 기기를 찾는 과정이죠.
그렇다면 멀티탭에 꽂혀있는 플러그들을 모두 살펴봐야 합니다. 또 다른 반복문이 필요하겠네요.
반복문안에서 뽑을 플러그가 결정되면 tmp라는 변수에 저장해놓겠습니다.
멀티탭에 있는 요소들에 대해서 2가지를 확인해봐야겠죠.
1. 나중에 사용하지 않는 플러그인가 -> tmp에 저장하고, break
2. 사용한다면 몇번째인가?
- 각 요소가 scd의 몇번 인덱스에서 다시 등장하는 지 저장할 변수 latest 선언, 초기값 : 0
- 각 요소들이 다시 등장하는 인덱스 번호를 latest와 비교, 더 클때마다 tmp와 lastest 갱신
코드로 보면
#꽂혀있는 물건들중에
for el in mulTap:
#나중에 사용하지 않을 물건이 있다면
if el not in scd[i:]:
#뽑을대상으로 지정, for문 탈출
tmp = el; break
#아래 코드는 가장 뒤에 사용할 물건 찾는 과정
#lastest보다 더 뒤에 나오는 물건이라면,
#슬라이싱으로 i부터 K 범위에서 탐색
elif scd[i:].index(el) > latest:
#가장 뒤에 사용할 물건의 인덱스 최신화
latest = scd[i:].index(el)
#뽑을 대상으로 지정
tmp = el위 과정까지 끝나면 tmp에는 뽑아야 할 플러그의 이름이 저장되어있습니다.
멀티탭에서 이 플러그를 현재 사용해야 할 플러그로 갱신해주면 하나의 플러그를 뽑고 꽂은 것과 같고, 결과 횟수를 1 증가시켜줘야합니다.
전체코드
import sys
input = sys.stdin.readline
N, K = map(int,input().split())
#물건들 스케줄
scd = list(map(int,input().split()))
mulTap = [] #멀티탭
result = 0 #뽑은 횟수 = 결과
for i in range(K):
#이미 꽂혀있다면
if scd[i] in mulTap : continue
#빈자리가 있다면
if len(mulTap) < N :
mulTap.append(scd[i])
continue
#가장 뒤에 사용할 물건의 인덱스
latest = 0
#꽂혀있는 물건들중에
for el in mulTap:
#나중에 사용하지 않을 물건이 있다면
if el not in scd[i:]:
#뽑을대상으로 지정, for문 탈출
tmp = el; break
#가장 뒤에 사용할 물건 찾는 과정
elif scd[i:].index(el) > latest:
#가장 뒤에 사용할 물건의 인덱스 최신화
latest = scd[i:].index(el)
#뽑을 대상으로 지정
tmp = el
#뽑기로 결정된 물건의 자리를 현재 꽂아야할 물건으로 대체
mulTap[mulTap.index(tmp)] = scd[i]
#결과 횟수 + 1
result += 1
print(result)끝으로
질문이나 피드백은 언제든지 환영입니다.
