[Baekjoon] 1021 회전하는 큐

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

문제 요약 및 풀이

2,3번 연산을 최소로 이용해서 숫자를 뽑아보아라는 문제입니다. 

 

간단히 생각해보면 큐 자료구조를 만드는데 앞 뒤로 뺴고 집어넣을 수 있게 변형하면 되는 문제입니다.

그래서 바로 자료구조를 만들어주어 주었습니다ㅏ.

struct SpinningQueue {
  var list = [Int]()
  
  var count: Int { self.list.count }
  
  func isEmpty() -> Bool {
    return list.isEmpty
  }
  
  func firstItem() -> Int {
    return list[0]
  }
  
  func lastItem() -> Int {
    return list.last!
  }
  
  func getLocation(of number: Int) -> Int? {
    return list.firstIndex(of: number)
  }
  
  mutating func popFirst() -> Int? {
    if isEmpty() {
      return nil
    } else {
      let first = list[0]
      self.list.remove(at: 0)
      return first
    }
  }
  
  mutating func popLast() -> Int? {
    return self.list.popLast()
  }
  
  mutating func secondCommand() {
    if let first = popFirst() {
      list.append(first)
    }
  }
  
  mutating func thirdCommand() {
    if let last = popLast() {
      list.insert(last, at: 0)
    }
  }
}

조금 긴데 나눠서 설명해보겠습니다.

struct SpinningQueue {
  var list = [Int]()
  
  var count: Int { self.list.count }
  
  func isEmpty() -> Bool {
    return list.isEmpty
  }
  
  func firstItem() -> Int? {
    return isEmpty() ? nil : list[0]
  }
  
  func lastItem() -> Int? {
    return isEmpty() ? nil : list.last!
  }

list는 정보를 담을 배열입니다. 여기서 정보는 숫자입니다.

count는 배열의 크기를 말합니다. 

isEmpty는 비어있는지 체크해줍니다.

firstItem과 lastItem은 첫번쨰 요소와 마지막 요소를 반환해줍니다. 

이 때, 비어있을 수 있으니 체크해줍니다.

  func getLocation(of number: Int) -> Int? {
    return list.firstIndex(of: number)
  }
  
  mutating func popFirst() -> Int? {
    if isEmpty() {
      return nil
    } else {
      let first = list[0]
      self.list.remove(at: 0)
      return first
    }
  }
  
  mutating func popLast() -> Int? {
    return self.list.popLast()
  }

getLocation 함수는 정보의 인덱스를 반환해줍니다.

어느 위치에 있는 지 알아야 2번 연산을 할 지, 3번 연산을 할 지 정할 수 있습니다.

popFirst 함수는 첫번째 숫자를 제거한 후 제거한 수를 반환해줍니다.

popLast 함수는 마지막 숫자로 같은 작업을 해줍니다.

 

  mutating func secondCommand() {
    if let first = popFirst() {
      list.append(first)
    }
  }
  
  mutating func thirdCommand() {
    if let last = popLast() {
      list.insert(last, at: 0)
    }
  }
}

마지막으로, 2번 연산과 3번 연산을 함수로 만들어주었습니다. 

 

이 자료구조를 이용한 최종 코드는 아래와 같습니다!

if let line = readLine()?.components(separatedBy: .whitespaces),
   let n = Int(line[0]),
   let m = Int(line[1]) {
  var db = SpinningQueue()
  for i in 1...n {
    db.list.append(i)
  }
  var secondCommandCount: Int = 0
  var thirdCommandCount: Int = 0
  if let numbers = readLine()?.components(separatedBy: .whitespaces) {
    for i in 0..<m {
      
      if let num = Int(numbers[i]) {
        // 여기서 num 은 숫자 위치입니다.
        if num == db.firstItem() {
          _ = db.popFirst()
        } else if db.getLocation(of: num)! <= (db.count / 2) {
          while num != db.firstItem() {
            db.secondCommand()
            secondCommandCount += 1
          }
          _ = db.popFirst()
        } else {
          while num != db.lastItem() {
            db.thirdCommand()
            thirdCommandCount += 1
          }
          db.thirdCommand()
          thirdCommandCount += 1
          _ = db.popFirst()
        }
      }
    }
  }
  print(secondCommandCount + thirdCommandCount)
}

전체 코드

import Foundation

struct SpinningQueue {
  var list = [Int]()
  
  var count: Int { self.list.count }
  
  func isEmpty() -> Bool {
    return list.isEmpty
  }
  
  func firstItem() -> Int? {
    return isEmpty() ? nil : list[0]
  }
  
  func lastItem() -> Int? {
    return isEmpty() ? nil : list.last!
  }
  
  func getLocation(of number: Int) -> Int? {
    return list.firstIndex(of: number)
  }
  
  mutating func popFirst() -> Int? {
    if isEmpty() {
      return nil
    } else {
      let first = list[0]
      self.list.remove(at: 0)
      return first
    }
  }
  
  mutating func popLast() -> Int? {
    return self.list.popLast()
  }
  
  mutating func secondCommand() {
    if let first = popFirst() {
      list.append(first)
    }
  }
  
  mutating func thirdCommand() {
    if let last = popLast() {
      list.insert(last, at: 0)
    }
  }
}

if let line = readLine()?.components(separatedBy: .whitespaces),
   let n = Int(line[0]),
   let m = Int(line[1]) {
  var db = SpinningQueue()
  for i in 1...n {
    db.list.append(i)
  }
  var secondCommandCount: Int = 0
  var thirdCommandCount: Int = 0
  if let numbers = readLine()?.components(separatedBy: .whitespaces) {
    for i in 0..<m {
      
      if let num = Int(numbers[i]) {
        // 여기서 num 은 숫자 위치입니다.
        if num == db.firstItem() {
          _ = db.popFirst()
        } else if db.getLocation(of: num)! <= (db.count / 2) {
          while num != db.firstItem() {
            db.secondCommand()
            secondCommandCount += 1
          }
          _ = db.popFirst()
        } else {
          while num != db.lastItem() {
            db.thirdCommand()
            thirdCommandCount += 1
          }
          db.thirdCommand()
          thirdCommandCount += 1
          _ = db.popFirst()
        }
      }
    }
  }
  print(secondCommandCount + thirdCommandCount)
}

👉https://github.com/wody27/algorithm-study/blob/master/BOJ/1021%20회전하는%20큐.swift 

GitHub - wody27/algorithm-study: 👻 알고리즘