프로그래머스 12924

박종대·2022년 9월 29일
0

Algorithm

목록 보기
3/3

해당 문제는 얻어 맞춘 느낌이 강하다. 다시 한 번 복습해야 할 것 같다. 다음은 얻어 맞춘 느낌의 풀이이다.

function solution(n) {
  let left = 1;
  let right = n;
  let result = 1;

  while (left < right) {
    let sum = 0;
    for (let i = left; i <= right; i++) {
      sum += i;
      if (sum > n) {
        left++;
        break;
      } else if (sum === n) {
        result++;
        left++;
        break;
      }
    }
  }

  return result;
}

일단 문제의 예시를 보면 양쪽 끝이 변하는 것을 확인할 수 있었다. 그래서 투포인터 알고리즘을 바로 떠올릴 수 있었다.
오랜만에 문제를 풀어서 그런지 right를 잘못 설정했다. 그런데도 문제없이 통과가 되었다.
해당 알고리즘은 right를 고정시켜놓고 left만 변화시키면서 test 하기 때문에 right 변수가 사실상 의미가 없다. 그래서 right를 n으로 바꿔봤다.

function solution(n) {
  let left = 1;
  let result = 1;

  while (left < n) {
    let sum = 0;
    for (let i = left; i <= n; i++) {
      sum += i;
      if (sum > n) {
        left++;
        break;
      } else if (sum === n) {
        result++;
        left++;
        break;
      }
    }
  }

  return result;
}

right를 n으로 바꿨을 뿐인데 효율성에서 통과하지 못한다. 아무리 생각해봐도 무슨 이유인지 모르겠다.. 다른 분들에게 여쭤봐도 모르신다. 아시는 분은 꼭 댓글 달아주시길 바랍니다.

어찌됐던 투포인터 알고리즘이라고 했지만 끼워맞춘 쌩구현 알고리즘으로 푼 것 같은 느낌이라 정석대로 다시 풀었다.

function solution(n) {
  let left = 1;
  let right = 1;
  let sum = 1;
  let result = 0;

  while (right <= n) {
    if (sum < n) {
      // 합이 n보다 작으면 늘려야해
      right++;
      sum += right;
    } else if (sum > n) {
      // 합이 n보다 크면 줄여야 해
      sum -= left;
      left++;
    } else {
      // 합이 같으면
      result++;
      right++;
      sum += right;
    }
  }

  return result;
}

이제 좀 제대로 된 풀이가 된 것 같다.

기억 할 점

  • 예시에서 양 끝을 바꿔가며 케이스를 구한다 -> 투포인터 느낌
  • left와 right가 같은 값에서, 혹은 양 끝 값에서 출발할 수 있다는 점 기억.
  • 매개변수에 접근하는 비용이 큰 것인가? 아직 의문으로 남아있음.
profile
Frontend Developer

0개의 댓글