<LeetCode # 4 ~ 6> 문제 풀이

# 4. Median of Two Sorted Arrays

정렬된 두 Array A, B 가 주어졌을 때, 중간값을 구하는 문제

* 수행시간이 O(log(m + n)) 으로 주어짐

 

우선, 내 머리로 이 문제를 풀기엔 역부족이었고 Solution 을 참고했다.

처음 생각했던 것은, 두 Array 가 정렬이 되어 있으니, Merge 를 하면 되지 않을까.. 생각을 했는데 그렇게 되면 O(m + n) 이 되므로 문제 풀이에 적합하지 않았다.

그래서 Solution 을 처음 봤는데 두 Array 를 각각 나눠서 왼쪽 부분과 오른쪽 부분을 각각 합치는데 그렇게 하면 왼쪽의 Max 값과 오른쪽의 Min 값으로 중간값을 구할 수 있다는 것이었다.

근데 여기서, 두 Array 를 나눠서 왼쪽 부분의 Max 가 오른쪽 부분의 Min 보다 작다는 보장을 할 수 있나... 라고 생각을 하던 중 Solution Source Code 를 보고 의문이 풀렸다.

이 문제를 푸는 Solution 의 핵심은 그 위치를 찾는 것이었다. 한 Array 를 기준으로 잡고 그 Array 에서 나눌 위치를 찾는 것을 이분탐색을 통해 수행하는 것, 그것이 이 문제의 해답이었다.

#define _MAX(x, y) ((x) > (y) ? (x) : (y))
#define _MIN(x, y) ((x) < (y) ? (x) : (y))

class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int m = nums1.size(), n = nums2.size();
		if (m > n) {
        	// Array 1 번을 기준으로 잡고 풀이를 진행하기 위해 Array 1 이 짧거나 같도록 유지
		}
        // Slice 위치 탐색을 위한 값 설정
		int iMin = 0, iMax = m, half = (m + n + 1) / 2;
		while (iMin <= iMax) {
        	int i, j; // i 는 Array 1 을 Slice 할 인덱스, j 는 나머지 개수를 채우기 위한 index
			if (i < iMax && nums2[j - 1] > nums1[i]) {
				// Slice 를 했는데 Array 2 의 Left Max 값이 
                // Array 1 의 Right Min 값보다 큰 경우
			}
			else if (i > iMin && nums1[i - 1] > nums2[j]) {
				// Slice 했는데 Array 1 의 Left Max 값이
                // Array 2 의 Right Min 값보다 큰 경우
			}
			else {
            	// 그 외 조건에 맞게 Median 값을 찾기

				if ((m + n) % 2 == 1)
					return (double)maxLeft;

				return (double)(maxLeft + minRight) / 2;
			}
		}
		return 0.0;
	}
};

# 5. Longest Palindromic Substring

String 이 주어지고, 이 String 의 Substring 중에 가장 긴 Palindromic String 을 찾는 문제

* Palindromic String 이란, 좌우가 대칭되는 문자열을 의미한다. ex) "abcba", "StringnirtS", ...

 

가장 먼저 떠올린 생각은, Dynamic Programming 을 활용하면.. 풀 수 있지 않을까 였는데 그 방법이 떠오르지 않아서 중심을 잡고 거기서 확장해 나가는 방법을 떠올렸다.

예를 들어, "ABCDEFG" 라는 문자열이 있으면, 'A', 'B', 'C', .. 각각의 문자를 중심으로 양 옆으로 확장했을 때 좌우 대칭이 이뤄지는 지를 확인하면 되지 않을까 라는 생각이었다.

이렇게 할 경우, Best Case 는 O(n) 의 시간 복잡도를 가질 것이고 Worst 의 경우는 O(n^2) 의 시간 복잡도를 가질 것이라 생각했다. 모든 위치에서 SubString 이 String 길이 만큼의 Palindromic 을 가질 경우가 Worst 라고 생각했지만, 그럴 경우는 거의 없을 것이고 평균적으로 O(n) 에서 크게 벗어나지 않을 것이라는 생각을 했다.

#define _MAX(x, y) ((x) > (y) ? (x) : (y))

int calculate(string &s, int l, int r) {
	while (l >= 0 && r < s.length() && s[l] == s[r]) {
    	// 기준 L, R 을 확인해서 두 문자가 서로 같으면 탐색을 계속한다.
	}
	return r - l - 1;
}

class Solution {
public:
	string longestPalindrome(string s) {
		if (s.length() < 1)
			return "";
		int st = 0, ed = 0;

		for (int i = 0; i < s.length(); i++) {
			int l1, l2; // l1 은 현재 위치 기준 1개부터 시작하고, l2 는 현재 위치 기준 2개씩 시작
			int len = _MAX(l1, l2);
			if (len > ed - st) {
				// 어디부터 시작하고 어디서 끝나는 지 st, ed 저장
			}
		}
		return s.substr(st, ed - st + 1);
	}
};

# 6. ZigZag Conversion

String 과 Row 를 주고, 지그재그로 문자열을 표현했을 때 Row 순으로 저장된 문자열을 찾는 문제

ex) String : "ABCDEFGHIJ", Row : 3
A      E       I

B  D  F  H  J

C      G

Result : "AEIBDFHJCG"

 

이 문제 역시 Solution 을 참고했다.

처음에 문제를 보고, 아! 행별로 문자를 뛰어넘는 Offset 값이 있고, 그걸 구해서 찾으면 되겠다! 라고 생각을 했는데

계산하기에 조건이 조금 귀찮아서 Solution 을 살짝 봤다.

계산하는 방식도 있긴 했지만, 그것보다 더 쉬운 방식이 있어 그걸 참고해서 구현했다.

참고한 방식은, 행별로 문자열을 저장할 공간을 만들어 두고 그냥 문자열을 순서대로 탐색하며 한 문자씩 한 행에 추가하는 방식이었다.

내가 생각한 방식보다 구현도 더 간단하고 시간적인 측면에서도 거의 차이가 없을 것 같아 이 방식을 사용했다.

#define _MIN_(X, Y) ((X) < (Y) ? (X) : (Y))

class Solution {
public:
    string convert(string s, int numRows) {
	if (numRows == 1)
		return s;
	string ret = "";
	vector<string> rows(_MIN_(numRows, s.size())); // 행별로 문자열을 저장해 둘 공간
	int curRow = 0; // 현재 어느 행에 저장할 지
	bool dir = true; // 다음 행의 위치가 어느 방향인지

	for (char c : s) {
        // 문자열 순서대로 탐색하면서 각 문자를 현재 행에 추가
        // 현재 행을 고려해 방향을 정하고, 그 방향으로 행 이동
	}
	for (string tmp : rows) {
        // 마지막에 행 순서대로 문자열 저장
	}
	return ret;
}
};