<LeetCode # 1 ~ 3> 문제 풀이

# 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;
    }
};