코딩테스트는 현대의 많은 기업들이 구직자를 평가하는 데 사용하는 중요한 도구입니다. 오늘은 배열과 리스트를 주제로 하는 문제를 다뤄보겠습니다. 배열(array)과 리스트(list)는 자료 구조의 가장 기초적인 형태로, 많은 알고리즘 문제에서 기본적으로 사용됩니다. 배열은 고정 크기의 연속 메모리 공간에 데이터를 저장하는 반면, 리스트는 동적 크기로 요소를 저장할 수 있습니다. 이 두 가지의 차이점을 이해하고 이를 이용한 문제 해결 능력을 키우는 것이 중요합니다.
문제: 배열에서 두 숫자의 합 찾기
주어진 정수 배열에서 특정 합을 만들 수 있는 두 숫자의 인덱스를 찾아라. 배열의 요소는 중복될 수 있으며, 두 숫자는 반드시 서로 다른 인덱스에서 선택되어야 한다.
입력 형식
- 첫 번째 줄에는 배열의 크기
n(1 ≤n≤ 10^4)이 주어진다. - 두 번째 줄에는 배열의
n개의 정수a[0], a[1], ..., a[n-1](1 ≤a[i]≤ 10^9)이 주어진다. - 세 번째 줄에는 찾고자 하는 정수
target가 주어진다.
출력 형식
찾은 두 숫자의 인덱스를 공백으로 구분하여 출력한다. 만약 존재하지 않는 경우 -1을 출력한다.
예제
입력:
5
2 7 11 15
9
출력:
0 1
문제 해결 전략
이 문제는 배열에서 두 숫자의 합을 찾는 대표적인 문제로, 다음과 같은 과정을 통해 해결할 수 있습니다:
- 해시맵 사용:
해시맵을 사용하여 배열 요소와 그 인덱스를 저장합니다. 각 요소에 대해, target - current_number를 계산하여 해시맵에서 해당 값이 있는지 확인합니다. 만약 존재한다면 해당 인덱스와 현재 인덱스를 반환합니다. 이 접근법은 평균적으로 O(n) 시간 복잡도를 가집니다.
C++ 코드 구현
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
vector twoSum(vector& nums, int target) {
unordered_map hashMap; // 해시맵 선언
for (int i = 0; i < nums.size(); ++i) {
int complement = target - nums[i]; // 필요한 숫자 찾기
if (hashMap.find(complement) != hashMap.end()) {
return {hashMap[complement], i}; // 인덱스 반환
}
hashMap[nums[i]] = i; // 숫자와 그 인덱스 저장
}
return {-1}; // 찾지 못한 경우
}
int main() {
int n, target;
cin >> n;
vector nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i]; // 배열 입력
}
cin >> target; // 타겟 입력
vector result = twoSum(nums, target);
for (int idx : result) {
cout << idx << " "; // 결과 출력
}
return 0;
}
코드 설명
위 코드는 주어진 배열과 타겟 값을 입력받아 두 숫자의 인덱스를 찾는 방식으로 작동합니다. unordered_map을 사용해 각 숫자와 그 인덱스를 저장함으로써, 배열을 한 번만 순회하여 해결할 수 있습니다. 이렇게 함으로써 최악의 경우에도 O(n)의 시간 복잡도를 가지게 됩니다.
결과 검증
작성한 코드가 정확하게 작동하는지 검증하기 위해, 다양한 테스트 케이스를 준비합니다. 예를 들어:
- n=5, 입력 배열: [2, 7, 11, 15], 타겟: 9 → 결과: 0 1
- n=4, 입력 배열: [3, 2, 4], 타겟: 6 → 결과: 1 2
- n=3, 입력 배열: [3, 3], 타겟: 6 → 결과: 0 1
- n=2, 입력 배열: [1, 2], 타겟: 3 → 결과: 0 1
- n=1, 입력 배열: [2], 타겟: 2 → 결과: -1 (원소가 없으므로)
마무리
오늘은 배열과 리스트를 이용한 코딩테스트 문제를 한 가지 다루어 보았습니다. 두 숫자의 합을 찾는 문제는 어려운 문제는 아니지만, 다양한 방법으로 접근 가능하다는 점에서 연습할 가치가 있습니다. 해시맵을 사용하면 시간 복잡도를 효율적으로 줄일 수 있는 좋은 예입니다. 다음 강좌에서는 다른 자료 구조나 알고리즘 접근 방식을 다뤄보겠습니다. 계속해서 코딩 연습을 해보세요!