Chikong

문제

풀이 코드

struct Queue<T> {
    private var elements: [T] = []
    private var reverseElement: [T] = []

    public var size: Int {
        return elements.count + reverseElement.count
    }

    public mutating func push(_ element: T) {
        return elements.append(element)
    }

    public mutating func pop() -> T? {
        if reverseElement.isEmpty {
            reverseElement = elements.reversed()
            elements.removeAll()
        }
        return reverseElement.isEmpty ? nil : reverseElement.popLast()
    }
}

var queue = Queue<Int>()
let N = Int(readLine()!)!

for n in 1...N {
    queue.push(n)
}

while queue.size != 1 {
    queue.pop()
    if let item = queue.pop() {
        queue.push(item)
    }
}

print(queue.pop()!)

풀이 과정

그냥 Queue를 이용하여 풀면 될거 같았다.

큐를 이용해 간단하게 구현하였지만 시간초과가 발생했다.

그 이유는 removeFirst 때문인데 첫 요소를 제거하면 다음의 엘리먼트들을 앞으로 한칸씩 땡겨와야 하기 때문에 연산시간이 오래걸린다.

그래서 removeElement 라는 변수를 큐 구조체내에 따로 구현해 주고, reversed 를 통해 마지막 요소를 제거하도록 했더니 시간초과 문제가 해결 되었다.

알고리즘을 풀때 첫요소나 중간 요소를 제거하면 그만큼 연산시간이 오래 걸린다는것을 배웠다.

문제

풀이 코드

let inputs = readLine()!
var stack = ""
var answer = ""

for op in inputs {
    switch op {
    case "(":
        stack.append(op)
    case ")":
        while !stack.isEmpty && stack.last != "("{
            answer.append(stack.removeLast())
        }
        stack.removeLast()
    case "*", "/":
        while !stack.isEmpty && (stack.last == "*" || stack.last == "/") {
            answer.append(stack.removeLast())
        }
        stack.append(op)
    case "+", "-":
        while !stack.isEmpty && stack.last != "(" {
            answer.append(stack.removeLast())
        }
        stack.append(op)
    default:
        answer.append(op)
    }
}

while !stack.isEmpty {
    answer.append(stack.removeLast())
}
print(answer)

풀이 과정

스택을 이용하여 풀이 하였다.

괄호를 만나면 일단 스택에 넣어주고, 닫는 괄호가 나왔을때, 우선순위가 모두 종료된 의미이기 때문에 스택에 있는 연산자를 모두 꺼내 주었고,

곱셈 이나 나눗셈을 만나면 곱셈 나눗셈까지 모두 꺼내 주고, 

덧셈이나 뺄셈이 나오면 괄호 를 만날때 까지 꺼내주었다.

문제

풀이 코드

import Foundation

let N = Int(readLine()!)!
let formula = readLine()!
var num = [Int]()
var answer = [Double]()

for _ in 0..<N {
    num.append(Int(readLine()!)!)
}

for op in formula {
    switch op {
    case "*":
        answer.append(answer.removeLast() * answer.removeLast())
    case "/":
        let stackLast = answer.removeLast()
        answer.append(answer.removeLast() / stackLast)
    case "+":
        answer.append(answer.removeLast() + answer.removeLast())
    case "-":
        let stackLast = answer.removeLast()
        answer.append(answer.removeLast() - stackLast)
    default:
        let idx = op.asciiValue! - 65
        answer.append(Double(num[Int(idx)]))
    }
}

print(String(format: "%.2f", answer.removeLast()))

풀이 과정

알파벳을 포함한 별도의 배열을 선언해 주고 계산을 해야하나 고민했는데,

Ascii 코드를 이용해서 인덱스를 할당하여 구현하면 된다고 생각했다.

A 의 아스키 코드는 65 이고, 입력받은 숫자들을 별도의 배열로 지정하여

A 일때는 0인덱스의 수를, B일때는 1인덱스의 수를 ... 이렇게 할당하면 될것같았다.

그렇게 그냥 스택을 이용해 풀이를 해주었고, 고려해야 할 점은 두가지였다.

- 와 / 인데,

덧셈과 곱셈의 경우 순서가 상관 없지만, 뺄셈과 나눗셈은 순서가 중요하기 때문에, 먼저 removeLast 를 수행하여 순서를 지정해 주었다.

이렇게 풀고 소숫점 2번째 자리까지만 출력하기 위해

String의 format 을 이용해 C언어의 printf 처럼 할당해 주었다

문제

풀이 코드

let N = Int(readLine()!)!
var nums = readLine()!.split(separator: " ").map{Int(String($0))!}
var numCount = Array(repeating: 0, count: nums.max()!)
var answer = [Int]()

// 등장횟수 계산
for idx in 0..<N {
    numCount[nums[idx] - 1] += 1
}

// 오등큰수 인덱스 검색
for idx in 0..<N {
    while !answer.isEmpty && numCount[nums[answer.last!] - 1] < numCount[nums[idx] - 1] {
        nums[answer.removeLast()] = nums[idx]
    }
    answer.append(idx)
}

for idx in answer {
    nums[idx] = -1
}

print(nums.map{String($0)}.joined(separator: " "))

풀이 과정

이전에 풀었던 오큰수와 크게 다르지 않은 문제라서 거의 코드를 가져온 수준이였다.

대신 다른점이 있다면, 입력된 값 내에서 최대값만큼 배열을 생성해 주었고, count 를 계산하여

count 를 비교하며 오큰수와 같은 형식으로 풀었다.

문제

풀이 코드

let n = Int(readLine()!)!
var nums = readLine()!.split(separator: " ").map{Int(String($0))!}
var answer = [Int]()

for index in 0..<n {
    while !answer.isEmpty && nums[answer.last!] < nums[index] {
        nums[answer.removeLast()] = nums[index]
    }
    answer.append(index)
}

for index in answer {
    nums[index] = -1
}

print(nums.map{String($0)}.joined(separator: " "))

풀이 과정

혼자 해결하지 못한 문제였다.

처음 생각은 filter를 이용해 현재 인덱스의 값보다 작은것들만 모아놓고,

그렇게 생성된 배열이 비어있으면 -1을, 

비어있지 않으면 해당 배열의 첫번째 인덱스를 저장하면 될것 같았는데

애초에 그렇게 구현하지 못하는 문제였기도 했고, 가능하다 했어도 매번 filter를 사용해야 하기 때문에 시간초과에서 걸렸을것 같았다.

그래서 인터넷의 코드를 참고하여 이해하는 수준에 그쳤다..

너무 어려운 문제였다.

우선,

answer 배열에 -1이 들어갈 인덱스를 저장한다.

그리고 for 루프 내에서 while 루프를 돌려, 오큰수를 찾고, 오큰수를 찾지 못하면 해당 인덱스를 저장하여

마지막에 해당인덱스 요소를 -1 로 바꿔 주었다.

디버깅