BOJ problem solving

#10989 - 수 정렬하기 3

counting sort라는, 다소 특수한 정렬 알고리즘을 언제 사용하는지 익힐 수 있었다.

counting sort

오름차순으로 어떤 수가 몇 번 등장하는지 센 후, 그 수만큼 배열에 넣어(혹은 출력해) 정렬한다.

장점

시간복잡도가 O(N)이다. 기존 배열을 한 번, count후 만든 배열을 한 번 순회하면 정렬이 끝이 난다.

단점

정렬하고자 하는 배열의 범위가 클수록 메모리 낭비가 심해진다. 예를 들어,

{0, 1, 2, 100000, 99, 80}

이 배열을 counting sort로 정렬하려면 {0~100000}의 배열이 필요하다. 낭비되는 공간이 심하게 많다. 다만, 거꾸로 말하면 범위가 작다면 가장 빠른 정렬 솔루션이 될 수 있다는 이야기다.

problem in my solution

counting sort의 단점은 메모리 낭비에 있기에, 메모리 절약이 중요한 이 문제에서 사용될 것이란 생각을 전혀 하지 못했다. 그러나 이 문제의 함정은 이곳에 있었다. 수의 범위를 매우 작게(0~10000) 제한함으로써, 오히려 counting sort를 사용하면 메모리가 절약되는 역설적인 상황을 부여한 것이다. 이 문제는 애초에 입력을 모두 배열에 넣으면 메모리가 초과된다. 0에서 10000까지의 counting배열만 만든 후 이 배열을 순회하여 출력해야 제한된 메모리를 초과하지 않는다.

what i learned

이제 counting sort라는 정렬 solution을 하나 더 사용할 수 있게 되었다. 정렬알고리즘들의 장/단점을 더 피부에 와닿게 체험할 수 있었다.

#1406 - 에디터

linked list라는, 어찌 보면 간단한 자료구조를 자유자재로 다룰 수 있는지 확인하는 문제

doubly linked list

각 노드의 다음 노드와, 이전 노드를 모두 연결한 링크드리스트

장점

노드에 접근, 또는 이동하는 시간복잡도가 O(N)이 아니라 O(1)이다.

단점

앞 뒤가 모두 연결되어있는 터라 null-pointer 처리가 까다롭고, 메모리 차지도 일반 링크드리스트보다 크다.

problem in my solution

null-pointer 처리 때문에 조건문이 과도하게 많이 사용되었고, 덕분에 O(1)의 시간복잡도를 가지고도 시간초과 오답이 나왔다.

what i learned

null-pointer 처리가 까다로운 상황이라면, 그 상황을 최대한 피할 수 있도록 자료구조를 구현하는게 중요하다고 느꼈다. 이번 경우에는, 맨 앞 노드를 지울 때나, 노드가 없을 때 삭제를 무시하는 부분이 링크드리스트의 head노드를 실제 원소로 처리했더니 복잡해졌다. head를 빈 더미 노드로 할당하고 처리하니, null-pointer 처리도 확연히 줄어 구현이 간편해졌고 조건문도 줄어 속도또한 향상되어 정답을 받을 수 있었다.