UIImageView ← 공식문서 참고
struct Deque<T> {
private var elements: [T] = []
public var size: Int {
return elements.count
}
public var empty: Int {
return elements.isEmpty ? 1 : 0
}
public func front() -> T? {
return self.elements.first
}
public func back() -> T? {
return self.elements.last
}
public mutating func push_front(_ element: T) {
return elements.insert(element, at: 0)
}
public mutating func push_back(_ element: T) {
return elements.append(element)
}
public mutating func pop_front() -> T? {
return elements.isEmpty ? nil : elements.removeFirst()
}
public mutating func pop_back() -> T? {
return elements.isEmpty ? nil : elements.removeLast()
}
}
let N = Int(readLine()!)!
var intQueue = Deque<Int>()
for _ in 0..<N {
let inputs = readLine()!.split(separator: " ")
switch inputs[0] {
case "push_front":
intQueue.push_front(Int(inputs[1])!)
case "push_back":
intQueue.push_back(Int(inputs[1])!)
case "pop_front":
print(intQueue.pop_front() ?? -1)
case "pop_back":
print(intQueue.pop_back() ?? -1)
case "size":
print(intQueue.size)
case "empty":
print(intQueue.empty)
case "front":
print(intQueue.front() ?? -1)
default:
print(intQueue.back() ?? -1)
}
}
Front 와 Back 을 구분하는것 이외에는 큐 문제와 완전 똑같았다,
채점결과 한번 틀렸는데
front 와 back 개념을 잘못 설정했다 .. 머쓱 ^^
back 함수들을 추가하여
insert(item, at: index) 를 통해 첫 요소에 값을 넣어 push_front 를 구성 하였고,
removeLast 함수를 사용해 마지막 요소를 제거해 주었다
var result = [Int]()
let inputs = readLine()!.split(separator: " ")
var num: [Int] = Array(1...Int(inputs[0])!)
var idx = Int(inputs[1])! - 1
while true {
result.append(num.remove(at: idx))
if num.isEmpty { break }
idx = (idx + Int(inputs[1])! - 1) % num.count
}
print("<\(result.map({ String($0)}).joined(separator: ", "))>")
문제를 이해하는데 그림을 그려야 했다.. 그래서 발로 그린듯한 그림을..
이렇게 원형으로 앉아있을때 K번 순으로 제거하는 문제였다
K번째를 셀때, 제거된 자리는 건너뛰고 세어야 한다!!
코드에서 inputs[0] 에는 N 이, inputs[1] 에는 K 가 들어간다.
그리고 나서 규칙을 찾기위해 열심히.. 그림을 그렸다
처음 idx 는 K - 1 ( 인덱스는 0부터 시작하기 때문!! ) 가 되고,
이후로 제거할때 마다 idx 를 바꿔줘야 하는데, 어떻게 바꿀지를 그리면서 고민한 결과 규칙을 찾았다!
1. 우선 idx 인덱스 요소를 제거한다
2. 현재 idx 의 값에 K-1 을 더한후, 제거후 남은 배열의 갯수로 나눈 나머지로 재설정한다 ( idx = (idx + (k-1)) % Array.count )
3. 무한 루프로 돌되, 제거후 배열이 비어 있는 상태가 되면 루프를 종료시킨다!
알고나면 간단한 문제였다..
이래서 그리면서 생각하는게 중요한가봄..
struct Queue<T> {
private var elements: [T] = []
public var size: Int {
return elements.count
}
public var empty: Int {
return elements.isEmpty ? 1 : 0
}
public func front() -> T? {
return self.elements.first
}
public func back() -> T? {
return self.elements.last
}
public mutating func push(_ element: T) {
return elements.append(element)
}
public mutating func pop() -> T? {
return elements.isEmpty ? nil : elements.removeFirst()
}
}
let N = Int(readLine()!)!
var intQueue = Queue<Int>()
for _ in 0..<N {
let inputs = readLine()!.split(separator: " ")
switch inputs[0] {
case "push":
intQueue.push(Int(inputs[1])!)
case "pop":
print(intQueue.pop() ?? -1)
case "size":
print(intQueue.size)
case "empty":
print(intQueue.empty)
case "front":
print(intQueue.front() ?? -1)
default:
print(intQueue.back() ?? -1)
}
}
Queue에 대한 개념을 학습하고, 이를 Swift 로 구현한 후 문제를 보니 쉽게 다가왔다,
Queue를 정의한 struct를 이용해서 문제를 풀 수 있었다.
그런데 풀이코드와 같은 Queue의 구조를 쓰게되면 메모리 효율이 떨어지기 때문에 다른 방법으로 큐를 구현하여 풀었더니
분명 TastCase 모두 정답이 나왔고, 문제없이 잘 출력 되었는데 틀렸다는 채점결과를 얻게되었다.
아직까지 뭐가 문제인지 모르겠다,, 이것저것 테스트를 해보았지만 정상적으로 값이 출력되었는데 도저히 모르겠다.
혹시나 해서 메모리 효율을 무시하고 그냥 원래의 방식대로 풀었더니 맞았다고 나왔다..
출력 결과는 같은데 도대체 뭐가 다른건지.. 도저히 모르겠다..
문제의 코드
struct Queue<T> {
private var elements: [T?] = []
private var head = 0
public var size: Int {
var numberOfNonNilValues = 0
for case .some in elements { numberOfNonNilValues += 1 }
return numberOfNonNilValues
}
public var empty: Int {
return elements.isEmpty ? 1 : 0
}
public func front() -> T? {
return self.elements.first ?? nil
}
public func back() -> T? {
return self.elements.last ?? nil
}
public mutating func push(_ element: T) {
return elements.append(element)
}
public mutating func pop() -> T? {
guard head < elements.count, let element = elements[head] else { return nil }
elements[head] = nil
head += 1
if head > (elements.count / 3) {
elements.removeFirst(head)
head = 0
}
return element
}
}
let N = Int(readLine()!)!
var intQueue = Queue<Int>()
var element: Int?
for _ in 0..<N {
let inputs = readLine()!.split(separator: " ")
switch inputs[0] {
case "push":
intQueue.push(Int(inputs[1])!)
case "pop":
print(intQueue.pop() ?? -1)
case "size":
print(intQueue.size)
case "empty":
print(intQueue.empty)
case "front":
print(intQueue.front() ?? -1)
default:
print(intQueue.back() ?? -1)
}
}
// Queue 선언
struct Queue<T> {
private var elements: [T] = []
public var count: Int {
return elements.count
}
public var isEmpty: Bool {
return elements.isEmpty
}
public mutating func enqueue(_ element: T) {
return elements.append(element)
}
public mutating func dequeue() -> T? {
return isEmpty ? nil : elements.removeFirst()
}
}
// Queue 사용
var intQueue = Queue<Int>()
print(intQueue)
// Queue<Int>(elements: [])
intQueue.enqueue(3)
print(intQueue)
// Queue<Int>(elements: [3])
print(intQueue.count)
print(intQueue.isEmpty)
// 1
// false
intQueue.dequeue()
print(intQueue.isEmpty)
// true
구현 한거 아니야? 뭐가 문제야!!!
응.. 문제야..
⇒ 위 그림에서는 한번만 수행되지만 만약 dequeue가 여러번 수행된다면..? 엄청난 메모리 낭비를 하게 될것이다
요소 하나하나 제거할 때마다 만약 queue내의 item이 100개, 1000개 라면,, 요소 하나를 제거하기 위해 수없이 많이 인덱스를 한칸씩 당겨주어야 한다
struct Queue<T> {
// nil 이 포함되기 때문에 [T?] 의 Optional 타입으로 선언
private var elements: [T?] = []
private var head = 0
// nil 인경우 count를 안하기 위해 for case 문을 사용
public var count: Int {
var elementCount = 0
for case .some in elements { elementCount += 1 }
return elementCount
}
public var isEmpty: Bool {
return elements.isEmpty
}
public mutating func enqueue(_ element: T) {
return elements.append(element)
}
public mutating func dequeue() -> T? {
// head 가 큐의 아이템 갯수보다 크거나, head가 가르키는 곳이 nil 일경우 nil 반환
guard head < elements.count, let element = elements[head] else { return nil }
elements[head] = nil
head += 1
// Queue아이템의 1/3 보다 클경우마다 인덱스 0부터 head 까지 요소를 제거하고 head 0으로 초기화
if head > (elements.count / 3) {
elements.removeFirst(head)
head = 0
}
return element
}
}var iQ = Queue<Int>()
iQ.enqueue(3)
iQ.enqueue(4)
iQ.enqueue(5)
iQ.count
// 3
iQ.dequeue()
// 3
iQ.count
// 2
iQ
// [nil, 4, 5] , head = 1
iQ.dequeue()
// 4
iQ
// [5], head = 0
iQ.count
// 1
iQ.dequeue()
// 5
iQ
// [], head = 0
iQ.dequeue()
// nil
iQ.count
// 0
iQ.dequeue()
// nil
참고 링크