- 문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한 사항
- phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
- 문제 풀이
먼저 무식한 방법으로 풀어보면,
같은 전화번호를 제외한 나머지를 1:1로 대응시켜 같은지 아닌지 판단한다.
이 방법은 풀리기는 하지만 BigO(n^2) 으로 느리다.
다음으로는 정렬하여 비교하는 방법이다.
[119
, 97674223
, 1195524421
]
이 경우에는 정렬하면, [119, 1195524421, 97674223] 이 되며
(첫번째, 두번째), (두번째, 세번째) 비교해 나갔을 때 같은 번호가 있다 [119, 1195524421]
따라서, 접두어가 같은 것이 있는지 찾으려면 정렬하여 순서대로 비교하면 된다.
시간복잡도는 개선된 BigO(n log n) 이다.
사실 더 좋은 방법이 있을 수도 있을 거 같은데 떠오르지가 않는다.
다음에 다시 한번 풀어봐야겠다.
Source Code: Phonenumber_list.cpp
번호를 스트링이 아니라 수로 접근해보면
정럴한다음
앞 숫자로 뒤에들 숫자를 나누면서하면
N(n/2) 정도될듯
가장 빠른 정렬법을 쓴다 해도 이미 BigO(n log n) 이라 BigO(n / 2)는 힘들거 같은데..?
그런데 앞 숫자로 뒤에들 숫자를 나누면서 한다는 것은 어떻게 하는 거야?
[119, 97674223, 1195524421] 라면 정렬하면 [119, 1195524421, 97674223] 이고
119 / 1195524421로 나누는 건가 아니면 반대로 1195524421 / 119 하는 건가?
O(n log n) 이 왜 튀어나왔는지 궁금해서 댓글 달려고 하니 이미 댓글들을 달아 놓은 듯
보통 log n 을 가진다는 건 전체 length에서 절반을 잘라 나눠서 분할 정복할 때 나오는 속도고
n을 가진다는 건 선형, 즉 index 0 to length 까지를 탐색하는 거라서
O(n log n)을 가지려면 quick, merge sort 정도는 해야 나오는 건데 소스코드 보니 for문이 중첩되어 있고
그러면 뭘 하던 O(n^2) 입니다.
O (n log n)이라는 주장의 근거를 잘 적으시던지
아니면 소스코드의 알고리즘을 실제로 O (n log n)으로 수정하시던지 해야 할 듯
제대로 코드를 안 보신듯 하군요.. 첫번째 solution 함수는 말씀대로 O(n^2) 지만 두번째 solution 함수에 보시면 내장 함수인 sort 함수를 썼습니다
조금 더 정확히 얘기하면.. 두번째 solution 함수에서 n을 phonebook 배열 길이라고 보고 k를 phonebook 배열의 원소의 string 길이라고 했을 때 sort를 처음에 하고 for 중첩문을 쓰므로 O(n log n + n * k) 정도로 되겠네요
흥미롭네요.
그 내장 sort 함수의 복잡도는 상관 없습니다.
solution 함수 전체의 복잡도를 얘기한 것으로 파라미터로 넘어온 vector phoneBook의 search strategy를 얘기한 것입니다.
int size = phoneBook.size();
for(int i = 0; i < (size – 1); ++i)
{
…
여기에서의 중첩된 for문은 대학 학부생에게 물어봐도 O(n^2)으로 판단할 수 있는데
제가 댓글 단 것 처럼 O(log n)이 나오려면 binary search가 들어간 quick, merge sort 정도가 나와줘야 합니다.
하지만 그 부분이 코드 상에 없기 때문에 O(n^2) 이라고 한 겁니다.
solution 함수의 전체 복잡도를 얘기하면서 sort 함수의 복잡도가 상관 없다는 말은 이해 할 수가 없네요. 정렬을 하지 않는다면 모를까 정렬을 한다면 그 비용은 당연히 무시할 수 없습니다. 내장함수의 성능은 개량된 quick sort 성능으로 알고 있습니다. 그리고 중첩문에서 O(n^2) 이라고 하셨는데 여기서 말하는 n은 phonebook size 입니다. k 는 phonebook size 가 아니라 phonebook의 원소 중 하나인 string의 길이가 되구요. 서로 다릅니다. 그래서 O(n log n + n * k) 라고 했었습니다. 만약에 첫번째 솔루션 함수 처럼 phonebook size인 n을 중첩해서 썼으면 n log n은 무시할 수 있으므로 Big-O(n^2) 이 맞겠지요. 여기서 k는 각 원소의 string 길이가 다르므로 가변적입니다..
그리고 말씀하신 BST (Binary Search Tree) 는 삽입, 삭제, 검색에서는 log(n)의 성능을 보여주고 quick, merge sort는 O(n log n) 성능을 보여줍니다. 다시 한번 찾아보세요.
음 제가 여기까지만 댓글을 달아보겠습니다.
누가 잘못 알고 있는지는 제 3자가 다시 판단해 주겠죠.
나중에 틀려서 부끄럽다고 글 내리지 않는 뻔뻔함 까지 있었으면 합니다.
물론 개인 블로그니까 글 내리고 아니고는 자유 의지겠지만요.
이 문제는 그렇다 치고 알고리즘 공부 열심히 하시길 빌겠습니다.
조금 과열된 감이 있네요..
감사합니다. FEEL 님도 알고리즘 공부 열심히 하시길 바랍니다.
일단 과열된 것에 대해서는 사과 말씀 드리겠습니다.
저도 무시하고 가면 그만이긴 한데 다시 생각해 보니까 건전한 의견 교환의 방향으로 가는게 서로에게 더 좋다는 생각이어서요.
그리고 제가 한가지 간과한 사실이 있는데… k가 상대적으로 n 보다 매우 작은 숫자인데다, 조건이 걸려 있어서 그 부분을 캐치 못한 점이 있습니다. (문제를 제대로 안본 제 잘못이겠죠)
O(n log n + n * k)에서 사실 n과 k의 범위가 정해지지 않았다면 O(n^2)으로 수렴할겁니다. 그렇기 때문에 제가 내장 sort 함수의 결과는 상관 없다고 한 거였습니다. n과 k의 길이가 서로 다른건 사실 Big-O에선 중요하지 않고 k가 가변적인 것도 상관 없긴 합니다. 그런데 n이 1,000,000인데 비해 상대적으로 k는 20 정도니까 무시할만하다고 여겨집니다. 그러면 상대적으로 n log n이 더 크므로 결국 O(n log n)이 맞는 것 같습니다. 범위가 정해져 있으므로 엄밀히 따지만 맞을 수도 있고 아닐 수도 있다겠죠.
Big-O의 n은 범위가 정해지지 않는 복잡도를 표기하는 방법이고, n이 <1,000,000 이하라는 조건에서는 내장 sort 함수도 최악의 경우 n^2 일 수도 있으므로, 사실 범위가 정해져 있는 알고리즘의 복잡도는 Big-O 표기법이 무의미할 수도 있다는 의견도 같이 드립니다.
조건을 안보고 코드만 보고 얘기했던 부분은 다시 한번 사과드립니다.
오히려 제가 더 배우고 가네요.
저야말로 FEEL님의 의도를 처음에 잘 못 이해해서 열을 냈었네요.. 죄송합니다.
말씀하신 대로 논점이 O(n log n) 이 아닌 k 였네요
k가 전화번호 문자열의 길이라 하였을 때 안 좋을 경우,
전화번호부 개수인 n의 길이보다 긴 전화번호 들이 나열될 수 도 있습니다.
즉, n * k가 n * n 보다 커지게 되는 거죠.
그런 경우는 말씀하신 대로 오히려 O(n log n)은 무시하고도 남을 O(n^2) 되겠죠
FEEL님은 이러한 의견을 피력하신 것이고, 저는 전화번호 개수와 전화번호 문자열을
따로 봐서 하는게 맞다고 의견을 피력한게 되는 것이네요.
누가 맞다기 보다는 견해 차이인거 같습니다.
확실한것은, 실제 성능에 있어서는 k와 n에 따라
O(n^2)보다 안 좋을 수도 있고 O(n log n) 정도 일 수도 있다는 것일 겁니다.
FEEL님의 다른 견해를 접하니 제 생각이 더 넓어지는 것 같습니다. 감사합니다.