뒤에 있는 큰 수 찾기

현재 인덱스보다 큰 인 덱스 중 원소가 더 큰 것을 새로운 배열에 담고, 없다면 -1을 담는 방식이다.

1. 비교를 한 뒤 마지막에 -1을 담는다
2. 처음에 -1을 담아두고 나중에 값을 바꾼다

2.의 방법은 굳이 일을 한번 더 하기 때문에 비효율적이ㅣ므로 1의 방법을 사용하면 될 것같다

나의 풀이

풀이 과정

분명 아무 문제 없는 방법이라고 생각했는데 이중 반복문이라서 느렸던것같다.

i와 i의 뒷큰수 사이의 숫자는 모두 i이하, 뒷큰수 미만이므로 한번에 처리해야할 것같다.
그럼 for문 대신 while문을 사용해보자

조금 고쳤는데 null이 들어가있다. 초기값을 설정해야하는것같다

초기값을 -1로 주고, 속도도 빨라졌는데 일부 구간에서 잘못된 값을 내놓고, 여전히 시간 초과를 하는 경우도 있다. 다시 바꿔보자

작은수가 연속으로 두번 있는 경우에 오류가 생긴다.
이 외에도 여러가지 개선을 했으나, 결과값을 제대로 못내놓거나 너무 느리다고 떴다. 이중 반복문을 없애거나 더 효율적으라 만들지않으면 답이 없을 것 같다.

lastBig이라고 쓰는게 가독성이 좋아보여서 그렇게 했는데 오히려 값이 안바뀌어서 더 나쁜 선택이 되었다.

나의 코드

function sol01(numbers) {
  const nl = numbers.length;
  const newNum = new Array(nl).fill(-1);

  for (let i = 0; i < nl - 1; i++) {
    for (let j = i + 1; j < nl; j++) {
      if (numbers[i] < numbers[j]) {
        newNum[i] = numbers[j];
        break;
      }
    }
  }
  return newNum;
}

function sol02(numbers) {
  const nl = numbers.length;
  const newNum = new Array(nl).fill(-1);
  const big = [];

  for (let i = 0; i < nl; i++) {
    while (big.length > 0 && numbers[big[big.length - 1]] < numbers[i]) {
      newNum[big.pop()] = numbers[i];
    }
    big.push(i);
  }

  return newNum;
}

sol01은 이해가 쉬운 코드이지만 속도에서 탈락
sol02는 속도는 좋지만 이해가 상대적으로 어렵다.

다른 사람의 풀이

function solution(numbers) {
    var answer = Array(numbers.length);
    var check = [0];
    for (var i = 1; i < numbers.length; i++) {
        while (check.length && numbers[check[check.length - 1]] < numbers[i]) {
            answer[check.pop()] = numbers[i];
        }
        check.push(i);
    }
    while (check.length) {
        answer[check.pop()] = -1;
    }
    return answer;
}

나와 비슷하게 풀었지만 초기값을 주지 않고 필요에 따라서 -1을 넣고 있다. 나도 처음에는 이런 방법을 쓰려했지만 예외 사항 처리등의 편리 때문에 지금의 방식으로 바뀌었다. 과연 속도에서는 어느게 더 나을지 비교해보고 싶어졌다.

속도비교

랜덤 배열을 만드는 함수

function makeArray() {
  // 배열의 길이 랜덤 생성
  // const length = Math.floor(Math.random() * 99997) + 4;
  length = 10000;

  // 배열 생성 + 범위
  const nums = Array.from(
    { length },
    () => Math.floor(Math.random() * 1000) + 1
  );

  return nums;
}

시간복잡도

sol01,02,10,11 : $O(N^2)$
sol20,21 : $O(N logN)$

길이 100배 증가

sol01은 최악의 경우 1000배 증가지만 그렇게는 되지 않았다

범위 100배 증가

속도에서 탈락했던 것을 제외하면 별다른 차이가 없다

표로 비교

한세트 (함수별로 1000번 반복)마다 새로운 랜덤 배열이 나오기 때문에 정확히 똑같은 비교라고 할 수 는 없지만 대략적인 비교는 가능하다.

배운점

1. 알고리즘을 잘 짰다면 미세한 차이는 입력 길이에 따른 처리 결과에 큰 영향을 미치지 않는다. 하지만 배율로 따졌을 경우이기 때문에 불필요한 행위는 최대한 줄이는 것이 좋다.

2. 같은 이중 반복문이라도 최적화를 얼마나 했느냐에 따라 속도 차이가 커진다. 특히, 지속적으로 불러와야하는 대상은 짧은 크기를 가지도록 유도하는 것이 좋다.