2021 카카오 채용연계형 인턴십 - 표 편집

이서현·2021년 8월 9일
0

Algorithm

목록 보기
73/76
post-thumbnail

08.09에 푼 문제입니다.🌷
표 편집

첫번째 풀이

정확도는 모두 통과했지만 효율성에서 모두 통과하지 못했다😂

function solution(n, k, cmd) {
    var answer = '';
    let stack = []
    for(let i=0 ;i< n;i++) stack.push(i)
    let del = []
    for(let c of cmd){
        if(c[0]==='U'){
            let num = parseInt(c.split(' ')[1])
            k-=num
        }
        else if(c[0]==='D'){
            let num = parseInt(c.split(' ')[1])
            k+=num
        }
        else if(c[0]==='C'){
            del.push(stack[k])
            stack.splice(k,1)
            if(k===stack.length) k--
        }
        else if(c[0]==='Z'){
            let delnum = del.pop()
            let inx = stack.findIndex(i=>i>delnum)
            if(inx===-1) {
                stack.push(delnum)
                inx=stack.length-1
            }
            else stack.splice(inx,0,delnum)
            
            if(k>=inx) k++
        }
    }
    
    for(let i=0;i<n;i++){
        if(stack.includes(i)) answer+='O'
        else answer+='X'
    }
    return answer;
}

두번째 풀이

다른 분의 풀이법을 참고해서 풀었다.
연결 리스트를 활용해서 해결해야 하는 문제이다.

U일 경우

위로 올라가야 하므로 연결리스트에서 앞에 있는 노드를 타고 올라가면 된다.

D 일 경우

U와 반대로 뒤에 있는 노드를 타고 내려가면 된다.

C 일 경우

[삭제된 노드, 삭제된 노드의 의 노드, 삭제된 노드의 의 노드]를 stack에 저장한다.

삭제된 노드 : 4
삭제된 노드 앞의 노드 : 3
삭제된 노드 뒤의 노드 : 5

삭제할 노드가 마지막 노드일 때
바로 앞의 노드에서 리스트가 끝나도록 하고 k는 앞에 있는 노드를 가리키게 한다.

[5,7] - [6,-1] k=7
-> [5,-1] / [6,-1] k=6

삭제할 노드가 마지막이 아닐 경우
앞에 노드를 뒤에 있는 노드에 붙여주면 된다.

[2,4] - [3,5] - [4,6] k=4
-> [2,5] -([3,5])- [3,6]
-> [2,5] - [3,6]

Z 일 경우

stack을 pop 한다.
삭제된 노드를 이전에 연결되었던 노드와 다시 연결한다.

삭제된 노드 : 4
삭제된 노드 앞의 노드 : 3
삭제된 노드 뒤의 노드 : 5

[2,5] - [3,6]
-> [2,4] - [4,6]
-> [2,4] - [3,5] - [4,6]

코드

function solution(n, k, cmd) {
    let list = Array.from({length:n},(v,i)=>[i-1,i+1])
    const anslist = Array(n).fill(true)
    list[n-1][1]=-1
    let stack = []
    cmd.map(command=>{
        command = command.split(' ')
        if(command[0]==='U'){
            for(let i=0;i<command[1];i++) k=list[k][0]
        }
        else if(command[0]==='D'){
            for(let i=0;i<command[1];i++) k=list[k][1]
        }
        
        else if(command[0]==='C'){
            const [pre,next] = list[k]
            stack.push([k,pre,next])
            anslist[k]=false
            if(next===-1){
                if(pre!==-1){
                    list[pre][1]=next
                }
                k=pre
            }
            else{
                if(next!==-1) list[next][0] = pre
                if(pre!==-1) list[pre][1] = next
                
                k=next
            }
            
        }
        else if(command[0]==='Z'){
            const [re,pre,next] = stack.pop()
            if(pre!==-1) list[pre][1]=re
            if(next!==-1) list[next][0]=re
            anslist[re]=true
        }
    })
    var answer = '';
    for(let i=0;i<n;i++){
        if(anslist[i]) answer+='O'
        else answer+='X'
    }
    return answer;
}
profile
안녕하세요. 이서현입니다( ღ'ᴗ'ღ )

0개의 댓글