민성이가 공유한 알고리즘 문제

[shinychan95]

# 트랜잭션을 지원하는 스택 구현
# 트랜잭션은 중첩될 수 있음
# - push(): 새로운 값을 현재 스택에 추가
# - top(): 가장 마지막에 추가되었던 값을 반환. 만약 비어있을 경우 0 반환
# - pop(): 가장 마지막에 추가되었던 값을 제거. 만약 비어있을 경우 아무일도 일어나지 않음
# - begin(): 새로운 트랜잭션을 시작
# - rollback(): 현재 트랜잭션을 롤백하고 true 반환. 만약 현재 진행 중인 트랜잭션이 없다면 false 반환
# - commit(): 현재 트랜잭션을 커밋하고 true 반환. 만약 현재 진행 중인 트랜잭션이 없다면 false 반환
​
​
class StackWithTransaction(object):
    def __init__(self) -> None:
        pass
​
    def push(self, value: int) -> None:
        pass
​
    def top(self) -> int:
        pass
​
    def pop(self) -> None:
        pass
​
    def begin(self) -> None:
        pass
​
    def rollback(self) -> bool:
        pass
​
    def commit(self) -> bool:
        pass
​
​
def test():
    swt = StackWithTransaction()
    swt.push(42)
    swt.begin()
    assert swt.top() == 42
    swt.pop()
    assert swt.top() == 0
    swt.pop()
    assert swt.top() == 0
    swt.push(5)
    swt.push(7)
    assert swt.top() == 7
    swt.begin()
    swt.push(10)
    swt.push(3)
    assert swt.top() == 3
    swt.commit()
    assert swt.top() == 3
    swt.rollback()
    assert swt.top() == 42
​
​
test()

[shinychan95]

질문

1. 트랜잭션 시작 중에 또 시작하면, 새로운 시작 지점부터 시작인건가. 아니면 이전 시작 지점으로 인식하는 건가? (테스트 케이스를 보면 이전 시작 시점으로 보이긴 한다)

2. 롤백의 경우 (시작~커밋) 전으로 돌아가는 것으로 보이는데, 커밋이 없다면 어떡하나? 아무 영향 없는가?

3. 롤백 조건에 진행 중인 트랜잭션이 없으면 false 라고 하는데, 커밋은 트랜잭션의 종료를 의미하는 것이 아닌가?

답

1. 트랜잭션이 중첩되는거임. 첫번째 트랜잭션 안에서 두번째 트랜잭션이 시작하는것
2. 롤백하면 가장 직전의 트랜잭션만 원복하면 댐
3. 커밋은 트랜잭션의 반영

[shinychan95]

풀이

type SWT struct {
    master []int        // 커밋 전까지 롤백을 위한 원본 스택, pop 함수가 적용되지 않는다.
    dev []int           // push, top, pop 함수가 모두 적용되는 스택. 트랜잭션 단위로 관리해야 한다.
    begins [][]int      // 두 스택의 트랜잭션 시작 지점을 저장하는 배열
    recovers [][]int    // 트랜잭션 롤백 시 복구할 원소들
}

func main() {
    var swt SWT

    push := func(v int) {
        swt.master = append(swt.master, v)
        swt.dev = append(swt.dev, v)
    }

    top := func() int {
        dLen := len(swt.dev)
        if dLen == 0 {
            return 0
        }

        return swt.dev[dLen - 1]
    }

    pop := func() {
        dLen := len(swt.dev)
        if dLen == 0 {
            return
        }

        mLen := len(swt.master)
        bLen := len(swt.begins)
        if bLen == 0 { // 트랜잭션이 진행 중이지 않으면 원본에서도 제거
            swt.master = swt.master[:mLen - 1]
            swt.dev = swt.dev[:dLen - 1]

            return
        }

        // 트랜잭션이 진행 중인 경우
        if swt.begins[bLen - 1][0] > mLen - 1 { // 트랜잭션 이전 데이터가 pop 되는 경우
            elem := swt.dev[dLen - 1]
            swt.recovers[bLen - 1] = append(swt.recovers[bLen - 1], elem) // 복원 데이터에 추가한다.

            swt.dev = swt.dev[:dLen - 1]
            swt.begins[bLen - 1][1]-- // dev 브랜치의 복원 시점을 감소한다.
        }
    }

    begin := func() {
        swt.begins = append(swt.begins, []int{len(swt.master), len(swt.dev)})
        swt.recovers = append(swt.recovers, []int{})
    }

    commit := func() bool {
        bLen := len(swt.begins)

        if bLen == 0 {
            return false
        }

        swt.begins = swt.begins[:bLen - 1]
        swt.recovers = swt.recovers[:bLen - 1]
        return true
    }

    rollback := func() bool {
        bLen := len(swt.begins)

        if bLen == 0 {
            return false
        }

        swt.master = swt.master[:swt.begins[bLen - 1][0]]
        swt.dev = swt.dev[:swt.begins[bLen - 1][1]]
        swt.dev = append(swt.dev, swt.recovers[bLen - 1]...) // dev 스택의 경우, 원본 스택에서 pop 수 만큼 뺀다 (예외)

        swt.begins = swt.begins[:bLen - 1]
        swt.recovers = swt.recovers[:bLen - 1]
        return true
    }

    // TEST #1
    push(42)
    begin()
    if top() != 42 { panic("error") }
    pop()
    if top() != 0 { panic("error") }
    pop()
    if top() != 0 { panic("error") }
    push(5)
    push(7)
    if top() != 7 { panic("error") }
    begin()
    push(10)
    push(3)
    if top() != 3 { panic("error") }
    commit()
    if top() != 3 { panic("error") }
    rollback()
    if top() != 42 { panic("error")}

    // FINISH
    swt.master = nil
    swt.dev = nil
    swt.begins = nil
    swt.recovers = nil

    // TEST #2
    push(1)
    if top() != 1 { panic("error") }
    push(2)
    if top() != 2 { panic("error") }
    push(3)
    if top() != 3 { panic("error") }
    begin()
    if top() != 3 { panic("error") }
    pop()
    if top() != 2 { panic("error") }
    push(4)
    if top() != 4 { panic("error") }
    push(5)
    if top() != 5 { panic("error") }
    begin()
    if top() != 5 { panic("error") }
    pop()
    if top() != 4 { panic("error") }
    push(6)
    if top() != 6 { panic("error") }
    push(7)
    if top() != 7 { panic("error") }
    begin()
    if top() != 7 { panic("error") }
    pop()
    if top() != 6 { panic("error") }
    push(8)
    if top() != 8 { panic("error") }
    push(9)
    if top() != 9 { panic("error") }
    rollback()
    if top() != 7 { panic("error") }
    rollback()
    if top() != 5 { panic("error") }
    rollback()
    if top() != 3 { panic("error") }
}