[LeetCode # 11 ~ 13] 문제 풀이

# 11. Container With Most Water

일렬로 세워진 n 개의 기둥들의 높이가 주어졌을 때, 두 기둥 사이에 받을 수 있는 물의 최대양을 구하는 문제

* 두 기둥 사이에 받을 수 있는 물은 (두 기둥 사이 거리 * 두 기둥 중 낮은 기둥의 높이) 로 정의

 

처음 이 문제를 봤을 때는, O(n^2) 으로 경우를 다 탐색해야 하나 생각을 했는데 이렇게 할 경우에 n 이 최대 3만이고 n^2 은 9억이니 불가능할 것이라고 생각했다. 그래서 생각한 점은, 기둥 사이 거리의 최대는 양 끝점이고, 양 끝점부터 하나씩 좁혀나가며 탐색을 하면 n 번만 탐색을 할 수 있을 것이라고 생각이 들었다.

 

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

int maxArea(vector<int> &height) {
	int l = 0, r = height.size() - 1;
    int max = 0;
    while (l < r) {
    	int area = _MIN_(height[l], height[r]) * (r - l);
        max = max > area ? max : area;
        if (height[l] < height[r])
        	l++;
        else
        	r--;
    }
}

# 12. Integer to Roman

정수 N 이 주어졌을 때, 이를 Roma 표기법으로 변경하는 문제

* I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000

 

이 문제는 풀이가 떠오르지 않아서 Solution 을 참고해 풀이를 작성했다.

나는 1, 5, 10, 50, ... 각 숫자 앞자리가 1 / 5 로 달라서 이를 어떻게 처리할 지 고민을 했는데, 솔루션은 이를 가볍게 해결할 수 있는 방법을 사용했다. 10 의 승수 기준으로만 숫자를 처리하는 것이 그 방법이었는데, 4 / 9 등의 숫자가 나오면 별도의 처리가 필요하지만 그 외는 일정하게 처리가 가능한 방식이었다.

 

여기서 Map 은 각 숫자가 어떤 문자로 변환될 지를 저장하기 위해 사용되었다.

 

string intToRoman(int num) {
	map<int, char> m = {{1, 'I'}, {5, 'V'}, ..., {1000, 'M'}};
    string ans = "";
    
    for (int i = 1000; i > 0; i /= 10) {
    	int firstNum = num / i;
        
        if (firstNum == 4) {
        	ans += m[i];
            ans += m[i * 5];
        }
        else if (firstNum == 9) {
        	ans += m[i];
            ans += m[i * 10];
        }
        else {
        	if (firstNum > 4) {
            	ans += m[i * 5];
            }
            for (int k = 0; k < (firstNum % 5); k++) {
            	ans += m[i];
            }
        }
        num %= i;
    }
    return ans;
}

# 13. Roman to Integer

이 문제는 위의 # 12. 문제를 거꾸로 만드는 문제이다.

 

위의 문제는 각 자리수별로 어떤 수가 저장되어있는 지를 확인해서 그 값을 로마자로 바꿔줬는데, 이번 문제는 로마자를 보고 수로 바꿔주었다.

차이점은, 로마자의 경우 현재의 값이 하나의 독립적인 값이 아니라 다음에 나올 값의 전치 값으로 사용될 수 있기 때문에 이를 조건에 추가해서 계산하도록 만들었다.

 

마찬가지로 map 을 사용했는데 이번에는, 각 문자가 어떤 숫자로 변환될 것인지 그 값을 저장하기 위해 사용되었다.

 

int romanToInt(string s) {
	map<char, int> m = {{'M', 1000}, {'D', 500}, ..., {'I', 1}};
    int ans = 0;
    
    for (int i = 0; i < s.length(); i++) {
    	if (m[s[i + 1]] > m[s[i]]) {
        	ans -= m[s[i]];
            ans += m[s[i + 1]];
        }
        else {
        	ans += m[s[i]];
        }
    }
    return ans;
}