4월 3주차 알고리즘 문제 - 더 적은 연산으로 문제 해결하기, 사용중인 저장 공간을 재활용

목차

주어진 조건을 더 적은 연산으로 해결하기
이미 사용중인 메모리의 저장 공간을 활용한 문제 해결

주어진 조건을 더 적은 연산으로 해결하기

문제 링크
내 풀이
문제 요약
- Strong Pair는 $|(x - y)| \leq min(x, y)$를 만족하는 pair이다.
풀이 요약
- 기존 풀이
  - if (abs(x - y) <= min(x, y))
- 개선 풀이
  - if y <= 2 * x

이미 사용중인 메모리의 저장 공간을 활용한 문제 해결

문제 링크
내 풀이
문제 요약
- list에서 가장 작은 수의 index를 찾는다. 이 때 같은 수가 여러개라면 가장 작은 index를 찾는다.
- 해당 값을 결과 값에 더하고, 좌우의 값을 visited로 만든다.
풀이 요약
- 기존 풀이
  - heap을 이용해서 가장 작은 수를 찾는다.
  - 좌우의 값을 확인한 뒤 이를 heap에서 제거한다.
  - 실제로 추가/제거하는 연산이 많아진다.
- 개선 풀이
  - 연산 완료 및 visited 처리된 index의 값을 -1로 변경한다.
  - heap이 아니라 sort한 이후에 visit을 이용해 처리한다.

2024-04-15