오늘 할 일
- (완료) 알고리즘 발표할 문제 풀기
- (완료) 발표할 PPT 만들기
1. 어떤 문제가 있었는지
햄버거 만들기 문제. 시간 초과가 떠버렸다. 😧 실행중단은 오래걸려서 내가 실행중지함.
2. 내가 시도해본 것들(삽질)
제한사항 중 매개변수의 값이 1,000,000이라면 반복문이 1,000,000번 돌아야해서 시간복잡도가 올라가게되는데 이래서 시간초과로 결과가 나온 듯했다.
1) 혹시 정규표현식을 사용하면 뭔가 다를까?
function solution (arr) {
//arr 배열 => 문자 변경
let changeArr = arr.join("");
//"1231"을 먼저 찾아서 빼내기
let answer = 0;
for(let i = 0; i<changeArr.length; i++) { //0~8 : 9번 반복
if(changeArr.includes(/1231/g)){ //true
changeArr = changeArr.replace(/1231/g,"")
answer++
}
}기존에 있던 "1231" 대신 정규표현식/1231/g로만 바꿔봤는데 typeError가 떴다.
알고보니 includes메소드는 문자열이 아닌 정규표현식과 함께면 에러가 뜬다고 한다.
2) 그럼 일단 for문을 먼저 사용하지 않도록 노력해봤다. 그럴려면 배열을 돌아가면서 확인해야하니 결국 map, foreach와 같은 메소드가 필요했다. 일단 map을 사용하는데에 있어 객체는 array이기에 처음 string으로 변경했던거를 그냥 배열인 상태로 뒀다.
반복문을 안쓰려고 했던건데 arr를 문자열로 안바꾸면 연속으로 1231이 있다는 알수가없다..결국 기존 코드에서 arr를 string으로 바꾸는 곳에서 map을 썼다. 대체 그게 무슨 소용인가!
그러던 중 발견한 replace에 대한 시간복잡도 포스팅!
https://programmer-may.tistory.com/154
문자열에 대한 반복문은 생각보다 성능 저하를 야기한다는걸 알았다. 변수와 상수, 불변하다는 것과 불변하지 않다는 점을 이해하고 있어 성능 저하에 관한 사항을 이해할 수 있었다.
3) 다시 문제를 이해해보자. arr에 연속으로 1,2,3,1이 나오면 팝! 하고 꺼내면서 새로운 배열에 1231을 넣어 그 배열의 길이를 구하면 답이 나오지 않을까..?
let answer = [];
function solution(arr) {
//Array.prototype.map()
turn(arr);
return answer.length;
}
function turn(arr) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === 1) {
if (arr[i + 1] === 2) {
if (arr[i + 2] === 3) {
if (arr[i + 3] === 1) {
answer.push("1231");
delete arr[i]
delete arr[i + 1]
delete arr[i + 2]
delete arr[i + 3]
arr.filter((item) => item !== null && item !== undefined && item !== '');
console.log(arr)
turn(arr);
}
}
}
}
}
}이건 콜백지옥이 아니라 조건문 지옥이다...
배열을 돌면서 배열의 차례대로 1,2,3,1이라면 answer에 1231을 푸쉬해서 넣고, 기존 arr에서 1,2,3,1이 들어있는 요소들을 지운다. 그리고 arr에 empty로 남아있는 부분을 지운다..! 그리고 다시1231이 없을때까지 재귀함수를 돌린다..라는게 내 목적이었다. 근데 일단 문제는 empty되어있는게 없어지지않는다. 그렇다면 백만인 배열을 계속 돈다는 말인데 시간복잡도...해결되지 않을거같아.
어제 밤부터 잡고 있던걸 이제 놓아줄때가 된거같아. 다른 사람의 코드를 보았다.
function solution(ingredient) {
let count = 0;
for (let i = 0; i < ingredient.length; i++) {
if (ingredient.slice(i, i + 4).join('') === '1231') {
count++;
ingredient.splice(i, 4);
i -= 3;
}
}
return count;
}... 도랐다. 미쳤다. 찢었다. 빼애애앰...!
입력받은 배열의 길이만큼 반복문을 돌려주는데
만약 배열의 i부터 i+3만큼 자른걸 join하여 붙여준게 1231이라면
count++해주고, 배열인덱스 i에서 부터 4개를 제거해준다.
그리고 제거해준만큼 i를 -3해준다..! 빼애애애애애애애애애애애애앰~💥💥💥💥💥
