[Swift] 2021 KAKAO INTERNSHIP 표편집

Problem

 

코딩테스트 연습 - 표 편집

---

Solution

해당 문제는 Linked List 자료구조를 이용해서 풀어야 하는 문제입니다.

 

1. 0부터 n까지 자기 이전의 숫자와 다음 숫자를 배열에 담아놓습니다.

 

func setLinkedList(n:Int) {
    for i in 0..<n {
        linkedList.append([i-1,i,i+1])
    }
}

 

(정석인 Linked List는 아니지만 제 방식대로 만들어봤습니다.)

 

2. 행을 위 or 아래로 이동할 때 선택된 index를 변경해줍니다.(D X or U X)

 

아래와 같이 현재 숫자의 전을 past로 다음을 next로 표시하고

 

x만큼 행을 이동해줍니다.

 

func past(_ index:Int) -> Int {
    return linkedList[index][0]
}

func next(_ index:Int) -> Int{
    return linkedList[index][2]
}

func moveColumn(x:Int,isUp:Bool){
    for _ in 0..<x {
        if isUp {
            selectedIndex = past(selectedIndex)
        }else {
            selectedIndex = next(selectedIndex)
        }
    }
}

 

3. 행이 삭제되었을때 linkedList를 바꿔주고 삭제된 index를 저장합니다.

 

만약 1 - 3 - 5가 연결되었고 3이 삭제되었다면 1 - 5 가 연결되어야겠죠?

 

(0 1 3 - 1 3 5 - 3 5 6 과 같이 저장되어 있을거에요)

 

그러므로 삭제된 전 숫자의 다음 숫자를 삭제된 다음 숫자로 연결해주고 (0 1 3 -> 0 1 5)

 

삭제된 다음 숫자의 전 숫자를 삭제된 전 숫자로 연결해줍니다. ( 3 5 6 -> 1 5 6)

 

그리곤 나중에 복구를 위해서 삭제된 Index를 removeHistory에 저장해줍니다.

 

func removeColumn() {
    changeLinkedList(selected: selectedIndex)
    removeHistory.append(selectedIndex)
    if next(selectedIndex) == linkedList.count {
        selectedIndex = past(selectedIndex)
    }else {
        selectedIndex = next(selectedIndex)
    }
}

 

4. 가장 마지막에 삭제된 index를 복구시켜주고 그에 맞게 linkedList를 변경해줍니다.

 

복구되는 숫자의 전 숫자의 다음 숫자를 현재 복구되는 숫자로 바꿔주고

 

복구되는 숫자의 다음 숫자의 전 숫자를 현재 복구되는 숫자로 바꿔줍니다.

 

func restoreColumn() {
    let restore = removeHistory.removeLast()
    if past(restore) >= 0 {
        linkedList[past(restore)][2] = restore
    }
    if next(restore) <= linkedList.count - 1 {
        linkedList[next(restore)][0] = restore
    }
}

 

5. n갯수만큼 O가 담긴 배열을 만들어주고 removeHistory의 index를 X로 바꿔줍니다.

 

바뀐 배열을 joined 메소드를 이용해 문자열로 바꿔주고 반환해줍니다.

 

 var result = Array(repeating: "O", count: n)
    
    for r in removeHistory {
        result[r] = "X"
    }
    
    return result.joined()

---

Source Code

 

	import Foundation
	var selectedIndex:Int = 0
	var linkedList = [[Int]]()
	var removeHistory:[Int] = []
	func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {
	return makeResultByCommand(cmd: cmd, n: n,k: k)
	}
	func makeResultByCommand(cmd:[String],n:Int,k:Int) -> String {
	initialSetting(n: n,k:k)
	for command in cmd {
	changeByCommands(command: command)
	}
	var result = Array(repeating: "O", count: n)
	for r in removeHistory {
	result[r] = "X"
	}
	return result.joined()
	}
	func initialSetting(n:Int,k:Int) {
	selectedIndex = k
	for i in 0..<n {
	linkedList.append([i-1,i,i+1])
	}
	}
	func changeByCommands(command:String) {
	let split = command.components(separatedBy: " ")
	if command.first == "D" {
	moveColumn(x: Int(split.last!)!, isUp: false)
	}else if command.first == "U" {
	moveColumn(x: Int(split.last!)!, isUp: true)
	}else if command.first == "C" {
	removeColumn()
	}else {
	restoreColumn()
	}
	}
	func past(_ index:Int) -> Int {
	return linkedList[index][0]
	}
	func next(_ index:Int) -> Int{
	return linkedList[index][2]
	}
	func changeLinkedList(selected:Int) {
	linkedList[selected][1] = -1
	if past(selected) >= 0 {
	linkedList[past(selected)][2] = next(selected)
	}
	if next(selected) <= linkedList.count - 1 {
	linkedList[next(selected)][0] = past(selected)
	}
	}
	func moveColumn(x:Int,isUp:Bool){
	for _ in 0..<x {
	if isUp {
	selectedIndex = past(selectedIndex)
	}else {
	selectedIndex = next(selectedIndex)
	}
	}
	}
	func removeColumn() {
	changeLinkedList(selected: selectedIndex)
	removeHistory.append(selectedIndex)
	if next(selectedIndex) == linkedList.count {
	selectedIndex = past(selectedIndex)
	}else {
	selectedIndex = next(selectedIndex)
	}
	}
	func restoreColumn() {
	let restore = removeHistory.removeLast()
	if past(restore) >= 0 {
	linkedList[past(restore)][2] = restore
	}
	if next(restore) <= linkedList.count - 1 {
	linkedList[next(restore)][0] = restore
	}
	}

view raw 표편집.swift hosted with ❤ by GitHub

---

P.S

 

처음에 문제를 풀 때 뭐 이렇게 쉬워? 하면서 풀었는데... 역시나 효율성에서 전부 다 시간초과가 났다...

 

계속 코드를 개선시키면서 해도 시간초과가 해결되지 않았다.

 

결국 카카오 홈페이지로 가서 풀이를 보니 Linked List로 풀어야하는 문제였다.

 

그동안 Linked List를 한번도 안써봐서 어떻게 접근해야할지 막막했는데 그냥 배열에 전 숫자와 다음 숫자를

 

담아놓으니깐 어느정도 구현은 됐다.

 

나중에 Linked List를 Swift로 어떻게 만드는지 공부해봐야겠다.