[코드업] 일곱 난쟁이 (C++)

일곱 난쟁이

 

문제

이 문제는 아홉 난쟁이들 중 키의 합이 100인 일곱 난쟁이들을 찾는 문제이다.

 

 

풀이

아홉 난쟁이들 중에서 키의 합에서 두 난쟁이의 키를 뺀 값이 100이 되는 두 난쟁이를 찾는 방법으로 풀이했다.

// 처음 풀이한 코드
#include <iostream>
#include<algorithm>
using namespace std;
// https://codeup.kr/problem.php?id=3008

int dwarfs[9] = { 0, }, sum = 0;
void Func() {
	for (int i = 0; i < 9; i++) {
		for (int j = i + 1; j < 9; j++) {
			if (dwarfs[i] + dwarfs[j] == sum) { // 나머지 난쟁이 둘의 키의 합과 같다면
				// 일곱 난쟁이가 아닌 나머지 난쟁이 둘을 구하고 키를 최대로 만듬
				dwarfs[i] = 101;
				dwarfs[j] = 101;
				return;
			}
		}
	}

}
int main() {
	for (int i = 0; i < 9; i++) { // 아홉 난쟁이를 입력받음
		cin >> dwarfs[i];
		sum += dwarfs[i]; // 아홉 난쟁이의 합을 구함
	}

	// 아홉 난쟁이의 합 - 일곱 난쟁이의 합 =  나머지 난쟁이 둘의 합
	sum -= 100; 

	Func(); // 일곱 난쟁이를 구함

	sort(dwarfs, dwarfs + 9); // 오름차순 정렬

	for (int i = 0; i < 7; i++) { // 일곱 난쟁이 출력
		cout << dwarfs[i] << endl;
	}

	return 0;
}

 

첫 번째 풀이에서는 두 난쟁이를 찾고 그들의 값을 최댓값으로 변경한 후, 나머지 아홉 난쟁이들의 키를 정렬하여 가장 작은 일곱 난쟁이를 출력하여 문제를 해결했다.

 

그러나 이 방법이 실제 문제에서 요구하는 해답인지 의문이 들었다.

 

해당 문제는 키의 합이 100인 일곱 난쟁이를 찾는 문제다.

하지만 위 풀이에서는 남은 두 난쟁이의 키를 변경하여 해결하려고 했으므로 이 방법이 원래 문제의 의도와 일치하지 않을 것으로 생각했다.

 

그래서 투 포인터 알고리즘을 사용하여 문제를 다시 풀이했다.

 

투 포인터 알고리즘은 정렬된 배열이나 리스트의 양 쪽 끝을 가르키는 두개의 포인터 변수를 선언하고,

이 포인터들을 조작하여 원하는 조건을 만족하는 구간이나 요소를 찾는 알고리즘이다.

// 투 포인터 알고리즘을 적용해 풀이한 코드
#include <iostream>
#include<algorithm>
using namespace std;
// https://codeup.kr/problem.php?id=3008

int main() {
    int dwarfs[9], sum = 0;

    for (int i = 0; i < 9; i++) { // 난쟁이들의 키를 입력 받음
        cin >> dwarfs[i];
        sum += dwarfs[i]; // 9 난쟁이들의 키의 합을 구함
    }
    
    // 투포인터 알고리즘을 사용해야하기 때문에 오름차순으로 정렬
    sort(dwarfs, dwarfs + 9);

    int left = 0, right = 8, currentSum = 0;
    // 아홉 난쟁이의 합 - 일곱 난쟁이의 합 =  나머지 난쟁이 둘의 합
    sum -= 100; 
    while (left < right)
    {
        currentSum = dwarfs[left] + dwarfs[right]; // 난쟁이 둘의 합
        if (currentSum == sum) { // 처음에 구했던 나머지 난쟁이 둘의 합과 같다면
            for (int i = 0; i < 9; i++) { // 해당 난쟁이들을 빼고 나머지 일곱 난쟁이의 키 출력
                if (i != left && i != right) {
                    cout << dwarfs[i] << endl;
                }
            }
            break;
        }
        else if (currentSum > sum) { // 난쟁이 둘의 합이 크다면 right --
            right--; 
        }
        else { // 난쟁이 둘의 합이 크다면 left --
            left++;
        }
    }
   
    return 0;
}

 

투 포인터 알고리즘을 사용한 코드가 처음 풀이한 코드보다 시간 복잡도가 개선되고 가독성이 좋다고 생각한다.

 

CodingTestPractice/CodeUp/탐색기반설계/일곱 난쟁이.cpp at main · seungdo1234/CodingTestPractice