문제
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.
간단하게 두 개의 배열을 비교하는 문제
일단 무식하게 풀어보자.
두개의 배열을 비교하는 문제라고 생각했기 때문에 이중포문을 작성하였다.
function solution(participant, completion) {
var answer = '';
//무식하게 풀기
for(var i = 0; i < completion.length; i++){
for(var j = 0; j < participant.length; j++){
if(participant[j] == completion[i]){
participant[j] =''
completion[i] = ''
break;
}
}
}
//배열을 string으로
answer = participant.join('');
return answer;
}실수한부분
- 시간복잡도를 생각하지 않았다.
- Object prototype Join 함수에 대한 성능을 생각하지 않았다.
문제의 값은 다 맞았지만 가장 중요한 시간복잡도에서 효율성을 생각하지 못하여 문제를 100점 만점에 50점만 맞게 되었다.
알고리즘
알고리즘 시간복잡도는 흔히 알고리즘 문제를 풀때 가장 중요한 항목이다. 알고리즘 문제를 풀때에는 이 시간복잡도를 아직 생각해서 풀기에는 미숙하다.
빅오 표기법
-
O(1) : 입력 자료의 수(n)에 관계없이 일정한 실행 시간을 갖는 알고리즘(Constant Time) - 예시 : 배열에서 특정 인덱스 찾기, 해시테이블 추가
-
O(log n) : 초반엔 빠르지만 후반부 갈수록 시간이 증가함 - 예시 : 이진 탐색
-
O(n) : 입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다.(linear) - 예시 : 연결 리스트 순회, 최대값찾기
-
O(n log n) : 선형 로그형, 데이터의 수가 2배로 늘 때, 연산횟수가 2배 조금 넘게 증가한다. - 예시 : 퀵 정렬, 병합정렬 등
-
O(n^2) : 주로 2중 for loop를 사용하여 조합가능한 모든 쌍을 대상으로 하는 경우가 전형적(quadratic) - 예시 : 버블 정렬,삽입 정렬
-
O(n^3) : 3차형(cubic)
-
O(2^n) : 지수형 빅오, '지수적증가'는 무서운 연산횟수 증가를 야기한다. 예시 :피보나치수열
-
O(c^n) : 최악의 시간 복잡도 - exponential - 예시 : recursion
-
O(n!) : 계승(factorial)
내가 위 알고리즘을 풀었던 시간복잡도는 이중포문의 O(n^2)으로 값의 수가 늘어날수록 걸리는 시간은 n^2이상으로 늘어난다.
인터넷에서 찾아본 해답
1~2시간동안 내가 못푼 문제라면 인터넷에 찾아서 코드를 비교하고 내것으로 만든다.
function anwser_2(participant, completion) {
var answer = '';
participant.sort();
completion.sort();
for(var i = 0; i < participant.length; i++){
if(participant[i] != completion[i]){
return participant[i]
}
}
}위 코드는 정렬 후 다시 비교하는 코드이다.
자바스크립트의 내장 sort함수를써서 해결하였다.
기본적으로 자바스크립트의 내장 sort는 ASCII 문자 순서로 정렬되어 숫자의 크기대로 나오지 않고 첫번째 문자와 두번째 문자 각각의 정렬로 처리된다.
자바스크립트의 sort함수
- compareFunction
이 함수를 사용하지 않으면 인자값이 숫자라 하더라도 문자열로 인식하여 정렬한다.
자바스크립트의 sort함수는 브라우저 마다 다르게 동작한다.
- V8: Quicksort or Insertion Sort (for smaller arrays)
- Firefox: Merge sort
- Safari: Quicksort, Merge Sort, or Selection Sort (depending on the type of array)
즉 아래의 코드의 시간복잡도는 O(n log n) 이고,
participant.sort();
completion.sort();
아래의 시간복잡도는 O(n) 이다.
for(var i = 0; i < participant.length; i++){
if(participant[i] != completion[i]){
return participant[i]
}
}결론
문제자체는 어렵지 않았지만 자바스크립트의 sort 내장함수에 대해서 좀 더 알수 있었고, 시간복잡도에 대해서 알수 있었던 문제였다.
