[2024] day 74. Leetcode 2485. Find the Pivot Integer

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 13일 (수)
Leetcode daily problem

https://leetcode.com/problems/find-the-pivot-integer/description/?envType=daily-question&envId=2024-03-13

Problem

양의 정수인 n이 주어질 때 1부터 n까지 일부 정수를 합한 갓과 같은 pivot 정수인 x를 찾는 것이다.
주어진 n에서의 피봇 정수가 없다면 -1를 반환하고, 피봇정수가 있다면 해당 정수를 반환한다.
(1과 x 사이의 모든 요소의 합은 x와 n 사이의 모든 요소의 합과 같을 때의
피벗 정수 x를 반환)
주어진 입력에 피벗 정수가 있다면 최대 하나의 피벗 인덱스가 있다.

예를 들어 n이 8로 주어질때 1부터 6까지의 합은 21 이고, 6에서 8까지의 합도 21이다. 두 값이 21로 같은 시점이 6이므로 n이 8일 때의 피봇 정수는 6이다.

Solution

math

여기서는 등차수열의 합 공식을 이용해서 문제를 해결한다.
1부터 n까지의 합을 구하는 공식은 n*(n+1)/2 이다.
이를 이용해서 1부터 n까지의 합을 구한다.

다음으로 피벗 정수 x를 기준으로 1에서 x까지의 합은 x(x+1)/2 이고,
x부터 n까지의 합은 (n-x+1)(n+x)/2 이다.

Code

Complexicity

시간 복잡도

공간 복잡도