[개발일지] - 838(연차)

(1).백준 21756번 지우개는 특이하게 홀수번째 값들을 다 날려버리고

다시 재배치된 상태에서 홀수번째를 다 날려서 최종 남은 숫자를 출력해야 하는 문제로

처음에는 queue에 담은 다음 무한반복하게 넣어주면서 지우고 통과하는 행동을 했는데

지워진 개수에 따라서 맨 앞으로 빠진 숫자의 삭제 여부가 결정되기 때문에 

새로 정렬 후 홀수번째가 모두 삭제되는 규칙과는 달라서 결국 배열을 덮어쓰는 방식으로 해야 했다.

 

값들을 0으로만 처리하고 값이 0이 아닌 개수를 새로운 순회마다 index 변수를 새로 관리해주면서 반복하는 방식도 생각해봤지만

지금 방식은 재할당을 계속 해주긴 하지만 시간복잡도로 생각하면 2n정도로 보이는데

전체 순회를 하면서 index를 카운팅하는 방식의 경우 n**2로 올라가기 떄문에 시간, 공간 복잡도에 따라 처리 방식이 결정되야 할 것 같다.

const input = 2
let arr = []

for(let i = 1 ; i <= input ; i++){
    arr.push(i)
}

while (arr.length > 1) {
    for(let i = 0 ; i < arr.length ; i++){
        if(i%2 == 0){
            arr[i] = 0
        }
    }
    arr = arr.filter(el => el != 0)
}

console.log(arr[0])