Leet Code - 219. Contains Duplicate II(C++)

예제: Contains Duplicate II

문제
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

풀이

영어!!영어!! 다 좋았는데 at most를 놓쳐서 몇 번 틀린 문제이다.
요약 해석하자면, nums[i] = nums[j]가 되는 인덱스 i와 j의 절대값의 차가 k이하인 경우가 있는지를 묻는 문제이다.

필자는 <값, index>를 속성으로 가진 vector를 선언하여 nums를 인덱스와 함께 저장하였다.
그 후 sort를 사용하여 오름차순으로 정렬한 후, 두 개씩 비교하며 값이 같을 때 인덱스의 절대값의 차가 k 이하이면 바로 true를 리턴하도록 알고리즘을 세웠다.

필자의 코드는 시간이 O(2N)이 될 것이다.

전체적인 소스코드는 아래와 같다.

소스 코드

class Solution {
public:
	bool containsNearbyDuplicate(vector<int>& nums, int k) {
		if (nums.size() == 0) return false;

		vector<pair<int, int>> v;
		for (int i = 0; i < nums.size(); i++) {
			v.push_back(make_pair(nums[i], i));
		}
		sort(v.begin(), v.end());

		for (int i = 0; i < v.size() - 1; i++) {
			if (v[i].first == v[i + 1].first)
				if (abs(v[i].second - v[i + 1].second) <= k)
					return true;
		}

		return false;
	}
};

풀이 후기

리트코드는 참 신기하다.
이게 easy 난이도라고? 싶은 문제도 있는가 하면 이게 easy 난이도지! 싶은 문제도 있다.
혹은 필자의 실력이 들쭉날쭉 하거나..