꼽행착오

# 1. Two Sum

Integer Array 와 찾고자 하는 Target 값이 주어졌을 때 Array 에서 더해서 Target 값이 되는 두 수를 찾는 문제

문제 풀이는 간단하게, 배열에 있는 모든 값을 Map 에 등록하고 다시 배열을 탐색하면서 현재 위치의 수와 더해서 Target 이 될 수 있는 수가 있는 지 확인하고 존재하면 해당 두 값의 인덱스를 return

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        map<int, int> m;
        for (int i = 0; i < nums.size(); i++) {
        	// 배열에 존재하는 모든 값을 map 에 등록 (first = 값, second = 인덱스)
        }

        for (int i = 0; i < nums.size(); i++) {
        	// 다시 배열을 탐색해서 현재 값과 더해서 Target 이 되는 값이 map 에 있는 지 확인
            // 확인해서 값이 존재하면 return
        }
        return ans;
    }
};

# 2. Add Two Numbers

두 리스트의 각각의 원소가 저장하는 값을 더하고, 한 자리만 그 위치에 저장. 10 이상의 값이 나온 경우 다음 계산에서 +1을 해 주는 문제

처음 생각은 리스트를 탐색해 두 리스트를 각각 정수형으로 만들고 한 번의 더하기로 합을 만들어 주는 거였는데, 주어진 두 리스트의 길이가 정해진 바가 없어서 정수형으로는 연산이 불가능

그래서 Full Adder 회로와 동일한 동작을 하도록 만들기로 함

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* Head = new ListNode(0);
        ListNode* p, * q, * curr;

        while (p != nullptr || q != nullptr) {
       		// p 와 q 중 어느 하나라도 nullptr 가 아니면 계속 진행
            // 아래 자리에서의 carry 값을 참고해 해당 자리의 sum 을 구하고
            // 그 값을 리스트에 저장
        }

        if (carry > 0)
        	// carry 가 0이 아니면 마지막 자리를 추가
            
        return Head->next;
    }
};

# 3. Longest Substring Without Repeating Characters

주어진 String 에서 동일한 문자가 존재하지 않는 Substring 을 도출하는 문제

처음에는 앞에서부터 탐색하며 동일한 문자가 나오지 않을 때까지 SubString 을 이어 나가고 동일한 문자가 나온 경우 앞에서부터 한 자리씩 줄이고 다시 탐색 (Sliding Window 활용)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        bool check[300] = { false, }; // 동일한 문자가 나왔는 지 확인하기 위한 배열
        int len = s.length();        
        int max = 0, st, ed;
        
        for (st = 0, ed = st + 1; st < len; st++) {
            if (st == 0) {
            	// 처음에는 무조건 SubString 에 추가
            }
            else
            	// 다음부터는 st - 1 위치의 문자를 뺌

            for (; ed < len; ed++) {
            	// 뒤로 늘려가며 같은 문자가 등장하는 지 확인하고
                if (check[s[ed]] == true)
                	// 등장하면 반복 중단
            }
        }

        return max;
    }
};

문제 링크 icpc.me/2508

이 문제는 높이가 서로 다른 나무 N 그루에서 나무를 M 미터만큼 벌목하고자 하는 문제이다.

벌목기를 사용하려고 하는데, 벌목기의 높이 H 를 지정할 수 있고 H 보다 더 큰 나무를 모두 절단해

각 나무의 높이 - H 만큼의 나무를 얻을 수 있다.

이 때 M 미터만큼 벌목을 하기 위해서 H 를 얼마로 설정해야 하는가를 찾는 문제이다.

처음 접근 방식은 N 그루의 나무 중 가장 높이가 큰 나무의 높이로부터 H 를 순차적으로 찾는 방식이었다.

이렇게 할 경우 간단한 문제는 해결이 가능하지만 나무의 개수가 많아질수록 시간이 오래 걸려 시간 초과가 발생하였다.

시간 초과가 발생한 후 다음으로 시도한 방법은 나무를 높이 순으로 정렬한 후 순차탐색을 하는 것이었다.

이렇게 할 경우, 마찬가지로 벌목기의 높이 H 를 줄여가며 확인을 해야 하지만 나무가 높이 순으로 정렬되어 있기 때문에

벌목기가 나무보다 높아질 경우 그 뒤의 나무는 자를 수 있는 지를 확인할 필요가 없다.

두번째 소스 코드 또한 마찬가지로 시간 초과가 발생했다.

아무래도 H 를 바꿔가며 나무를 일일히 확인하는 방법은 시간적으로 많이 소모된다고 생각이 들었다. 그래서 생각해낸 방법이

두번째 방법과 유사하지만 나무를 확인하는 횟수를 줄이는 것이었다.

간단하게 설명하자면, 위의 소스코드는 H 를 변경할 때마다 모든 나무에서 몇 m 씩만큼의 나무를 얻을 수 있는 지를 계산해야 한다.

하지만 이 과정은 나무가 높이 순으로 정렬되어 있기 때문에 불필요한 과정이었다.

이전 단계 (즉, 이전 벌목기의 높이 H) 에서 벌목 가능한 나무를 X 그루라고 하면, 단계가 변할 때마다 총 얻을 수 있는 나무의 양은 X 만큼

증가하게 된다.

추가적으로 H 가 감소했으니, 이전 단계에서 벌목 가능한 나무의 위치 바로 다음 위치부터 있는 나무만을 확인하면 된다.

이렇게 작성한 소스 코드는 다음과 같다.

이렇게 풀었을 때, 더이상 시간초과는 발생하지 않았지만 왠지 모르게 입력되는 값이 커질수록 결과값이 이상하게 출력되었다.

처음에 long long 을 사용하지 않고 int 형을 사용해 자료형 문제로 생각하고 long long 으로 바꾼 후 다시 제출을 했지만

마찬가지로 36% 정도에서 틀렸다는 결과가 발생했다.

그래서 예외 상황이 생길 수 있나 생각했는데 상황을 찾지 못해 결국 풀이 방식을 바꾸는 쪽을 생각했다.

데이터를 정렬하지 않고 문제를 푸는 방법을 생각하게 되었고, 정렬을 하지 않게 되면 이 알고리즘에서 시간을 줄일 수 있는 방법이

H 의 값을 변경하는 횟수를 줄이는 것이었다.

이 알고리즘의 속도는 H 를 얼마나 많이 변경하느냐와 H 에 따라 벌목할 수 있는 나무를 얼마나 탐색하느냐 이 두 가지에 따라 결정된다.

즉, O(H * N) 이 된다고 볼 수 있다. 이 때, N 을 줄이는 것은 앞서 시도한 방법들에서 실패했으니 H 를 줄이는 방법을 생각해 보았다.

H 를 줄이는 방법은 H 를 N 그루의 나무 중 최대 높이부터 1씩 감소시켜 나가는 것이 아니라 최대 높이와 최소 높이를 기준으로

이분 탐색을 하는 방법이었다.

이분 탐색을 함으로써 O(H * N) 은 O(logH * N) 으로 바꿀 수 있게 되고, H 는 최대 1,000,000,000 의 값을 갖는다고 문제의 조건으로

주어졌으니 log(1,000,000,000) ≒ 29 로 알고리즘의 성능은 O(N) 으로 표현할 수 있게 된다.

소스 코드는 다음과 같다.

%spark.dep
z.load("...") // import 하려는 package 를 address:name:version 형식으로 ... 에 입력

후 import ... 형식으로 사용

ex)

%spark.dep

z.load("com.twitter.penguin:korean-text:4.0")

import com.twitter.penguin.***