LeetCode(35) - Search Insert Position 문제 중복을 허용하지 않는 정렬된 integer nums와 integer type의 target이 주어진다. nums배열에서 target을 발견한다면 target이 위치한 index를 반환한다. target을 찾지 못하였다면 target이 포함될 index를 반환한다. time complexity는 O(log n)을 만족해야 한다. 입력 Input: nums = [1,3,5,6], target = 7 출력 Output: 4 풀이 O(log n) 의 조건이 없다면, 정렬된 배열이므로 for loop으로 한번 배열을 순회하면 답을 찾을 수 있다. 하지만 이 경우 Time complexity는 O(n) 이므로 사용할 수 없다....
LeetCode(27) - Remove Element 문제 중복이 허용되며, 정렬되지 않은 integer 배열 nums와 val가 주어진다. nums에서 val가 제거된 배열을 반환한다. 추가적인 array 할당은 할 수 없으며, in-place로 수정한다. 입력 nums = [0,1,2,2,3,0,4,2], val = 2 출력 5, nums = [0,1,4,0,3,_,_,_] 풀이 문제 26과 유사한 내용이다. 전체 배열을 순회하면서 val와 다른 값이라면 count index에 현재 값을 저장한다. 정렬되지 않은 값이라고 하더라도, count index로 in-place에 저장된 값들은 이미 val과 비교된 값이므로, 현재 element와 비교만 하면 된다....
LeetCode(26) - Remove Duplicates from Sorted Array 문제 중복이 허용된 integer type의 오름처순 배열에서, 중복된 값들을 제거한 sorted array를 만들고, 중복을 제외한 원소의 개수를 반환하라. 입력 nums = [0,0,1,1,1,2,2,3,3,4] 출력 5, nums = [0,1,2,3,4,_,_,_,_,_] 풀이 추가적인 배열을 할당하지 않고, 주어진 vector<int>를 수정할 것. 그리고 반환하는 원소의 개수 이후의 nums index는 don’t care 한다. 주어진 배열을 마사지 해서 반환해야 하므로, 배열을 순회하면서 배열의 값을 바꿔야 한다. 처음 접근은 다음과 같이 진행하였다....
LeetCode(21) - Merge Two Sorted Lists 문제 두 Linked List의 header가 주어진다. 두 리스트를 정렬하여 하나의 리스트로 반환하라. 입력 list1 = [1,2,4], list2 = [1,3,4] 출력 [1,1,2,3,4,4] 풀이 두 리스트를 순회하면서 작은값을 취하고, 취한 리스트는 다음 노드로 이동하여 두 리스트가 모두 NULL일 때 까지 순회한다. 두 리스트는 모두 정렬된 상태이므로, 함수 도입부에서 한 리스트가 NULL이라면 다른 리스트를 반환한다. 두 리스트 모두 NULL인 경우가 있어서 헷갈렸는데, list1이 NULL일 경우 NULL인 list2를 리턴해도 무방했다....
LeetCode(20) - Valid Parentheses 문제 소괄호, 중괄호, 대괄호로 이루어진 문자열이 주어진다. 이 문자열의 괄호들이 알맞은 pair라면 true를, 아니라면 false를 반환한다. 입력 s = "()[]{}" 출력 true 풀이 전형적인 stack문제로, 괄호가 닫힐때 마다 pair를 확인한다. 주어진 문자열의 문자들을 순회하면서 문자가 여는괄호면 stack에 쌓고, 닫는 괄호라면, 현재 stack에서 top()과 pair비교 후 pair라면 pop을, 아니면 false를 리턴한다. 코드 Visual studio에서 바로 실행하도록 임의의 main문을 함께 첨부합니다. isValid()만 보시면 됩니다. #include<iostream> #include<string> #include<stack> using namespace std; bool isValid(string s) { stack<char> st; for (char c : s) { if (c == '(' || c == '{' || c == '[') { st....