[LeetCode # 20 ~ 22] 문제 풀이

# 20. Valid Parentheses

괄호로 이루어진 문자열이 주어졌을 때, 이 문자열의 괄호 구조가 적절한 지 확인하는 문제

 

이 문제는 단순히 스택을 활용해서 여는 괄호면 push, 닫는 괄호면 pop 해서 확인하는 방식으로 문제를 해결했다.

bool isValid(string s) {
	stack<char> st;

	for (auto c : s) {
		if (c == '(' || c == '[' || c == '{')
			st.push(c);
		else {
			if (st.empty())
				return false;
			switch (c) {
			case ')':
				if (st.top() != '(')
					return false;
				break;
			case ']':
				if (st.top() != '[')
					return false;
				break;
			case '}':
				if (st.top() != '{')
					return false;
				break;
			}
			st.pop();
		}
	}
	if (!st.empty())
		return false;
	return true;
}

# 21. Merge Two Sorted Lists

정렬된 두 리스트가 주어졌을 때, 정렬을 유지한 상태로 두 리스트를 하나로 합치는 문제

 

간단하게 Two Pointer 사용해서 순서대로 비교하고, 하나의 리스트로 합치도록 만들었다.

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	ListNode dummyHead = ListNode(0);
	ListNode *tmp = &dummyHead;
	while (l1 != nullptr || l2 != nullptr) {
		if (l1 == nullptr) {
			tmp->next = l2;
			tmp = tmp->next;
			l2 = l2->next;
		}
		else if (l2 == nullptr) {
			tmp->next = l1;
			tmp = tmp->next;
			l1 = l1->next;
		}
		else {
			if (l1->val < l2->val) {
				tmp->next = l1;
				tmp = tmp->next;
				l1 = l1->next;
			}
			else {
				tmp->next = l2;
				tmp = tmp->next;
				l2 = l2->next;
			}
		}
	}
	return dummyHead.next;
}

# 22. Generate Parentheses

Parentheses 쌍의 개수 n 이 주어졌을 때, 가능한 괄호 "()" 쌍의 조합을 모두 구하는 문제

 

주어진 n 개의 여는 괄호 / 닫는 괄호의 가능한 모든 조합을 그냥 Recursive 함수로 찾도록 구현

사용된 여는 괄호 개수만큼만 닫는 괄호를 사용할 수 있도록 해 불가능한 괄호 조합은 만들지 않도록 했다.

vector<string> generateParenthesis(int n) {
	vector<string> ans;
	recursiveGenerate(ans, "", n, n);
	return ans;
}

void recursiveGenerate(vector<string>& v, string s, int l, int r) {
	if (l == 0 && r == 0) {
		v.push_back(s);
		return;
	}

	if (l > 0) {
		recursiveGenerate(v, s + "(", l - 1, r);
	}
	if (r > l) {
		recursiveGenerate(v, s + ")", l, r - 1);
	}
}