본문 바로가기
알고리즘 문제/CodeJam

[Kickstart][2020][Round E] 1. Longest Arithmetic

by 햄과함께 2020. 8. 25.
반응형

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff47/00000000003bf4ed

 

Kick Start - Google’s Coding Competitions

Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all.

codingcompetitions.withgoogle.com


음수가 아닌 정수형 배열이 주어질 때, 최장 부분산수배열 길이를 구해라. 이때, 부분산수배열의 연속되는 원소의 차이는 서로 같다. ex) [1,3,5], [5,5,5]


배열을 처음부터 탐색하면서 이전 원소 차이를 diff 변수(arr[i-1] - arr[i-2])에 저장해둔다. 그리고 부분산수배열의 길이를 변수 cnt에 저장한다.

탐색중인 원소와 이전 원소의 차이(arr[i] - arr[i-1])가 diff 변수와 같다면 부분산수배열이 될 수 있으므로 cnt+1을해준다.

diff 변수와 다르다면 arr[i-1], arr[i] 부터 다시 부분산수배열이 가능한지 체크해가면서 cnt를 구해야 하므로 cnt = 2로 갱신해주고 위 알고리즘을 다시 진행한다. 이 때, 탐색하고 있는 i가 0이라면 arr[i-1]은 존재하지 않으므로 cnt는 1로 갱신한다. 이를 모든 배열을 탐색할 때까지 반복하고 탐색중에 나오는 cnt중 최대값이 정답이 된다.

 

시간복잡도는 O(N).


소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundE/Longest%20Arithmetic.cpp

반응형

태그

,

댓글0