[백준 1700 파이썬] 멀티탭 스케줄링

 

백준 1700 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

문제

- 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털카메라 충전기
5. 키보드
6. 헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

입력

첫줄에는 멀티탭 구멍의 개수 n과 전기용품의 총 사용 횟수 k가 정수로 주어진다

두 번째 줄에는 전기용품의 이름이 k 이하의 자연수로 사용 순서가 주어진다

공백 문자로 구분된다 

출력

하나씩 플로그를 빼는 최소의 횟수를 출력하시오

풀이

예제 입력

2 7
2 3 2 3 1 2 7

멀티탭 구멍의수는 2개이고 전자제품 총 사용 횟수는 7회 이면 

사용순서는 2 3 2 3 1 2 7 이다

첫 번째 멀티탭에 2 3을 넣을 수 있다 (현재 멀티탭 2 3)

그 후 2가 나오므로 이미 꼽혀있기에 패스하면 그다음수인 3 또한 있으므로 패스한다 (현재 멀티탭 2 3)

그다음 1이 나오며 뒤에 3이 없기에 3을 빼고 1을 집어넣는다 (현재 멀티탭 2 1)

그다음 수는 2 임으로 2는 꼽혀 있기에 패스 한다 (현재 멀티탭 2 1)

그 다음 수로는 7로 1과 2 중 아무거나 뽑아도 되기에  (현재 멀티탭 7 1)

플로그를 빼는 최소의 횟수는 2이다 

 

고려해야 할 거

1. 초기 멀티탭이 비어있을 때 멀티탭이 가득 찰 때까지 채운다

2. 이미 꼽혀 있는 수가 나올 경우 넘어간다

3. 이미 꼽혀있지 않은 수가 나올 경우 현재 꼽혀 있는 수중 가장 나중에 나올 수를 빼고 그 자리에 넣는다

 

 

코드

from collections import deque

n,k=map(int,input().split())
data=list(map(int,input().split()))
data=deque(data)
multi=[]
count=0

while data:

    if data[0] in multi: #현재 꼽혀있는거 있으면 통과
        data.popleft()
        continue
    if len(multi)<n: #자리가 남아있다면 집어넣기
        multi.append(data.popleft())
    else:
        cnt=0
        ix=0 #뽑을 위치
        temp=101 # 뽑는값을 저장할 변수
        for j in multi:
            if j in data:
                cnt=data.index(j) # 현재 시점에서 꼽혀있는 수가 뒤에서 처음 등자하는 시점
                if ix<cnt:
                    ix=cnt
                    temp=j #뒤에서 등장하는것 부터 뽑아버리기위한 저장값

            else:
                temp=j #뒤에 등장하지 않기에 등장하지 않는 값을 뽑아주기 위해
                break
        for g in range(n):

            if multi[g]==temp:
                multi[g]=data.popleft()
                count+=1
                break
print(count)

 

 

deque를 이용하여 멀티탭에 넣는 값을 빼주면서 while 문을 돌렸다 

temp값이 101인이 이유는 조건에 최대 k값이 100으로 주어지기에 그것보다 큰 수를 넣었다

 

다른 사람들 꺼 보면 제 거보다 더 간결하게 적은 게 많은 것 같다.. 일단 비슷하긴 하고 처음에 풀 때 꼽혀 있는 수가 2개 이상 다시 꼽아야 할 때 가장 늦게 등장하는 수를 빼버려 하는 걸 문제를 보고 바로 생각하지 못하여 힌트틀 보면서 풀었다 

가장 늦게 등장하는 수를 확인하는 방법이 for 문을 멀티탭 원소로 돌린다 돌리는 이유는 멀티탭에 꼽혀있는 수 다시 꼽아야 하는지 아닌지 확이하면 아니라면 아닌 수를 빼서 다음 순서를 넣는다

만약 다시 꼽아야 한다면 그 다시 꼽아야 하는 수중 가장 늦게 등장하는 수를 가장 높은 우선순위로 잡아

그 수를 빼서 다음수를 넣어야 한다 

temp에 빼야 할 수가 저장되어  그 수와 같을 경우 그 수 자리에 다음수를 넣고 count 값을 증가시켜 

플러그 빼는 최소의 횟수를 알 수 있다

 

결과