[Programmers] 입문) 최댓값 만들기 (1)

 

이번 문제는 2개의 수를 찾아야한다.

STL을 활용한다면 쉽게 할 수 있다고 생각했다.

 

애초에 최대값 2개를 곱하는 문제이니 정렬 후 마지막 수 2개를 곱하면 되는 문제였다.

 

단, 코드를 작성하면서도 정렬을 거치기 때문에 상당히 느릴 것을 예상했다.

 

using System;

public class Solution {
    public int solution(int[] numbers) {
        Array.Sort(numbers);
        return numbers[numbers.Length - 1] * numbers[numbers.Length - 2];
    }
}

결과는 역시 1ms를 넘겨버렸다.

아무래도 정렬을 거치기 때문에 어쩔수 없다고 생각한다.

 

다른 사람들이 푼 방식 중 가장 눈에 들어온 것은 이중 for문 방식이다.

 

using System;

public class Solution {
    public int solution(int[] numbers) {
        int answer = 0;
        for( int i = 0; i < numbers.Length-1; i++)
        {
            for ( int j = i + 1; j < numbers.Length; j++)
            {
                if ( numbers[i] * numbers[j] > answer)
                    answer = numbers[i] * numbers[j] ;
            }
        }
        return answer;
    }
}

분명 나쁜 방식은 아닌 것 같지만 여전히 for문을 2번쓰는 이유가 보이지 않는다.

어차피 한번 탐색에 2개의 값을 정하는 것이라면 굳이 이중 for문이 필요없어 보이기 때문이다.

 

그래서 다시한번 내방식대로 반복문을 작성해보았다.

 

using System;

public class Solution {
    public int solution(int[] numbers) {
        int max = 0;
        int second = 0;
        
        for( int k = 0; k < numbers.Length; k++){
            if (max <= numbers[k]) {
                second = max;
                max = numbers[k];
            }
            else if (second <= numbers[k]){
                second = numbers[k];
            }
        }
        
        return max * second;
    }
}

이 방법은 반복문 2번 대신 한번의 반복문에서 큰 값을 갱신할때마다 스택을 쌓듯 2번째 큰 값과 함께 값을 갱신하는 방법이다.

 

그렇게 크게 이중 for문과 차이를 보이지는 않는 것 같지만 전반적으로 0.01ms 정도 빠르고 특정 케이스는 되려 좀 느려진 것 같기도하다. (테스트 케이스 공개좀 해줬으면 좋겠다....)