[코딩연습] Largest Number At Least Twice of Others 가장 큰 숫자 찾기

LeetCode 문제 중 난이도 Easy인 Largest Number At Least Twice of Others이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

정수배열인 nums는 딱 하나의 가장 큰 값을 가지고 있다.

다른 모든 숫자들보다 두배이상 큰 가장 큰 수가 있다면 인덱스 값을 리턴하라. 그렇지 않으면 -1을 리턴한다.

가장 큰 값이 모든 값보다 두배 이상 큰지 보려면 두번째로 큰 값보다 두배 이상 큰지 확인하면 된다. 배열을 돌면서 가장 큰 값(largest)과 두번째로 큰 값(secondLargest)의 인덱스를 탐색한다.

맨 처음에 0,1을 넣고 nums[2]부터 돌면서 i가 largest보다도 큰 가장 큰 값이면 largest의 값을 secondLargest에 넣고 i의 값을 largest에 넣는다. largest보다는 크지 않지만 secondLargest보다 크면 secondLargest를 i로 바꿔준다. 마지막까지 배열을 탐색한 후 nums[secondLargest]*2≤를 만족하면 largest를 리턴하고 아니면 -1을 리턴한다.

class Solution {
    public int dominantIndex(int[] nums) {
        
        if(nums.length==1) return 0;
        
        //비교를 위해 첫 두 배열의 값을 넣어주고 시작
        int largest=0;
        int secondLargest=1;
        if(nums[0]<nums[1]){
            largest=1;
            secondLargest=0;
        }
        
        //nums[i]가 largest보다크면 바꾸고 largest보단안커도 secondLargest보다크면 바꿈
        for(int i=2 ; i<nums.length ; i++){
            if(nums[i]>nums[largest]){
                secondLargest=largest;
                largest=i;
            }else if(nums[i]>nums[secondLargest]) secondLargest=i;
            
        }
 
        //largest가 secondLargest*2 보다 크거나 같으면 인덱스값 반환,아니면 -1
        return nums[largest]>=nums[secondLargest]*2 ? largest : -1 ;
    }
}

마지막 리턴값의 A ? B : C 는 삼항연산자라고 부르고 A가 참이면 B를, A가 거짓이면 C를 반환한다.

배열을 한번 전체탐색하고 추가적인 메모리는 사용하지 않으므로 이 방법의 시간복잡도는 O(n), 공간복잡도는 O(1)이다.

문제 출처 링크 - https://leetcode.com/problems/largest-number-at-least-twice-of-others/