백준 5397번: 키로거 - Swift 풀이

오늘의 문제

5397번: 키로거

 

나의 삽질 과정

1. 처음에는 res 변수를 빈 문자열로 초기화하고 cursor를 res의 인덱스(Int)로 두고 진행했었다. <, >일 때 cursor를 -1, +1하고 글자일 때는 res를 슬라이싱 해서 cursor를 기준으로 left, right로 나누고 res = left + String(i) + right 뭐 이런 식으로 했었다. 테스트 케이스는 통과했었으나 다른 케이스에서 IndexError가 났는지 제출 시 런타임 에러를 띄웠다.

 

2. 1번의 방식에서 - 부분의 조건문을 조금 고쳐서(요소 삭제 시 커서도 줄어든다는 점을 놓쳤었음) 질문 게시판에서 다른 테스트 케이스 찾아서 통과하고 제출을 다시 했는데 이번에는 시간 초과를 띄웠다.

 

3. Swift가 입력 어쩌구가 느려서 로직이 맞아도 시간 초과 뜰 때가 종종 있다.는 말이 기억나서 라이노 님의 FileIO를 사용해서 입력을 받아봤음. 똑같이 시간 초과 스껄돼서 질문 게시판에서 이 문제를 Swift로 푼 사람을 찾아다녔다. 그 분의 코드를 슥. 봤는데 (아예 베끼는 건 싫어서 정말 스크롤 내리면서 슥 봤음) 처음부터 left 스택, right 스택 이렇게 나눠놓고 그 사이에서 데이터를 왔다갔다 옮기는 식이었다.

오케이 이런 식으로 나도 바꿔보자.

 

4. 

case "<":
    if !left.isEmpty {
        guard let last = left.popLast() else { break }
        right = String(last) + right
    }

뭐 이런 식으로 left랑 right가 둘 다 String이니까 + 연산으로 글자들을 합쳤다.

-> 질문 게시판의 테스트 케이스들은 다 통과했는데 계속 시간 초과가 발생했다 ^..^

시간 초과의 발생 원인을 정확하게 알지 못해서 removeLast가 문제인가? popLast가 문제인가? right.first가 문제인가? 아님... 싹 다 문제인 걸까? 를 무한 반복하며 이거 저거 수정해서 다시 제출했으나 무한대의 시간 초과만 얻었다.

 

5. 풀기 시작한 지 1시간 반... 쯤 흘렀었나 이 정도면 할 수 있는 건 다 해봤고 더 이상 모르겠어서 (제발 Swift 풀이가 있길 바라면서) 구글링을 했다. 다행히 있었고 코드의 로직은 동일했다. 내 코드와 달랐던 지점은

나: + 연산으로 글자를 합침.
통과된 코드: 모든 글자를 append로 합침

ㄴ ?

처음 깨달았다. String끼리의 + 연산보다 String.append가 시간 복잡도가 덜한가보지? 정말 왜일까 레전드 충격적이다. popLast도 removeLast도 문제가 아닌... + 연산이 문제였다는 것.

근데 여기서 의문을 품을 수 있다. "<"의 경우에는 left의 맨 뒤의 값이 right의 맨 처음으로 들어가야 하는데 append는 맨 마지막에 들어가는 거잖아? 다 append 처리를 해도 되나?

-> 그래서 마지막에 left랑 right 값을 합칠 때 left와 right.reversed 값을 합친다.

즉 right는 left에 합쳐지기 전까지는 앞뒤 순서가 바뀐 상태로 유지된다. 그래서 "<" 이 경우에 left의 마지막 값을 right.append로 추가하면 이것은 right.reversed의 맨 처음 값이 된다.

 

이렇게만 고쳤더니... 무한 시간 초과의 늪을 빠져 나와 맞았습니다!를 볼 수 있었다.

 

내 최종 풀이

import Foundation

let T = Int(readLine()!)!

// 테스트 케이스 개수만큼 입력 받고 출력
for _ in 0..<T {
    let arr = readLine()!
    var left = "" // 커서를 기준으로 왼쪽에 있는 글자들
    var right = "" // 커서를 기준으로 오른쪽에 있는 글자들
    
    // 입력 받은 문장을 한 글자씩 순회
    for i in arr {
    	// 그 한 글자가
        switch i {
        // < 이면 커서가 왼쪽으로 한 칸 이동 -> left의 맨 뒤의 요소가 right로 들어가야 함
        case "<":
            // 일단 left가 비어있을 때는 달라질 게 없기 때문에 고려 안 함
            if !left.isEmpty {
            	// left의 맨 뒤의 요소를 빼서
                guard let last = left.popLast() else { break }
                // right의 맨 뒤에 추가 -> right는 나중에 reverse 할 거라서 앞뒤 바뀌어서 들어가게 됨
                right.append(last)
            }
        // > 이면 커서가 오른쪽으로 한 칸 이동 -> right의 첫 요소가 left로 들어가야 함 -> right는 현재 앞뒤가 바뀐 상태라서 right의 맨 뒤의 요소를 꺼내서 사용하면 됨
        case ">":
            // right가 비어있을 때는 이미 커서가 맨 오른쪽에 있다는 뜻이기 때문에 고려 안 함
            if !right.isEmpty {
            	// right의 맨 뒤의 요소를 빼서
                guard let last = right.popLast() else { break }
                // left의 맨 뒤에 추가
                left.append(last)
            }
        // - 이면 커서 왼쪽(left의 맨 뒤의 요소)을 삭제
        case "-":
            // left에 요소가 들어있을 때
            if !left.isEmpty {
            	// 맨 뒤의 요소 제거
                left.removeLast()
            }
        // 부호가 아니라 글자면 커서 왼쪽(left의 맨 뒤)에 추가
        default:
            // left의 맨 뒤에 추가
            left.append(i)
        }
    }
    
    // 모든 글자를 돌았는데 커서의 오른쪽에 글자들이 있다면
    if !right.isEmpty {
    	// right의 글자들을 앞뒤를 바꿔서 left에 이어붙인다 -> 원래 문장 생성됨
        for j in right.reversed() {
            left.append(j)
        }
    }
    
    // 최종 left 출력
    print(left)
}

 

코드 설명은 주석으로 대체.