leetcode3 [Easy] Leetcode | 21. Merge Two Sorted Lists | Linked list - 문제 연결 리스트를 이용하여 주어진 정렬된 두 리스트를 병합시켜 새 리스트를 만들어 반환하는 문제이다. 노드 구조체는 문제에 주어진다. - 풀이 우선 주어진 리스트가 NULL일 경우는 나머지 리스트를 그대로 반환해준다. l1과 l2를 가리키는 리스트를 first, second로 선언한다. head라는 더미노드를 만들고 head->next에 반환할 리스트의 첫 노드를 생성한다. 즉 병합된 리스트의 첫 노드는 head->next 노드이다. curNode를 생성해 새로 노드가 추가될 곳을 가리키도록 한다. tempList는 루프를 진행하며 l1과 l2중 크기가 작은 노드를 가리키도록 하며 curNode->next에 tempList->val을 val로 갖는 노드를 생성한다.첫 루프는 둘 중 하나의 리스트가 .. 2020. 2. 1. [Easy] Leetcode | 20. Valid Parentheses | String, Stack - 문제 스택의 대표적인 문제인 괄호 검사 알고리즘 문제이다. 괄호로 이루어진 문자열이 주어지는데 이 문자열 속 괄호들이 쌍에 맞으며 순서 또한 맞는지 검사하는 문제이다. - 풀이 스택의 LIFO (Last In First Out) 성질을 이용하여 순서와 쌍을 검사한다. 대략적인 알고리즘은 문자열의 크기만큼 루프를 돌면서 열린 괄호는 모두 스택에 저장한다. 따라서 시간 복잡도는 O(n)이 될 것이며 최악의 경우 스택에 n개 모두 저장하므로 공간 복잡도는 O(n)이 될 것이다. 만약 닫힌 괄호( ')', '}', ']' ) 가 나온다면 무조건 스택의 top(마지막에 저장한 괄호)과 쌍이 맞아야 하므로 top이 쌍이 맞지 않다면 false를 반환하며 쌍이 맞다면 top의 요소를 pop한다. 이 과정을 반복하.. 2020. 1. 29. [Easy] Leetcode | 1. Two Sum | Array, Hash table - 문제 integer를 요소(원소)로 가지는 array(nums)와 target이 주어진다. array의 요소 중 2개의 요소를 더해 target을 만드는 요소의 인덱스 2개를 반환하는 함수를 만드는 문제이다. 정답은 정확히 1개가 존재하며, 동일한 요소를 중복으로 사용할 수 없다고 가정한다. 위의 예를 보면 2와 7을 더하면 target이 되므로 0과 1이 담긴 배열을 반환하면 정답이다. - 풀이 우선 크게 2가지 방법이 있다. 첫 번째 방법은 이중 루프를 사용하여 모든 경우를 한 번씩 확인하는 것이다. 따라서 이 경우 모든 조합을 다 체크하므로 시간복잡도는 n*(n-1)/2 => O(n^2)이 될 것이다. 그리고 반복 횟수와 상관없이 반환할 요소는 2개이므로 공간 복잡도는 O(1)이 될 것이다. 다.. 2020. 1. 28. 이전 1 다음
