[프로그래머스] 음양 더하기

문제 요약

주어진 절댓값 배열 absolutes와 부호 배열 signs를 이용하여 실제 정수들의 합을 구하는 문제입니다.

시간 복잡도 분석

• 최악의 경우: absolutes 배열의 모든 원소를 한 번씩 순회해야 하므로, 시간 복잡도는 O(N)입니다. 여기서 N은 absolutes 배열의 길이입니다.
• 평균적인 경우: 최악의 경우와 동일하게 O(N)입니다.

결론: 입력 배열의 크기에 비례하여 시간이 선형적으로 증가하므로, 효율적인 알고리즘이라고 할 수 있습니다.

공간 복잡도 분석

• 추가 메모리 사용: 별도의 자료구조를 사용하지 않고, 입력으로 주어진 배열과 합을 저장할 변수 answer만 사용합니다.
• 공간 복잡도: O(1)입니다. 즉, 입력 데이터의 크기에 상관없이 일정한 크기의 메모리만 사용합니다.

결론: 공간 복잡도가 매우 낮아 메모리 효율적인 알고리즘입니다.

코드 다시 보기

public int solution(int[] absolutes, boolean[] signs) {
    int answer = 0;

    for (int i = 0; i < absolutes.length; i++) {
        answer += signs[i] ? absolutes[i] : -absolutes[i];
    }

    return answer;
}

• 시간 복잡도 O(N): for 루프를 통해 배열을 한 번 순회하므로 N에 비례하는 시간이 소요됩니다.
• 공간 복잡도 O(1): 추가적인 메모리 사용 없이 입력 배열과 answer 변수만 사용합니다.

결론

위 코드는 음양 더하기 문제를 해결하기 위한 효율적이고 간결한 풀이입니다. 시간 복잡도와 공간 복잡도 모두 최적이며, 실제 환경에서 사용하기 적합합니다.

요약:

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)
• 장점: 간결하고 효율적이며, 메모리 사용량이 적음

더 궁금한 점이 있다면 언제든지 질문해주세요.

참고:

• 시간 복잡도: 알고리즘이 문제를 해결하는 데 걸리는 시간을 입력 데이터의 크기에 대한 함수로 나타낸 것
• 공간 복잡도: 알고리즘 실행 시 사용되는 메모리 양을 입력 데이터의 크기에 대한 함수로 나타낸 것
• O 표기법: 알고리즘의 성능을 비교하기 위한 표기법으로, 입력 데이터의 크기가 충분히 커질 때 가장 큰 영향을 미치는 항만을 나타냄

다른 풀이 방법:

• if-else 문: 삼항 연산자 대신 if-else 문을 사용하여 조건 분기를 할 수 있습니다.
• for-each 문: Java 5부터 도입된 for-each 문을 사용하여 배열을 순회할 수도 있습니다.
• 스트림: Java 8부터 도입된 스트림을 이용하여 함수형 스타일로 코드를 작성할 수 있습니다.

주의: 위에서 제시된 풀이들은 모두 시간 복잡도와 공간 복잡도 측면에서 큰 차이가 없습니다. 따라서 문제의 요구 사항과 개인의 코딩 스타일을 고려하여 적절한 방법을 선택하면 됩니다.