[LeetCode # 31 ~ 33] 문제 풀이

# 31. Next Permutation

next permutation Library 함수를 구현하는 문제. 정수 배열이 주어지고, 이 배열의 다음 permutation 을 찾아야 한다.

 

이 문제는 Solution 을 참고해서 문제를 해결했는데 문제 해결 방식은 다음과 같다.

1. 배열의 뒤에서부터 탐색을 하며, 값이 처음으로 작아지는 위치 pos 를 찾는다.

2. pos + 1 부터 배열 끝까지 탐색을 하면서, pos 위치 값보다 더 작은 값의 위치 pos2 를 찾는다.

    (찾지 못한 경우 pos2 는 Last Index 로 지정한다.)

3. pos 값과 pos2 - 1 의 값을 서로 교환한다.

4. pos + 1 부터 배열의 끝까지 값을 뒤집는다.

코딩도 하고 했는데 아직도 로직이 헷갈리는 걸 보니 제대로 이해를 못한 것 같다..

 

void nextPermutation(vector<int>& nums) {
	int i, size = nums.size();
	// 일단 뒤에서부터 탐색하면서 작아지는 첫 번째 위치 탐색
	for (i = size - 1; i > 0; i--) {
		if (nums[i - 1] < nums[i]) {
            cout << nums[i - 1] << " " << nums[i] << "\n";
			// 여기서 i - 1 이 처음 작아진 위치
			for (int j = i; j < size; j++) {
				// 여기서 j 가 마지막 위치거나, j + 1 의 값이 i - 1 보다 작으면 j 랑 i - 1 값 교체
				if (j == size - 1 || nums[i - 1] >= nums[j + 1]) {
                    cout << "swap " << nums[i - 1] << " with " << nums[j] << "\n";
					swap(nums[i - 1], nums[j]);
					break;
				}
			}
			break;
		}
	}
	reverse(nums.begin() + i, nums.end());
}

# 32. Longest Valid Parentheses

괄호 '(', ')' 의 열고 닫음 관계가 올바르게 사용된 것을 찾는 문제인데, 주어진 문자열에서 가장 긴 괄호 문자열을 찾는 문제이다.

 

이 문제를 O(n) 으로 해결할 수 있을 것 같다는 생각은 들었지만, 문제 풀이 아이디어가 떠오르지 않아 솔루션을 참고했다.

스택을 사용한 방식으로 문제를 해결할 수 있었는데, 기존 문제 해결 방식과 달리 push / pop 을 통해 괄호 관계를 판별하는 걸 넘어 스택에 index 를 저장해 두었다가 중간중간 length 를 저장할 수 있도록 했다.

 

int longestValidParentheses(string s) {
    int ans = 0;
    stack<int> idxStack;
    idxStack.push(-1);
    for (int i = 0; i<s.length(); i++){
        if (s[i] == '('){
            idxStack.push(i);
        }
        else {
            idxStack.pop();
            if (idxStack.empty())
                idxStack.push(i);
            else
                ans = ans > i - idxStack.top() ? ans : i - idxStack.top();
        }
    }
    return ans;
}

# 33. Search in Rotated Sorted Array

Rotated Sorted Array 가 주어졌을 때, 그 Array 에서 원하는 값을 찾는 문제

* Rotated Sorted Array 는 이전 문제에서 풀었던, Sorted Array 에서 일정 pivot 앞과 뒤를 반전시킨 Sorted Array

 

이 문제는 Binary Search 함수를 일부 변형해 문제를 해결할 수 있었는데, 풀이는 다음과 같이 했다.

원래 Binary Search 의 경우, index 의 시작부터 끝까지 값이 증가하는 정렬된 자료구조에서 시행되기 때문에 찾고자 하는 값이 시작 index ~ 끝 index 의 값 사이에 없으면 그 구간은 탐색을 하지 않는다.

하지만 이 문제의 경우는, 시작 index 값이 끝 index 값보다 작다는 것이 보장되지 않는다.

예를 들어, [4, 5, 6, 0, 1, 2, 3] 과 같이 배열이 주어지면 [4, 5, 6, 0] 구간은 시작 index 값이 더 크게 된다.

이 때문에 탐색 조건에 한 가지를 추가할 필요가 있었는데 시작 index 값과 끝 index 값을 비교해 그 구간이 증가하는 구간인 지를 먼저 확인한 후 그 구간 내에 탐색하고자 하는 값이 없을 경우에만 구간 탐색을 포기하도록 만들었다.

그 외는 기존 Binary Search 와 동일하게 구현해서 문제를 해결했다.

 

int binarySearch(vector<int>& nums, int target, int s, int e) {
	if (s >= e) {
		if (s == e && target == nums[s])
			return s;
		return -1;
	}

	if (nums[s] < nums[e] && (nums[s] > target || target > nums[e])) {
		return -1;
	}
	int m = (s + e) / 2;
	int l = binarySearch(nums, target, s, m);
	int r = binarySearch(nums, target, m + 1, e);
	if (l != -1)
		return l;
	if (r != -1)
		return r;
	return -1;
}

int search(vector<int>& nums, int target) {
	return binarySearch(nums, target, 0, nums.size() - 1);
}