프로.입문.최댓값 만들기

1. 2중 for문 

 

코딩테스트에서는 대체로 이쪽의 효율이 좋다. (성능적으로 가볍다)

int solution(vector<int> numbers) {
    int answer = -1;
    size_t n = numbers.size();
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            if (answer < numbers[i] * numbers[j])
                answer = numbers[i] * numbers[j];
        }
    }

    return answer;
}

 

2. next_permutation()를 이용한 조합

 

잘못한 부분

1. visit 을 정렬하지 않음.

2. combi를 초기화하지 않음.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> numbers) {
    int answer = 0;
    size_t n = numbers.size();
    
    //1. 조합 구하기 nC2
    vector<int> visit(n, 0);
    visit[0] = 1, visit[1] = 1;

    sort(visit.begin(), visit.end());

    do
    {
        vector<int> combi;
        for (int i = 0; i < n; ++i)
        {
            if (1 == visit[i])
            {
                combi.push_back(numbers[i]);
            }
        }

        if (answer < combi[0] * combi[1])
            answer = combi[0] * combi[1];

    } while (next_permutation(visit.begin(), visit.end()));
    
     
    //2. 조합의 곱 중 최댓값 반환하기.
    return answer;
}

 

3. 그냥 직관적으로

 

정렬하여 제일 큰수와 그 다음수 곱하기.

 

오름차순.

answer = numbers[numbers.size()-2] * numbers[numbers.size()-1];

내림차순.

int solution(vector<int> numbers) {
    sort(numbers.begin(),numbers.end(),greater<int>());
    return numbers[0]*numbers[1];
}

 

시간복잡도 

1. 2: O(N²)

3. O(nlogn)