해보자

문제

• Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
  

  Input: nums1 = [1,3], nums2 = [2]
  Output: 2.00000
  Explanation: merged array = [1,2,3] and median is 2.
  

  Example 2:
  
  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106
• Constraints:
• Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
• Example 1:
• The overall run time complexity should be O(log (m+n)).

https://leetcode.com/problems/median-of-two-sorted-arrays/

풀이

이미 정렬된 두개의 배열을 준다고 하여, 그냥 하나로 합쳐서 풀었다.

코드

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int i = 0, j = 0, z = 0;
        
        int[] nums = new int[nums1.length + nums2.length];
        while (i < nums1.length && j < nums2.length) {
            nums[z++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        }
         
        if (i == nums1.length) {
            for (; z < nums.length; z++) {
                nums[z] = nums2[j++];
            }
        }
        else {
            for (; z < nums.length; z++) {
                nums[z] = nums1[i++];
            }
        }
        
         
        if (nums.length % 2 == 0) {
        	return (double)(nums[nums.length / 2 - 1] + nums[nums.length / 2]) / 2;
        }
        else {
        	return nums[nums.length / 2]; 
        }
    }
}

결과

문제

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

https://leetcode.com/problems/longest-substring-without-repeating-characters/

풀이

이전에는 String에 넣고, 중복된 문자가 있는 경우 다시 시작했던 index의 다음부터 다시 비교하다 보니 시간과 메모리 소요가 컸다.

최대한 반복하지 않고, 변수도 줄일 생각으로 문제를 다시 한번 풀어보았다.

이번에는, 가면서 중복된 문자가 있을 경우 start를 1증가시켜서 다시 비교해 나가는 방식으로 코드를 작성했다.

substring을 사용하여 현재 index의 문자가 없는 부분까지 start를 증가시킨 후, 다음 index부터 비교하도록 하여 반복 시간과 메모리 사용량을 줄였다.

코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int start = 0;
        int idx = 0;
        int maxlength = 0;
        
        while(idx < s.length()) {
        	if(start > idx) {
        		break;
        	}
        	
        	if(!s.substring(start, idx).contains(""+s.charAt(idx))) {
        		idx++;
        		maxlength = (maxlength - (idx - start) > 0) ? maxlength : (idx - start);
        		continue;
        	}
        	
        	start++;
        }
        
        return maxlength;
    }
}

결과

• AS-IS

• TO-BE

문제

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

https://leetcode.com/problems/longest-substring-without-repeating-characters/

풀이

하나씩 비교해 가면서 중복된 문자가 있을 경우, start를 1증가시켜서 다시 비교해 나가는 방식으로 코드를 작성했다.

임시로 String을 저장해 놓고 중복된 문자가 있는 경우 기존 문자열(res)보다 큰 경우에 res에 저장하도록 했는데, 문제를 풀기는 했지만 속도와 메모리를 너무 많이 사용한다.

한번의 loop로 끝낼 수 있는 방법을 찾아서 다시 한번 해봐야겠다.

코드

class Solution {
	public int lengthOfLongestSubstring(String s) {
		String res = "";
		String tmp = "";
        
		int start = 0;
		int idx = 0;
        
		while(idx < s.length()) {
			if(start > idx) {
				break;
			}
			if(!tmp.contains("" + s.charAt(idx))) {
				tmp += s.charAt(idx++);
				if(tmp.length() > res.length()) res = tmp.toString();
				continue;
			}
			start++;
			idx = start;
			tmp = "";
		}
        
		return res.length();
	}
}

결과