카드 뭉치
방법은 두개다.
- cards1,2에 있는 요소들에게 goal에 기반한 key 또는 value값을 주어서 순서가 뒤바뀌었는지 확인하기
- 그냥 하나하나 순서대로하기
앞의 방법은 왠지 이상한 예외사항이 많을 것같으므로 두번째 방법으로 하자.
나의 풀이
function sol01(cards1, cards2, goal) {
var canDraw = 'Yes';
let i = 0
while (i < goal.length) {
if (goal[i] === cards1[0]){
cards1.shift()
} else if (goal[i] === cards2[0]){
cards2.shift()
} else {
canDraw = 'No'
return canDraw
}
i++
}
return canDraw;
}처음에는 canDraw가 true인 경우에 무한 루프를 돌게 만들었는데 이렇게하면 카드가 다 떨어진 경우 = Yes를 리턴해야할 경우에 무란루프에 빠졌던것이다.
cards[0]도 goal[i]도 빈값이기 때문
function sol02(cards1, cards2, goal) {
var canDraw = 'Yes';
let i = 0
while (i < goal.length) {
if (goal.length === 0 ) {
break
}
if (goal[i] === cards1[0]){
cards1.shift()
} else if (goal[i] === cards2[0]){
cards2.shift()
} else {
canDraw = 'No'
return canDraw
}
i++
}
return canDraw;
}예외 사항을 추가한 경우이다.
대부분의 경우에서는 0.01ms가 증가했고 반대로 길게 걸리던 경우에는 0.12ms정도 감소했다.
큰 데이터를 처리할때 유리하게 짜야하므로 sol02가 더 좋은 솔루션일것같다.
다른 사람의 풀이
function sol11(cards1, cards2, goal) {
let j = 0;
let k = 0;
for(let i=0;i<goal.length;i++){
if(goal[i] == cards1[j]) j++;
else if(goal[i] == cards2[k]) k++;
else return "No"
}
return "Yes";
}shift를 쓰지 않고 다음 칸으로 나아가는 방식이다.
어느게 더 빠를지 궁금하다.
아래는 while문으로 고친 것이다.
function sol12(cards1, cards2, goal) {
let j = 0;
let k = 0;
let i = 0;
while (i < goal.length){
if(goal[i] == cards1[j]) j++;
else if(goal[i] == cards2[k]) k++;
else return "No"
i++
}
return "Yes";
}속도 비교(실패)
반복 횟수 100회 증가
부하가 낮은 상태에서는 의미가 없는 차이를 보인다.
그런데 이거 이상한데?...
트러블 슈팅 - 얕은 복사
시험삼아서
console.log(sol01(q, w, e));
console.log(sol01(q2, w2, e2));와
sol01(q, w, e);
console.log(sol01(q, w, e));
console.log(sol01(q2, w2, e2));를 비교한 것이다.
그렇다 원본 배열의 값을 없애는 과정이 있기 때문에 제대로 된 반복 측정이 되지 않았던 것이다.
function sol01(q, w, e) {
const cards1 = q;
const cards2 = w;
const goal = e;코드를 수정했지만 같은 문제가 발생했다.
자바스크립트에서 배열같은 객체를 복사하면 객체의 값이 아닌 주소값을 복사하는 얕은 복사가 일어나는데 이걸 망각했던 것이다.
const cards1 = [...q];
const cards2 = [...w];
const goal = [...e];깊은 복사를 하여 문제를 해결하였다.
다시 속도측정
반복 횟수 10배 증가
내가 짠게 느리다는거 말고는 아무런 특이 사항이 없는 결과다
입력값 길이 10배 증가
입력값이 큰 경우 arr.shift()가 느리다고 들었는데 이렇게까지 차이가 날줄은 몰랐다.
그리고 for문보다 while문이 더 빠른건 여전히 나타나는 현상인것같다.
영어 끝말잇기
까다롭게 하려면 얼마든지 까다롭게 할 수 있는 조건인데 양심적으로(?) 순서대로 주는것같다.
우선 words에서 중복 또는 끝말잇기가 안되는 곳을 찾고 n으로 그게 걸리는 곳을 찾으면 되겠다.
짜다보니 안된다.
그냥 순서대로 배열 만들면서 가야겠다.
나의 풀이
function sol0(n, words) {
const length = words.length
let banedIndex = -1
let i = 0
while ( i < length ) {
const word = words[i]
const index1 = words.indexOf(word)
const index2 = words.lastIndexOf(word)
if ( index1 !== index2 && index1 !== -1) {
banedIndex = index2
break;
}
i++
}
i = 1
while ( i < length ) {
const word1 = words[i-1]
const word2 = words[i]
if ( word1[word1.length - 1] !== word2[0] ) {
if ( banedIndex === -1) {
banedIndex = i
break;
} else if ( banedIndex > i) {
banedIndex = i-1
break;
}
}
i++
}
const banedPeople = (banedIndex)%n +1
banedIndex = Math.ceil((banedIndex+1)/n)
return [banedPeople,banedIndex]
}끝말 잇기가 끝나는 조건을 두개중 먼저 나오는 경우를 기준으로 계산한다.
다른 사람의 풀이
function sol1(n, words) {
var fail_i = -1;
for(var i = 1; i < words.length; i++){
var val = words[i];
// 전단계의 끝말과 현단계 첫말이 다를 경우
if(words[i-1].substring(words[i-1].length-1) != val.substring(0, 1)) {
fail_i = i;
break;
}
// indexOf 함수는 첫번째로 값이 맞는 인덱스만 반환하므로
// 현재 인덱스와 맞지 않을 경우 중복된 값
if(words.indexOf(val) != i) {
fail_i = i;
break;
}
}
if(fail_i == -1) return [0,0];
var no = fail_i%n + 1;
var turn = Math.floor(fail_i/n) + 1;
return [no, turn];
}나랑 같은 논리인데 순서가 바뀌었고 더 간단하다.
특히 내가 첫번째 while문에서 복잡한 조건으로 쓴것을 짧은 코드로 구현했다.
function sol2(n, words) {
let answer = 0;
words.reduce((prev, now, idx) => {
answer = answer || ((words.slice(0, idx).indexOf(now) !== -1 || prev !== now[0]) ? idx : answer);
return now[now.length-1];
}, "")
return answer ? [answer%n+1, Math.floor(answer/n)+1] : [0,0];
}너무 압축이 되어서 읽기가 불편하다.
words.reduce((prev, now, idx) => {
answer = answer || ((words.slice(0, idx).indexOf(now) !== -1 || prev !== now[0]) ? idx : answer);
return now[now.length-1];
}, "").reduce((prev, now, idx) : 원래라면 누산기(acc)여야할 곳에 prev라는 이름의 변수를 넣었다.
즉, 삼항 연산자를 실행한 다음에 prev의 값을 now[now.length-1] 현재 문자의 마지막 글자로 만드는 것이다.
answer = answer || ((words.slice(0, idx).indexOf(now) !== -1 || prev !== now[0]) ? idx : answer)
- answer 가 falsy한 값인 경우
false,0,null,undefined,NaN,'' - 배열의 처음부터 현재까지, 현재 값과 중복인 값이 있는 경우
- 이전 글자의 마지막 글자가 현재 글자의 첫 글자와 같지 않은 경우
- 앞의 조건중 하나라도 참이면 answer = idx (갱신)
- 모두 거짓이라면 answer = answer (유지)
나와는 중복을 보는 기준이 반대다.
속도 비교
시간복잡도는 모두 똑같이 이다.
반복 횟수 100회 증가
증가율 자체는 비슷하고, 실행속도는 sol1 >(2배차이)> sol2 > sol0 이다.
words길이 10배증가
일부러 무한 끝말 잇기를 할 수 있게
words = ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] 로 설정하고 마지막의 executive를 executivh로 고쳤다.
그리고 이것을 10회 반복한 배열로 입력값을 증가시켰다.
고려하는 단계가 하나 더 있어서인지 sol2가 제일 많이 증가하였다.
그 다음 특이한 상항으로는 sol0,1은 유지가 되거나 오히려 빨라졌다는 점이다.
나의 코드 sol0이 sol1보다 구현이 조금 나빠서 그렇지 방법 자체는 나쁘지 않았던것같다.
공부하며 느낀 점
- 배열(= stack)의 길이가 길다면
.shift()로 배열의 길이를 줄이는데 걸리는 시간은, 긴 배열에서 특정index로 값을 찾는 것보다 훨씬 길다.- 배열의 마지막 값 제거 :
- 배열의 첫번째 값 제거 :
- 하나의 객체에 대해서 여러 함수에서 참조를 해야하고, 해당 함수의 안에서 객체의 내용을 변경한다면
깊은 복사를 사용해야지 오류를 막을 수 있다. - 다시 느끼지만 시간복잡도는 중요하지만 절대적이지는 않다.
참조한 페이지
