해보자

문제

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

 

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

https://leetcode.com/problems/merge-two-sorted-lists

풀이

우선 결과를 내보낼 dummy 노드를 하나 만들어 연결하고, 순서를 조정할 index 노드를 생성하여 진행했다.

입력 변수인 list1과 list2를 비교하면서 더 작은 값의 노드를 idx가 따라가며 dummy노드 뒤에 연결하도록 하고, while문이 종료된 이후에는 큰값만 남은 노드리스트만 있을테니 남은 리스트를 연결하도록 했다.

코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) {
        	return list2;
        } else if(list2 == null) {
        	return list1;
        }
		
        ListNode dummy = new ListNode(0);
        ListNode idx = dummy;
        
        while(list1 != null && list2 != null) {
        	if(list1.val > list2.val) {
        		idx.next = list2;
        		list2 = list2.next;
        	} else {
        		idx.next = list1;
        		list1 = list1.next;
        	}
        	idx = idx.next;
        }
        
        if(list1 != null) {
        	idx.next = list1;
        } else if(list2 != null) {
        	idx.next = list2;
        }
        
        return dummy.next;
    }
}

결과

Runtime : 0 ms

Memory Usage : 42.39 MB

문제

https://leetcode.com/problems/valid-parentheses

풀이

괄호의 열고 닫힘의 validation을 체크하는 것으로, 소/중/대 괄호에 대한 열고 닫힘이 연속되어야 하는 것이다.

(마지막에 소괄호를 열었으면 소괄호로 닫아야 한다)

이에 Stack을 이용해서 String을 char array로 변환하여 순환하면서, 열림 괄호가 나오면 Stack에 담고 닫힘 괄호가 나왔을 때 동일한 괄호가 나왔는지 확인하도록 했다.

확인하는 방법은 각 괄호에 대해 아스키 값을 확인해 보니 1 또는 2의 차이가 있는 점을 이용하여 닫힘 괄호가 나왔을 때 Stack의 pop 결과와의 차이가 1이나 2가 아닌 경우 실패로 처리했다.

 -> ( : 40, ) : 41, { : 123, } : 125, [ : 91, ] : 93

또한 String에 닫힘 괄호만 있는 등 열림 괄호가 닫힘 괄호보다 개수가 적게 있을 경우 pop할 때 Stack이 비어있기에 에러가 날 수 있다는 상황에 대한 예외 처리도 진행했다.

코드

class Solution {
    public boolean isValid(String s) {
        Stack<Character> valid_stack = new Stack<>();
        for(Character c : s.toCharArray()) {
        	if(c.equals('(') || c.equals('{') || c.equals('[')) {
        		valid_stack.push(c);
        	} else {
        		if(valid_stack.isEmpty()) {
        			return false;
        		}
        		char compare_c = valid_stack.pop();
        		if(c - compare_c > 2 || c - compare_c < 1) {
        			return false;
        		}
        	}
        	
        }
        
        return valid_stack.isEmpty();
    }
}

결과

Runtime : 3 ms

Memory Usage : 41.47 MB

문제

Given the head of a linked list, remove the nth node from the end of the list and return its head.

 

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

 

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

 

https://leetcode.com/problems/remove-nth-node-from-end-of-list

풀이

바로 마지막 위치를 알 수 없는 노드 특성 상, 제거해야할 노드 순서가 뒤에서 몇번째 형태라 바로 몇번만에 도달할 수 있는지 알 수 있는 방법이 없었다.

이에 노드를 따라가기 위한 2개의 노드를 새로 만들고, 이 2개의 노드가 n만큼의 거리를 가지도록 했다.

이후 뒤쪽 노드와 앞쪽 노드 모두 이동 시키면서  더 뒤쪽에 있는 노드가 마지막 노드를 지났을 때 앞쪽의 노드는 제거해야할 노드 전의 노드에 도달하도록 했다.

앞쪽 노드가 도달한 다음을 다다음 노드와 연결하도록 만들어서, 해당 노드의 리스트에서 제거되도록 한 것이다.

다만 처음 더미 노드 없이 바로 입력노드(head변수)을 활용하려면, 노드의 개수가 1개일 때 앞쪽 노드와 뒤쪽 노드의 거리를 벌릴 수 없어서 맨 앞에 더미노드를 하나 만들어서 입력노드와 연결 후 진행하도록 했다.

코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode first = new ListNode(0);
        first.next = head;
        ListNode start = first;
        ListNode end = first;
        
        for(int i = 0; i <= n; i++) {
        	end = end.next;
        }
        
        while(end != null) {
        	start = start.next;
        	end = end.next;
        }
        
        start.next = start.next.next;
        
        return first.next;
    }
}

결과

Runtime : 0 ms

Memory Usage : 42.29 MB

문제

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

https://leetcode.com/problems/4sum

풀이

이전에 풀었던 3Sum에서 숫자 1개를 더 선택하는 것으로, 이와 유사하게 풀었다.

배열을 오름차순으로 정렬 후 2개를 미리 선택해 놓고, 나머지 2개에 대해 각 숫자들을 더한 값을 target과 비교하여 target보다 작은 경우 왼쪽 index 증가 / target보다 큰 경우 오른쪽 index 감소를 진행하며 target과 동일한 값이 선택될 때까지 비교했다.

한가지 문제였던 점은 주어지는 배열 내 숫자가 10억이라 4개를 선택하는 경우 합이 최대 40억이 될 수 있었고, 이는 int의 양수/음수 최대값인 2,147,483,647을 넘는 문제가 있었다.

이에 선택한 4개의 합은 int보다 큰 자리수 표현이 가능한 long으로 계산하도록 진행하여 완료했다.

코드

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        HashSet<List<Integer>> res = new HashSet<>();
    	
    	Arrays.sort(nums);
    	
    	for(int i = 0; i < nums.length-3; i++) {
    		for(int j = i+1; j < nums.length-2; j++) {    			
    			int left = j + 1;
    			int right = nums.length - 1;
    			while(left < right) {
    				long temp_target = Long.valueOf(nums[left]) + Long.valueOf(nums[right]) + Long.valueOf(nums[i]) + Long.valueOf(nums[j]);    				
    				if (temp_target < target) {
    					left++;
    				} else if (temp_target == target) {
    					List<Integer> res_temp = new ArrayList<>();
    					res_temp.add(nums[i]);
    					res_temp.add(nums[j]);
    					res_temp.add(nums[left]);
    					res_temp.add(nums[right]);
    					res.add(res_temp);
    					left++;
    					right--;
    				} else {
    					right--;
    				}
    			}
    		}

    	}
    	return new ArrayList<>(res);
    }
}

결과

Runtime : 143 ms

Memory Usage : 45.54 MB

문제

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

 

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

https://leetcode.com/problems/letter-combinations-of-a-phone-number

풀이

숫자별로 지정된 문자들에 대해 모든 조합을 작성하는 문제였다.

각 숫자별로 나올 수 있는 문자들을 2차원 배열에 저장해 놓고, 각 숫자에 지정된 문자들을 추가하면서 다음 숫자를 확인하여 이어가도록 코드를 작성했다.

현재까지 만든 문자열과 확인한 숫자의 길이가 같기 때문에, 이를 이용하여 dfs를 마무리하도록 했다.

다행이었던 점은 문자만 존재한 2~9까지의 숫자만 입력값으로 준다는 점과 문자열 길이가 최대 4자리라서 소요 시간 걱정은 덜 수 있었다.

코드

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<String>();
		
		if(digits.length() == 0) {
			return res;
		}
		
        String[][] mapping = {{}, {}, 
        		{"a","b","c"}, 
        		{"d","e","f"}, 
        		{"g","h","i"}, 
        		{"j","k","l"}, 
        		{"m","n","o"}, 
        		{"p","q","r","s"}, 
        		{"t","u","v"}, 
        		{"w","x","y","z"}
        		};
        
        dfs(digits, "", mapping, res);
        
        
        return res;
    }

    public void dfs(String digits, String temp_str, String[][] mapping, List<String> res) {
		if(temp_str.length() == digits.length()) {
			res.add(temp_str);
			return;
		}
		
		int idx = Character.getNumericValue(digits.charAt(temp_str.length()));
		for(int i = 0; i < mapping[idx].length; i++ ) {
			dfs(digits, temp_str + mapping[idx][i], mapping, res);
		}
	}
}

결과

Runtime : 1 ms

Memory Usage : 41.90 MB

문제

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

https://leetcode.com/problems/3sum-closest

풀이

이전에 풀었던 3Sum(https://doitalldev.tistory.com/18)과 매우 유사한 문제로,

뽑은 3개의 숫자의 합이 0이냐 target과 가장 가깝냐의 차이만 있었다.

그래서 우선 동일하게 배열을 오름차순으로 정렬하고 하나를 선택한 뒤, 작은 수와 큰 수를 선택하여 target과 가까운지 비교하도록 했다. 

세 숫자의 합이 target보다 작을 때는 작은 수(left)의 위치를 옮기고, 클 때는 큰 수(right)의 위치를 옮기면서 비교를 진행하다가 target과의 차이가 적을 때마다 적용해주는 형태이다.

코드

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
		
		int res = nums[0] + nums[1] + nums[nums.length-1];
    	
    	for(int i = 0; i < nums.length; i++) {
    		int left = i + 1;
    		int right = nums.length - 1;

    		while(left < right) {
    			int temp_res = nums[left] + nums[right] + nums[i];
    			if (temp_res < target) {
    				left++;
    			} else if (temp_res > target) {
    				right--;
    			} else {
    				return temp_res;
    			}
    			
    			if(Math.abs(target - temp_res) < Math.abs(target - res)) {
    				res = temp_res;
    			}
    	      }
    	}
    	return res;
    }
}

결과

Runtime : 14 ms

Memory Usage : 43.42 MB

문제

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

https://leetcode.com/problems/3sum

풀이

나열된 숫자에서 3개를 뽑아 확인하는 것이기에 조합(combination)을 생각했다가,

배열이 최대 3000개일 경우 시간복잡도가 2^3000으로 너무 오래걸리기 때문에 다른 방법을 고민하고 코딩했다.

배열을 오름차순으로 정렬하고 하나를 선택한 뒤, 작은 수와 큰 수를 선택하여 조건에 맞는지 비교하는 방법으로 작성했다.

비교를 하지 않고 넘어갈 조건과 중복을 제거할 조건을 좀 더 추가하면 속도가 더 빠를 것 같긴한데,

우선 HashSet을 이용하여 저장할 때부터 중복을 제거하게끔 진행해봤다.

추가적인 조건은 나중에 다시 생각해봐야겠다.

코드

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        HashSet<List<Integer>> res = new HashSet<>();
    	
    	Arrays.sort(nums);
    	
    	for(int i = 0; i < nums.length; i++) {
    		int left = i + 1;
    		int right = nums.length - 1;

    		while(left < right) {

    			if (nums[left] + nums[right] + nums[i] < 0) {
    				left++;
    			} else if (nums[left] + nums[right] + nums[i] == 0) {
    				List<Integer> res_temp = new ArrayList<>();
    				res_temp.add(nums[i]);
    				res_temp.add(nums[left]);
    				res_temp.add(nums[right]);
    				res.add(res_temp);
    				left++;
    				right--;
    			} else {
    				right--;
    	        }
    	      }
    	}
    	return new ArrayList<>(res);
    }
}

결과

Runtime : 299 ms

Memory Usage : 52.81 MB

문제

Input: strs = ["flower","flow","flight"]
Output: "fl"

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

https://leetcode.com/problems/longest-common-prefix

풀이

substring 결과를 각 문자열의 시작과 동일한지 비교했다.

첫 문자열에서 substring을 늘려가면서 하기에는 이후에 다시 줄여야할 수 있기에, 처음부터 줄여가면서 비교하는 방식으로 진행했다.

긴 문자들만 나온다면 아예 정렬해놓고 처음 문자열과 마지막 문자열을 각 자리별로 비교하는 형태도 괜찮을 것 같다.

코드

class Solution {
    public String longestCommonPrefix(String[] strs) {
        for(int i = strs[0].length(); i > 0; i--) {
        	int f_cnt = 0;
        	for(int j = 0; j < strs.length; j++) {
        		if(strs[j].startsWith(strs[0].substring(0, i))) {
        			f_cnt++;
        			if(f_cnt == strs.length) {
        				return strs[0].substring(0, i);
        			}
        		} else {
        			break;
        		}
        	}
        }
        return "";
    }
}

결과

Runtime : 2 ms

Memory Usage : 44.08 MB