송아지를 잡자

성공여부

걸린시간(분)

정리

완료

문제출처

제로베이스

생성 일시

Apr 18, 2025 02:23 PM

1️⃣ 문제

2️⃣ 문제 해결 전략

deque가 아닌 stack으로만 관리

⇒ 현재 time의 위치와 다음 time의 위치를 같은 deque로 관리하면 shift로 연산을 써서 시간초과

⇒ 두개의 위치를 따로 구분. 즉, 스택을 두개 만들어서 관리하면 pop연산으로 시간초과 나지 않음

3️⃣ 코드 및 설명

내 코드

shift 연산을 써서 효율성 테스트에서 통과x


function solution(s, e) {
  var answer = 0;
  var deque = [s];
  var cowMove = 1;

  while (deque.length) {
    var count = deque.length;
    if (e > 200000) {
      return -1;
    }
    var newValues = new Set([]);
    for (let i = 0; i < count; i++) {
      var de = deque.shift(); //
      if (de === e) {
        return answer;
      }
      for (var value of [de - 1, de + 1, de * 2]) {
        if (!newValues.has(value)) {
          deque.push(value);
          newValues.add(value);
        }
      }
    }
    answer += 1;
    e += cowMove;
    cowMove += 1;
  }
  return answer;
}
solution(10, 3);

모범 코드

pop연산으로 효율성 테스트까지 통과


function solution(s, e) {
  const MAX = 200000;
  var answer = 0;
  var stack = [s];
  var cowMove = 1;

  while (stack.length) {
    var count = stack.length;
    if (e > MAX) {
      return -1;
    }
    var setq = new Set([]);
    for (let i = 0; i < count; i++) {
      var de = stack.pop();
      if (de === e) {
        return answer;
      }
      for (var value of [de - 1, de + 1, de * 2]) {
        if (value > 0 && value <= MAX) {
          setq.add(value);
        }
      }
    }
    stack = Array.from(setq);
    answer += 1;
    e += cowMove;
    cowMove += 1;
  }
  return answer;
}
solution(10, 3);

4️⃣ 시간복잡도

O(3^t)