Chikong

문제

풀이 코드

// 변수 선언
var inputs = readLine()!
var commandResult = ""
let commandCount = Int(readLine()!)!

for _ in 0..<commandCount {
    let command = readLine()!
    
    switch command {
    case "L":
        if !inputs.isEmpty { commandResult.append(inputs.popLast()!) }
    case "D":
        if !commandResult.isEmpty { inputs.append(commandResult.popLast()!) }
    case "B":
        if !inputs.isEmpty { inputs.removeLast() }
    default:
        inputs.append(command.last!)
    }
}

print(inputs + commandResult.reversed())

풀이 과정

// 변수 선언
var result = readLine()!
let commandCount = Int(readLine()!)!
var cursor = result.count

for _ in 0..<commandCount {
    let index = result.index(result.startIndex, offsetBy: cursor)
    let command = readLine()!.split(separator: " ")
    
    switch command[0] {
    case "P":
        result.insert(contentsOf: command[1], at: index)
        cursor += 1
    case "L":
        if cursor - 1 >= 0 { cursor -= 1 }
    case "D":
        if cursor + 1 <= result.count { cursor += 1 }
    default:
        if cursor > 0 {
            cursor -= 1;
            let removeIndex = result.index(result.startIndex, offsetBy: cursor)
            result.remove(at: removeIndex) }
    }
}

print(result)

처음, 위와 같은 방식으로 문제를 풀었다, 하지만 시간초과 가 발생했습니다.

이리 저리 고쳐 봤지만, 시간 초과 문제를 해결하지 못했습니다.

그래서 검색해본 결과

1. split을 쓰면 시간이 오래걸림
2. 내가 짠 코드에서 String.index 로 변환하고, 다시 변수 생성하고 등등의 과정으로 오랜 시간이 소요됨

이라는 결론을 낼 수 있었고, Stack 구조체를 이용하여 풀어야 한다고 생각했지만,

그런데 전에 풀었던 방식으로 구조체로 사용하게되면 string 을 각각 문자로 변환하고 그걸 또 스택에 넣어야 하는 과정속에서 또 다시 시간초과가 날 거 같아서 그냥 배열로 처리를 해주었습니다.

입력된 결과에서 현 커서의 위치가 이동될 때 마다 새로운 문자열(commandResult)에 Push 해 주거나 원 문자열에서 pop 해주면서 계산해주어 풀이했습니다.

문제

풀이 코드

// Stack 구조체 선언
public struct Stack<T> {
    private var elements = [T]()
    public init() {}
    
    public mutating func pop() -> T? {
        return self.elements.popLast()
    }
    
    public mutating func push(_ elements: T) {
        self.elements.append(elements)
    }
    
    public func top() -> T? {
        return self.elements.last
    }
    
    public var empty: Bool {
        return self.elements.isEmpty
    }
}

// 변수 선언
let n = Int(readLine()!)!
var sequence = [Int]()
var result = [String]()
var sequenceStack = Stack<Int>()
var pushValue = 1

// 입력값 저장 배열
for _ in 0..<n { sequence.append(Int(readLine()!)!) }

// 1부터 현재의 value 까지 채워넣고, 스택의 마지막 값과 현재 value 의 값을 비교하여 같으면 pop, 다르면 해당 수열을 만들 수 없으므로 NO 출력
for value in sequence {
    while pushValue <= value {
        sequenceStack.push(pushValue)
        result.append("+")
        pushValue += 1
    }
    if sequenceStack.top()! == value {
        sequenceStack.pop()
        result.append("-")
    } else { print("NO"); break }
}

// 스택이 비어있는 상태면 정상적인 계산 완료
if sequenceStack.empty {
    print(result.joined(separator: "\n"))
}

풀이 과정

조금 어려웠다 일단 문제 이해가 어려웠고, 그다음 구현이 어려웠다.. 그렇게 몇시간을 고민하다가 다른 분들의 코드를 보고 힌트를 얻어 구현했다..

일단 문제를 해설하자면 입력으로 주어진 순서의 값들이, 스택에 1부터 오름차순으로 push 해서 pop 할때와의 순서와 같아야 하고, 그렇게 할수 없는 경우 NO를 출력하면 된다

나도 이게 무슨소리인지 몰랐지만

정리하면 예시로 나온 4 3 6 8 7 5 2 1 로 보자

처음에  4가 pop으로 나와야하니 스택에

1 2 3 4 가 들어가고 4 가 pop 된다 그러면 

+ + + + - 까지 되고 그다음 숫자인 3이 pop되야하니 그냥 pop하면 된다 그러면

+ + + + - - 까지가 4 3 이 출렷 된다! 그다음 숫자는 6이기 때문에 우선 6까지 채워줘야 하므로

+ + + + - - + + 이렇게 하면 스택에 1 2 5 6 이 있고, 여기서 pop을 하면 1 2 5 가 스택에 남는다

+ + + + - - + + - 이렇게 반복하여서 Push 할땐 + 를, pop할땐 - 를 해주면 된다,

그러다가 중간에 pop을 해도 해당 순서로 정렬할수 없는경우 가차없이 NO를 출력하면 된다!

여기에 해당하는 조건은 stack.top() 이 현재 출력해야할 수보다 크면 순서대로 정렬할 수 없기 때문에 NO를 출력하면 된다!!

문제를 이해하고나면 그리 많이 어려운 문제는 아니였는데,, 

이해하는데도 오래걸리고 1부터 채워서 어떻게 출력하지? 라는 고민때문에 다른분의 코드를 보고 힌트를 얻은게 참 아쉽다

문제

풀이 코드

// [BOJ] 9012 - 괄호
public struct Stack<T> {
    private var elements = [T]()
    public init() {}
    
    public mutating func pop() -> T? {
        return self.elements.popLast()
    }
    
    public mutating func push(_ element: T) {
        self.elements.append(element)
    }
    
    public var empty: Bool {
        return self.elements.isEmpty
    }
}

let T = Int(readLine()!)!

for _ in 0..<T {
    let ps = readLine()!
    var psStack = Stack<Character>()
    var result = "YES"
    
    for item in ps {
        if item == "(" { psStack.push(item) }
        else {
            if psStack.empty { result = "NO";break }
            else { psStack.pop() }
        }
    }
    if !psStack.empty { result = "NO" }
    print(result)
}

풀이 과정

Stack 을 이용하여 문제를 풀어보았다.

전체적인 프로세스는 다음과 같다.

이렇게 스택을 이용하여 풀이를 하였지만,

아무래도 가독성이 너무 떨어지는것 같다.

사실 처음에는 단순히 +1 . -1 해서 판단 하려 했으나, 이번주 알고리즘 스터디 내용이 Stack 이기 때문에 스택을 이용하여 풀이를 해보았다

문제

풀이 코드

// [BOJ] 9093 - 단어 뒤집기

let T = Int(readLine()!)!
var sentReversed : String

for _ in 0..<T {
    sentReversed = ""
    let sentence = readLine()!.split(separator: " ")
    sentence.forEach {
        sentReversed.append($0.reversed() + " ")
    }
    print(sentReversed)
}

풀이 과정

크게 두가지 메서드를 이용하여 구현 했다.

1. ForEach 

2. reversed

foreach 를 사용하여 배열 내부의 모든 요소를 검사하여 각 단어의 반전을 주었다!

reversed 메서드를 사용하여 쉽게 순서를 뒤집었는데

reverse 와 reversed 가 있다. 간단히 살펴보면 다음과 같다

1. reverse

- 원래의 배열 자체를 반전하여 변화시킴

- 시간복잡도 O(n) 

2. reversed

- 호출 할때만 반전되고 원래의 배열 자체는 변화하지 않음

- 시간복잡도 O(1)

효율성을 위하여 reversed 를 사용 하였다!

문제

풀이코드

// [BOJ] 10828 - 스택

public struct Stack<T> {
    private var elements = [T]()
    public init() {}
    
    public mutating func pop() -> T? {
        return self.elements.popLast()
    }
    
    public mutating func push(_ element: T) {
        self.elements.append(element)
    }
    
    public func top() -> T? {
        return self.elements.last
    }
    
    public var empty: Int {
        return self.elements.isEmpty ? 1 : 0
    }
    
    public var size: Int {
        return self.elements.count
    }
}

let N = Int(readLine()!)!
var intStack = Stack<Int>()
var lastElement : Int?
for _ in 0..<N {
    let command = readLine()!.split(separator: " ")
    switch command[0] {
    case "push":
        intStack.push(Int(command[1])!)
    case "pop":
        lastElement = intStack.pop()
        print(lastElement == nil ? -1 : lastElement!)
    case "size":
        print(intStack.size)
    case "empty":
        print(intStack.empty)
    default:
        lastElement = intStack.top()
        print(lastElement == nil ? -1 : lastElement!)
    }
}

풀이과정

https://ai-hong.tistory.com/198?category=1001478 

에서 설명한 것과 같이 오늘은 스택을 이용한 문제를 풀었다.

개념을 공부하고 문제를 보니 큰 어려움은 없었다.

구조체로 스택을 선언하고, 다만 문제에 나와있는대로 그 내용을 조금 변경했다.

문제에

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

가 나와 있기 때문에 이를 따라 구조체를 선언해 주었고,

Switch - case 구문을 통하여 각각의 상황에 맞는 함수 혹은 파라미터를 호출해 주었다 :)

문제에서 지정된 명령어 이외의 명령은 없다고 나와있기에

"top"같은 경우, default 에 기능을 넣어 주었다

깔끔히 통과!