2164번 - 카드2
이것 역시 가능한 풀이이며, 좋은 접근이라고 생각합니다.
알고리즘 문제 풀이의 즐거움 중 하나는 꼭 출제자가 의도한 대로 풀지 않더라도 제한 시간 안에 항상 올바르게 동작하는 코드라면 다 정답이 된다는 점이 아닐까 싶습니다. 현실에서 우리가 마주하게 되는 문제들에서 대개의 경우 "출제자의 의도" 같은 것이 없다는 것을 생각하면 오히려 이것이 문제 풀이의 본질에 가까울 수도 있겠다는 생각을 해봅니다.
이와 별개로, 시간복잡도의 개념을 정확히 이해하는 것이 중요합니다. 문제에서 요구하는 시간복잡도가 어떻게 되는지 알고, 내가 떠올린 풀이가 최악의 경우에도 시간 안에 돌아갈 지를 직접 코드를 짜보지 않고도 알 수 있어야 합니다.
예컨대, '리스트를 이용하여 문제에 주어진 방식 그대로 시뮬레이션 한다면 리스트의 맨 앞에서 원소를 지우는 연산이 O(N)이므로 총 시간복잡도가 O(N^2)이 되어서 시간 초과여서 안된다' 라고 생각하셨다면 훌륭합니다. 여기에서 큐라는 자료구조를 알고 있고, 큐의 맨 앞에서 원소를 지우는 연산은 리스트와 다르게 O(1)이므로 총 시간복잡도가 O(N)이어서 괜찮다는 사실까지 떠올릴 수 있으면 완벽합니다.
큐를 떠올리지 못해서 다른 풀이를 고민하기 시작했었다면 자료구조 공부를 더 하면 되는 것인데, 만약 큐를 떠올렸음에도 '큐를 이용해도 결과적으로 문제에서 시키는 그대로 막노동을 시키면 시간 초과가 될거야'라는 막연한 생각으로 이를 배제했다면 시간복잡도에 대한 이해가 필요한 상황입니다.
작성하신 풀이는 왜 시간 안에 동작하는지 또한 시간복잡도의 개념으로 정확히 파악할 수 있어야 합니다.
3번 줄의 while문의 loop가 한 번 실행될 때 시간복잡도는 O(N)입니다. 그런데 loop가 한 번 실행될 때 배열의 크기가 절반으로 줄기 때문에, loop가 실행되는 총 횟수는 O(log N)회입니다. 따라서 3번 줄 while문의 총 시간복잡도는 O(N log N)이고, 이후 13번 줄은 매우 작은 상수 시간에 동작할 것이므로 전체 시간복잡도 또한 O(N log N)입니다. N = 50만에서 O(N log N) 역시 가능한 풀이이므로 이 풀이 또한 시간 안에 동작합니다.
놀랍게도, 시간복잡도만 따져보면 이른바 '막노동'을 시키는 큐를 이용한 풀이가 더 빠릅니다! 실제로 구현을 했을 때 어느 풀이가 정확히 몇 ms가 걸리는지는 너무나도 많은 변수가 있기에 작성하신 풀이가 더 빠르게 동작할 가능성도 배제할 수는 없겠지만, 중요한 것은 시간복잡도를 정확히 이해하지 못한 상황에서 생각하는 '이 풀이는 수학적으로 엘레강스해서 빠르고 이 풀이는 막노동이라서 느릴 것이다'라는 감이 부정확할 수도 있다는 사실을 인지하는 것입니다.
좋은 답변 감사합니다 자료구조와 시간복잡도에 관해서 스스로 공부해보겠습니다!
댓글을 작성하려면 로그인해야 합니다.
dbstjr3377 1년 전
자료구조에 대해 더 알아보도록 유도하는 문제인지 몰랐음
뭔가 컴퓨터한테 막노동시키지 말고 수학적인 수식을 사용해서 풀라는게 문제 의도인줄 알아서
리스트 원소 갯수를 계속 2로 나누는 식으로 푸니까 시간초과는 안됐는데 이렇게 푸는게 아니었나 싶은 생각이 들기도 하네요 키키