코딩테스트 문제 (5) - 가장 큰 수
문제 이름이 가장 큰 수로 되어 있지만 당연하게도 배열 중 가장 큰 수를 찾는 문제는 아닙니다. 이 문제는 항목들을 조합하여 만들 수 있는 가장 큰 수를 출력하는 문제입니다. 문제 1. [10,2] => '210', 2. [3,30,34,5,9] => '9534330' [10,2] 케이스의 경우 10을 추출하는 것이 아닌 두 원소의 조합 '102'와 '210' 중 더 큰 수를 출력해야 합니다. 배열의 원소는 정수입니다. 풀이 [10,2]의 경우 10이 아닌 2가 앞에 위치하도록 정렬해야 합니다. [3,30,34,5,9]의 경우에는 9가 맨 앞에 위치하도록 정렬해야합니다. 이러한 순으로 정렬한 후에 각 원소를 string으로 만들어 join 메소드를 이용해 합치면 될 것 같습니다. 배열의 원소가 정수로 들..
코딩테스트 문제 (4) - 구간 병합
이 문제는 구간들을 원소로 가진 입력 리스트에 대해 겹치는 구간을 병합한 결과를 제출하는 문제입니다. 문제 1. [[2,6],[15,18],[1,3],[8,10]] => [[1,6],[8,10],[15,18]] 입력은 정렬되지 않은 상태로 들어옵니다. 풀이 먼저 입력이 정렬되지 않았으니 시작점 기준으로 정렬해야 할 것 같습니다. 그 후, for 루프를 통해 각 구간을 순회하면서 전 구간의 끝점과 현 구간의 시작점을 비교해서 두 값이 겹치게 되면 병합하면 될 것 같습니다. kaggle.com 의 notebook으로 작성한 풀이는 다음과 같습니다. 홍머스 정리 난이도: 하 참조 , p497-498 leetcode.com/problems/merge-intervals/
코딩테스트 문제 (3) - 두 배열의 교집합
두 배열의 교집합을 찾는 문제입니다. 중복된 문자는 고려하지 않고 한 문자로 취급합니다. 문제 1. array1 = [1,2,2,1], array2 = [2,2] => [2] 2. array1 = [4,9,5], array2 = [9,4,9,8,4] => [9,4] 풀이 array1과 array2에 대해 이중 for 루프를 돌면서 결과 집합 (파이썬의 set)에 추가하면 될 것 같습니다. 하지만 array 2개의 루프를 수행하니 시간 복잡도는 $O(n^2)$가 되겠네요. 더 작은 시간 복잡도가 걸리는 방법은 뭘까요? array1에 대해서는 그대로 for 루프를 수행하고 for 루프 안에서 해당 array1의 값을 array2에 대해 이진 탐색으로 값을 검색하면 어떨까요? 이진 탐색은 시간 복잡도가 $O(..
코딩테스트 문제 (2) - 유효한 괄호
이 문제는 괄호 "(,),{,},[,]" 로 이루어진 string이 입력으로 들어왔을 때, 괄호의 여는 곳과 닫는 곳이 문맥 상 일치하는지 묻는 문제로 대표적인 스택 문제입니다. 테스트 케이스를 한 번 살펴보죠. 문제 1. '{}(){}' => True, 2. '{()}[]' => True, 3. '{{)}[}' => False, 4. '(([]))' => True 풀이 스택 문제라고 언급했는데, 스택을 어떻게 이용해야 할까요? 스택은 마지막 원소가 추출되니 '[', '(', '{' 같이 여는 괄호를 스택에 순서대로 넣어두고 ']', ')', '}' 가 들어오면 스택에서 pop해서 매칭이 되는지 확인하면 될 것 같습니다. 그리고 마지막에 스택에 원소가 남아 있으면, 매칭되는 닫는 괄호가 입력에 없는 것이..
