'leetcode'에 해당되는 글 2건

LeetCode의 문제와 유저들이 등록한 코드 중 득표수가 가장 높은 코드 분석

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

단어 사전에 저장된 단어들을 조합하여 주어진 String을 만들 수 있는지 여부 확인

Note:

• The same word in the dictionary may be reused multiple times in the segmentation. 단어 사전에 있는 단어는 중복해서 사용 가능
• You may assume the dictionary does not contain duplicate words. 단어 사전에는 중복된 단어들이 저장되어있지 않음

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]

Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

"leetcode"는 "leet code"로 만들어질 수 있으므로 true

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]

Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".   Note that you are allowed to reuse a dictionary word.

"applepenapple"는 "apple pen apple"로 만들어질 수 있으므로 true (apple 중복 사용)

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

Output: false

"catsandog"는 단어 사전에 있는 단어의 조합으로는 만들어질 수 없으므로 false

class Solution {
     public static boolean wordBreak(String s, List<String> wordDict) {

        Set<String> helper = new HashSet(wordDict);
        int[] cache = new int[s.length()];
        Arrays.fill(cache, -1);

        int longestWord = 0;

        for (String word : wordDict) {
            if (word.length() > longestWord) {
                longestWord = word.length();
            }
        }

        return wordBreak(s, 0, helper, cache, longestWord);
    }

    private static boolean wordBreak(String s, int start, Set<String> wordDict, int[] cache, int lw) {
        if (start >= s.length()) {
            return true;
        }

        if (cache[start] != -1) {
            return cache[start] == 0 ? false : true;
        }

        boolean result = false;

        for (int i = start; i < start + lw && i < s.length(); i++) {
            if (wordDict.contains(s.substring(start, i + 1))) {
                result = wordBreak(s, i + 1, wordDict, cache, lw);
            }
            if (result) {
                break;
            }
        }

        cache[start] = result ? 1 : 0;

        return result;
    }
}

풀이 방법

1. 주어진 String를 처음 문자부터 잘라내어 단어 사전에 포함된 단어인지 있는지를 체크하고 없다면 잘라낼 문자의 수를 증가시킨다. 

 - 주어진 String이 catsandog 인 경우 c, ca, cat, cats, 단어 사전에 와 같이 문자를 잘라내어 단어 사전에서 검색

2. 단어가 사전에 포함되어있는 경우

 - 문자를 만드는 시작점을 변경하여 다시 사전에서 검색한다. 

 - s = "catsandog", wordDict = ["dog", "sand", "cat"]인 경우 cat 이 사전에 있으므로 시작점은 cat의 다음인 s로 변경한다.

코드 동작 확인

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

1. 문자를 조합할 때 단어장에서 가장 긴 단어의 길이를 초과할 필요가 없으므로 단어 사전에서 가장 긴 단어의 길이를 구한다. 

2. 한번 계산한 결과를 저장할 배열을 생성하고 초기값을 -1로 설정한다.

3. 주어진 String를 이용하여 단어를 만들어가며 단어 사전에 포함되어 있는지 확인한다.

초기값: start = 0, cache = [-1, -1, -1,-1, -1, -1,-1, -1, -1], lwlongestWord =  4

1차 사전에 포함된 단어 확인

start = 0 

i = 2

substring = "cat"

start = 3

i = 6

substring = "sand"

cache [3] = 0

start = 7

i = 8

substring = "og"

cache [7] = 0

1차 검색 실패로 2차 검색 시작

start = 0

i = 3

substring = "cats"

start = 4

i = 6

substring = "and"

start = 7

cache [7]에 결과가 저장되어 있으므로 해당 값으로 false 반환

2차 검색 실패로 3차 검색 시작

start = 0

i = 4

substring = "catsa"

만들어진 단어의 길이가 단어 사전에서 가장 긴 단어보다 길어 검색을 종료

단어 사전에 있는 단어의 조합으로 만들어 낼 수 없으므로 false를 반환

LeetCode의 문제와 유저들이 등록한 코드 중 득표수가 가장 높은 코드 분석

Given a collection of intervals, merge all overlapping intervals.

시작점과 끝점이 있는 숫자 쌍의 리스트 중 겹치는 부분이 있는 것을 병합하기

Example 1:

Input: [[1,3], [2,6], [8,10], [15,18]]

Output: [[1,6], [8,10], [15,18]]

Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

[1,3]과  [2,6] 은 [1,6]로 병합

Example 2:

Input: [[1,4], [4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

[1,4]과 [4,5]는 [1,5]로 병합

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1)
            return intervals;
            
        // Sort by ascending starting point
        Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[0]));

        List<int[]> result = new ArrayList<>();
        int[] newInterval = intervals[0];
        result.add(newInterval);
        for (int[] interval : intervals) {
            if (interval[0] <= newInterval[1]) // Overlapping intervals, move the end if needed
                newInterval[1] = Math.max(newInterval[1], interval[1]);
            else {                             // Disjoint intervals, add the new interval to the list
                newInterval = interval;
                result.add(newInterval);
            }
        }

        return result.toArray(new int[result.size()][]);
    }
}

풀이 방법

1. intervals 배열을 시작점이 작은 순서대로 정렬한 뒤 처음에 위치한 숫자 쌍을 기준값으로 설정한다. 

2. intervals 배열을 반복문을 돌면서 나오는 숫자 쌍의 시작점과 기준값의 종료점을 비교한다. 

3. 값의 비교

  3-1.  기준값의 종료점이 더 크거나 같은 경우

    - 범위가 겹치는 경우 이므로 종료점이 더 큰 것을 추출하여 기준값을 재정의 한다. 

    - ex) 기준값: [1,2], 비교대상 [1,3]인 경우

  3-2. 기준값의 종료점이 더 작은 경우

    - 범위가 겹치지 않는 경우 이므로 기준값과 비교한 숫자 쌍을 새로운 기준값으로 정의하고 결괏값을 저장하는 리스트에도 추가한다.

    - ex) 기준값: [1,6], 비교대상 [14,16]인 경우

코드 동작 확인

Input: [[2,6], [1,3], [8,10], [15,18]]

1. intervals 배열을 시작점이 작은 순서대로 정렬

- [[2,6], [1,3], [8,10], [15,18]][1,3], => [[1,3], [2,6], [8,10], [15,18]]

2. 결괏값을 담을 리스트를 생성 후 정렬한 intervals 배열의 처음에 위치한 값으로 설정

- [[1,3]]

3. intervals 배열을 루프 돌면서 엘리먼트들의 시작점이 기준값의 끝점보다 작거나 같은지 비교

최초

> newInterval = [1,3]

> intervals =  [[1,3], [2,6], [8,10], [15,18]]
> result = [[1,3]]

루프 1차 비교 

> newInterval = [1,3]

> interval =  [1,3]

> result = [[1,3]]

[1] <= [3]   interval의 시작점이 newInterval의 끝점보다 작기 때문에 newInterval [1] = Math.max(3, 3) 

> newInterval = [1,3]으로 변화 없음

루프 2차 비교 

> newInterval = [1,3]

> interval =  [2,6]

> result = [[1,3]]

[2] <= [3]   interval의 시작점이 newInterval의 끝점보다 작기 때문에 newInterval [1] = Math.max(3, 6) 

> newInterval = [1,6]

> result = [[1,6]]

루프 3차 비교 

> newInterval = [1,6]

> interval =  [8,10]

> result = [[1,6]]

[8] <= [6]  interval의 시작점이 newInterval의 끝점보다 크기 때문에 newInterval =  [8,10]

> newInterval = [8,10]

> result = [[1,6][8,10]]

루프 4차 비교 

> newInterval = [1,10]

> interval =  [15,18]

> result = [[1,6][8,10]]

[15] <= [10]   interval의 시작점이 newInterval의 끝점보다 크기 때문에 newInterval [1] = Math.max(10, 18) 

> newInterval = [1,10]

> result = [[1,6][8,10], [15,18]]

종료