[Swift Algorithm] 멀티탭 스케줄링 BOJ #1700

문제 설명

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

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

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

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

 

입력

첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다.

 

출력

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

 

입출력 예제

입력

2 7
2 3 2 3 1 2 7

출력

2

 

내 문제 풀이

import Foundation

let info = readLine()!.split(separator: " ").map({Int(String($0))!})
var use = readLine()!.split(separator: " ").map({Int(String($0))!}) // 사용 순서 대기열
var multitap = Array(repeating: 0, count: info[0]) // 구 개수만큼 0으로 채운 멀티탭 배열
var answer = 0

use.reverse()

while use.count > 0 {
    // 멀티탭에 빈 공간이 있을 경우
    if multitap.contains(0) {
        if multitap.contains(use.last!) { use.removeLast() }
        else { multitap[multitap.firstIndex(of: 0)!] = use.removeLast() }
    }
    // 멀티탭에 빈 공간 없을 경우
    else {
        if multitap.contains(use.last!) { use.removeLast() }
        else {
            var min = use.count
            var check = 0
            for j in multitap {
                if !use.contains(j) { check = j; break }
                else if use.lastIndex(of: j)! < min { min = use.lastIndex(of: j)! }
            }
            if min == use.count { multitap[0] = use.removeLast() }
            else if check != 0 { multitap[multitap.firstIndex(of: check)!] = use.removeLast() }
            else { multitap[multitap.firstIndex(of: use[min])!] = use.removeLast() }
            answer += 1
        }
    }
}

print(answer)

👉 이 문제는 크게 3가지 고려할 점이 있다.

1) 멀티탭에 빈 공간이 있을 경우

2) 멀티탭에 빈 공간이 없을 경우

3) 순서가 다가온 물건이 현재 멀티탭에 꽂혀있는지

+ 예외가 아주 많은 문제라 제출 전에 꼭 다른 예제를 많이 만들어서 테스트해보시길 바랍니당,,

• 우선 연산을 진행하기 전, 입력받은 순서 배열 use를 반대로 뒤집어주었다.
  연산을 진행하면서 순서가 지난 물건은 use에서 삭제해줄 것인데, 배열의 앞에서부터 삭제해나간다면
  계속 배열을 한 칸씩 당겨야하는 비효율성을 가지게 되므로 reverse하여 뒤에서부터 순서를 시작하게했다.
• use 배열이 모두 삭제될 때까지 while문을 반복하게 했는데, 멀티탭에 빈 공간이 있을 경우와 없을 경우로 나눴다.
• 먼저 멀티탭에 빈 공간이 있을 경우는 multitap 배열이 0을 포함하는지로 체크해주었고,
  순서가 다가온 물건이 현재 멀티탭 안에 존재하는지 확인했다.
  존재할 경우에는 다시 코드를 뺄 이유가 없기 때문에 그냥 use배열에서 삭제만 해주었고,
  존재하지 않을 경우에는 멀티탭의 빈 자리중 첫 번째 자리에 해당 물건을 넣어주었다.
  (순서를 뒤집어 주었으므로 코드 안에서 순서가 다가온 물건은 계속 use.last!로 표현할 예정이다.)
• 멀티탭에 빈 공간이 없을 경우에는 빈 공간이 있을 경우보다 조금 더 고려할 사항이 있는데,
  1) 멀티탭에 순서가 다가온 물건이 이미 꽂혀있는가?
  2) 순서가 다가온 물건이 멀티탭에 꽂혀있지 않는가?
  2-1) 멀티탭에 꽂혀있는 물건 전부가 use에 존재하지 않는가?
  2-2) 멀티탭에 꽂혀있는 물건들 중 use에 존재하지 않는 물건이 있는가?
  2-3) 멀티탭에 꽂혀있는 물건들 전부가 use에 존재하는가?
• 1) 멀티탭에 순서가 다가온 물건이 이미 꽂혀있다면 그냥 use 배열에서 해당 물건 삭제만 진행했다.
• 2) 순서가 다가온 물건이 멀티탭에 꽂혀있지 않다면 for문을 사용하여 멀티탭 배열을 검사했다.
  멀티탭 배열에 꽂힌 물건들의 use에서의 위치를 확인, 그 중 순서가 가장 늦는 물건의 위치를 min에 저장했다.
  반복하며 min을 갱신하던 중, 멀티탭에 꽂혀있는 물건들 중 use 배열에 존재하지 않는 물건을 발견했다면
  multitap 배열에서 어떤 물건을 뺄지 고민할 필요도 없이 해당 물건을 멀티탭에서 빼면 되기 때문에
  바로 for문을 break해주었다. 그리고 for문 아래에 위에서 말한 2-1), 2-2), 2-3)번 예외를 고려했다.
• 2-1) min이 처음 그대로라면 멀티탭에 꽂힌 물건들 모두가 use 배열에 존재하지 않는다는 의미이므로
  아무 물건이나 빼도 상관없다. 따라서 그냥 multitap의 첫 번째 자리에 순서가 다가온 물건을 넣어주었다.
• 2-2) check가 0이 아니라는 것은 어떠한 물건이 use에 존재하지 않음을 확인했다는 뜻이므로
  multitap에서 check에 저장된 물건을 찾아 그 위치에 있는 물건을 빼주고 순서가 온 물건을 꽂아주었다.
• 2-3) 2-1번과 2-3번의 조건에 걸리지 않았다면, 멀티탭의 모든 물건이 use 배열에 존재한다는 뜻이므로
  가장 순서가 늦는 물건(min)의 multitap에서의 위치를 찾아 빼고 순서가 다가온 물건을 넣어주었다.

 

💡 피드백

• 처음엔 use 배열에, 멀티탭의 물건들의 위치를 전부 찾아주고 검사하는것이 너무 비효율적일까봐
  어떻게든 효율적으로 풀어보기 위해 애썼는데,, 그렇게 푸니까 예외가 끝도 없이 나와서ㅜㅜ
  그냥 계속 검사해주는 방법을 택했다.
• 문제 푸는데 굉장히 오래걸렸는데, 그리디 문제는 효율보다도
  모든 예외를 포함할 수 있는 정확한 코드를 짜는 방안을 생각해 내는 것이 더 중요한 것 같다.

 

---

 

문제

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