해보자

문제

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

문제

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

Input: s = "III"
Output: 3
Explanation: III = 3.

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

https://leetcode.com/problems/roman-to-integer

풀이

40, 90 등 5의 배수에서 빼는 것은 큰 문자 앞에 작은 문자가 오는 것에서 착안하여, 문자열 맨 뒤부터 이전 문자보다 큰 값일 경우 더하고 작은 값일 경우 빼는 형태로 진행했다.

코드

class Solution {
    public int romanToInt(String s) {
        char[] chars = s.toCharArray();
    	int result = 0;
    	int prevNum = 0;
    	
    	for(int i = chars.length-1; i >= 0; i--) {
    		int curNum = charToInt(chars[i]);
    		if(curNum >= prevNum) {
    			result += curNum;
    		} else {
    			result -= curNum;
    		}
    		prevNum = curNum;
    	}
		
        return result;
    }

    public int charToInt(char c) {
		int res = 0;
		switch (c) {
			case 'M':
				res = 1000;
				break;
			case 'D':
				res = 500;
				break;
			case 'C':
				res = 100;
				break;
			case 'L':
				res = 50;
				break;
			case 'X':
				res = 10;
				break;
			case 'V':
				res = 5;
				break;
			case 'I':
				res = 1;
				break;
		}
		return res;
	}
}

결과

Runtime : 3 ms

Memory Usage : 44.84 MB

문제

3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC as 500 (D) + 100 (C) + 100 (C)
  40 = XL as 10 (X) less of 50 (L)
   9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places

50 = L
 8 = VIII

1000 = M
 900 = CM
  90 = XC
   4 = IV

https://leetcode.com/problems/integer-to-roman

풀이

로마문자와 값을 큰 숫자부터 작은 숫자 순서로 배열에 넣어서, 큰 숫자부터 로마문자 변환하여 StringBuilder에 저장하도록 했다.

4나 9일 때만 빼는 형태로 작성해야 하니 검사할 값으로 나눈 몫이 4인지 체크했고, 큰 수부터 비교하기 때문에 9의 경우에는 이전에 5 형태의 숫자에서 몫 1과 나머지 4로 5에 대한 로마문자 이후 4가 있을거기 때문에 몫이 4인 경우에 이전 로마 문자와 StringBuilder에 저장된 마지막 로마문자가 같은 경우 9인 것으로 판단하도록 했다.

4xx나 4x와 같이 input이 4로 시작되는 숫자의 경우 9인지 체크할 때 아직 StringBuilder에 값이 없어서 에러가 날 수 있으니 , 5 형태의 숫자로 나눈 이후의 4인지의 체크하도록 StringBuilder에 문자가 있을 경우에 체크하도록 조건을 추가했다.

1000, 900, 500, 400, 100 처럼 사이에 4나 9로 시작하는 숫자들에 대한 내용도 추가하여, input 값에서 계속 빼면서 넣도록 진행한다면 속도를 더 줄일 수 있을 것 같지만, 문제의 제한사항인 input 4000 미만이 아닌  로마 숫자의 가로줄 대신 다른 형태로 큰 수 표현을 나타낼 수 있는 경우 자리수가 커질 수록 메모리 사용량이 증가하지 않을까 싶어 비교하면서 문자로 만들도록 진행해봤다.

코드

class Solution {
    public String intToRoman(int num) {
        char[] symbol = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
    	int[] value = {1000, 500, 100, 50, 10, 5, 1}; 
    	StringBuilder res = new StringBuilder();
    	
    	
    	for(int i = 0; i < value.length; i++) {
    		int check = num / value[i];
    		if(check == 4) {
    			if(res.length() > 0 && res.charAt(res.length()-1) == symbol[i-1]) {
    				res.deleteCharAt(res.length()-1);
    				res.append(symbol[i]).append(symbol[i-2]);
    			} else {    				
    				res.append(symbol[i]).append(symbol[i-1]);
    			}
    		} else {
    			for(int append = 0; append < check; append++) {
    				res.append(symbol[i]);
    			}
    		}
    		num %= value[i];
    	}
    	
        return res.toString();
    }
}

결과

Runtime : 3 ms

Memory Usage : 44.15 MB

문제

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

 

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

https://leetcode.com/problems/container-with-most-water

풀이

while문을 사용하여 양쪽에서 물 양을 비교하며 최대값만 저장하게끔 진행했다.

어차피 양쪽의 높이 중 낮은 높이에 따라 양이 결정되니, 이중 for문을 이용하여 전부 다 비교하기 보다는 높은 쪽을 고정해 두고 낮은 쪽만 움직이게끔 하는 것이 낫다고 생각했다.

코드

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int leftIdx = 0;
        int rightIdx = height.length - 1;
        
        while(leftIdx < rightIdx) {
        	int water = (rightIdx - leftIdx) * Math.min(height[leftIdx], height[rightIdx]);
        	max = Math.max(max, water);
        	if(height[leftIdx] < height[rightIdx]) {
        		leftIdx++;
        	} else {
        		rightIdx--;
        	}
        }
        
        return max;
    }
}

결과

Runtime : 5 ms

Memory Usage : 57.90 MB

문제

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

풀이

받은 문자열을 패턴과 비교하여 일치하면 다음 패턴을 검사하는 방식으로 진행해보았다.

'*'가 있을 경우 이전 문자와 비교해야 하므로, 우선 문자를 비교한 후 다음 패턴 문자에 '*'가 있는 경우 다음 글자를 현재 패턴 문자와 비교 + 다음 패턴을 비교하도록 했다.

재귀적으로 만들어서 지속적으로 비교하고 다음 패턴 및 문자 비교로 넘어갈 수 있도록 코드를 작성했다.

코드

class Solution {
    public boolean isMatch(String s, String p) {
        return isMatch(s, p, 0, 0);
    }

    private boolean isMatch(String s, String p, int textIdx, int patternIdx) {
    	if(patternIdx == p.length()) {
    		return textIdx == s.length();
    	}
    	
    	boolean checkFirstChar = (textIdx < s.length() && (s.charAt(textIdx) == p.charAt(patternIdx) || p.charAt(patternIdx) == '.'));
    	
    	if(patternIdx + 1 < p.length() && p.charAt(patternIdx + 1) == '*') {
    		return isMatch(s, p, textIdx, patternIdx + 2) || (checkFirstChar && isMatch(s, p, textIdx + 1, patternIdx));
    	} else {
    		return checkFirstChar && isMatch(s, p, textIdx + 1, patternIdx + 1);
    	}
    }
}

결과

Runtime : 472 ms

Memory Usage : 41.66 MB

문제

The underlined characters are what is read in and the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^

Step 1: "   -042" (leading whitespace is read and ignored)
            ^
Step 2: "   -042" ('-' is read, so the result should be negative)
             ^
Step 3: "   -042" ("042" is read in, leading zeros ignored in the result)
               ^

Step 1: "1337c0d3" (no characters read because there is no leading whitespace)
         ^
Step 2: "1337c0d3" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "1337c0d3" ("1337" is read in; reading stops because the next character is a non-digit)
             ^

Step 1: "0-1" (no characters read because there is no leading whitespace)
         ^
Step 2: "0-1" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "0-1" ("0" is read in; reading stops because the next character is a non-digit)
          ^

풀이

String과 long 2가지 방식으로 풀어보았다.

입력값이 String인 관계로 우선 String으로 구현했는데, 제약조건들을 맞추는데에는 숫자로 바로바로 판단하는게 좋을 것 같다고 생각해서 long으로도 구현해보았다.

String 보다는 숫자로 진행하는 것이 속도는 더 빨랐는데, 시간을 더 줄일 수 있는 방법은 아직 못찾았다.

입력값 "   +0 123"에 대해 출력이 0으로 나와야 하는 것으로 보아, 맨 앞 공백만 무시하면 될 것 같아서 split을 통해 공백을 제거한 후 진행해 봤으나 시간 소요가 더 컸다.(7ms)

어차피 확인할텐데 split을 위해 String을 뒤져보는데에 시간 소요가 더 있었던 것으로 보인다.

코드

String으로 진행

class Solution {
    public int myAtoi(String s) {
        StringBuilder sb = new StringBuilder();
		int res = 0;
		char[] signed = new char[] {' '};
		
		for(char c : s.toCharArray()) {
			if(c == ' ') {
				if(sb.length() != 0 || signed[0] != ' ') {
					break;
				}
				continue;
			}
			if(c == '-' || c == '+') {
				if(sb.length() != 0 || signed[0] != ' ') {
					break;
				}
				signed[0] = c;
				continue;
			}
			if(Character.isDigit(c)) {
				sb.append(c);
			} else {
				break;
			}
		}
		
		if(sb.length() != 0) {
			try {		
				res = (signed[0] == '-')? Integer.parseInt(sb.toString()) * -1 : Integer.parseInt(sb.toString());
			} catch(NumberFormatException e) {
				res = (signed[0] == '-')? Integer.MIN_VALUE : Integer.MAX_VALUE;
			}
		}
		
        return res;
    }
}

숫자로 진행

class Solution {
    public int myAtoi(String s) {
        String input = s.trim();
		int idx = 0;
		int signed = 1;
		long res = 0;
		
		if(input.isEmpty()) {
			return 0;
		}
		
		if(input.charAt(idx) == '-' || input.charAt(idx) == '+') {
			signed = (input.charAt(idx++) == '-')? -1 : 1;
		}
		
		while(idx < input.length() && Character.isDigit(input.charAt(idx))) {
			res = (res * 10) + Character.getNumericValue(input.charAt(idx++));
			if(res > Integer.MAX_VALUE) {
				return (signed == -1)? Integer.MIN_VALUE : Integer.MAX_VALUE;
			}
		}
				
        return (int) res * signed;
    }
}

결과

String 진행 : runtime 3ms, memory 42.88MB

숫자로 진행 : runtime 2ms / memory 42.36MB

문제

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range  [-2^31, 2^31 - 1] , then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Constraints:

• -2^31 <= x <= 2^31 - 1

https://leetcode.com/problems/reverse-integer

풀이

숫자 순서를 바꾸는 거에 대해, String으로 변환하여 reverse 시키는 방법과 숫자 그대로 진행하는 방식 2가지로 진행해보았다.

문제를 보고 처음 들었던 생각이 '순서'를 바꾸는거라 String으로 푸는 방법이 생각났는데, 진행하다보니 숫자의 마지막을 계속해서 자리수를 높혀가면 될 것 같아서 int로도 코드를 짜보았다.

int의 경우 1의 자리의 수를 저장 후 10으로 나눠서 저장한 1의 자리의 수 삭제 및 다음 1의 자리의 수를 만들고, 저장할 변수는 게속해서 10을 곱해주면서 1의 자리의 수를 저장할 수 있도록 했다.

10으로 더이상 나눌 값이 없어지면 0이 나올거기 때문에 while(x != 0)을 통해 입력값의 자리수만큼 진행하도록 했다.

중간에 생겼던 문제로는 제한사항(-2^31 <= x <= 2^31 - 1)을 맞추는 것 이었는데,

String의 경우 'NumberFormatException'의 integer 파싱 에러가 발생하여 단순히 try catch로 처리할 수 있었던 반면에 int의 경우 범위를 넘어가는 경우 에러가 없었기 때문에 방안을 생각하는데 코딩 시간 소요가 컸다.

이에 대한 해결으로 저장용 변수 값의 이전 값이 실제 이전 값과 동일한가에 대한 체크를 진행했는데, int 범위를 넘어서면 Integer.MIN_VALUE(-2^31)나 Integer.MAX_VALUE(2^31-1)부터 시작될거기 때문에 실제 이전 값이 나오지 않을거라 생각했다.

코드

StringBuilder를 통한 reverse를 통해 진행한 방법

class Solution {
    public int reverse(int x) {
        int res = 0;
		
        StringBuilder sb = new StringBuilder(Integer.toString(x));
        sb = sb.reverse();
        if(x < 0) {
            sb.insert(0, '-');
            sb.deleteCharAt(sb.length() - 1);
        }
		
        try {
            res = Integer.parseInt(sb.toString());
        } catch (NumberFormatException e) {
            return 0;
        }
        return res;
    }
}

1의 자리 숫자 지속 계산을 통해 진행한 방법

class Solution {
    public int reverse(int x) {
        int res = 0;
        int next = 0;
		
        while(x != 0) {
            next = (res * 10) + (x % 10);
			
            if((next - (x % 10)) / 10 != res) {
                return 0;
            }
			
            x /= 10;
            res = next;
        }
				
        return res;
    }
}

결과

String 진행 : runtime 2ms, memory 40.99MB

int 진행(1의 자리수) : runtime 0ms / memory 40.74MB

개인적으로 StringBuilder의 reverse를 사용하게 되면 시간이 더 빠를 줄 알았는데, 양끝 swap을 위한 index 계산이랑 swap하는데 시간이 더 걸리는건가 싶다...

문제

https://leetcode.com/problems/zigzag-conversion/description/

풀이

문제 설명 그대로 구현했다.

String 형태의 문자 관리가 필요하기에 StringBuilder를 배열 형태로 이용하여 메모리 사용량을 줄이고, append하여 쉽게 구현 가능했다.

다만 문자 수가 열 수보다 작거나 열 수보다 문자 수가 작은 등의 예외 처리에 신경써야 했다.

코드

class Solution {
    public String convert(String s, int numRows) {
        if(s.length() < numRows) {
        	numRows = s.length();
        }
        
        StringBuilder[] temp = new StringBuilder[numRows];
        boolean order = true;
        int idx = 0;
		
        for(int i = 0; i < s.length(); i++) {
        	
        	if(temp[idx] == null) {
        		temp[idx] = new StringBuilder();
        	}
        	
        	temp[idx].append(s.charAt(i));
        	
        	if(idx >= numRows - 1) {
        		order = false;
        	} else if(idx <= 0) {
        		order = true;
        	}
        	
        	idx += order? 1 : -1;
        	if(idx < 0) { 
        		idx = 0;
        	}
        	
        }
        
        for(int i = 1; i < temp.length; i++) {
        	temp[0].append(temp[i].toString());
        }
        
		
		return temp[0].toString();
    }
}

결과