[Mock] Random 17

이거 3문제도 나오는 거였구나...

---

66. Plus One

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

My Answer 1: Accepted (Runtime: 32 ms - 63.91% / Memory Usage: 14.3 MB - 44.42%)

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        carry = 0
        ans = deque()
        
        if digits[-1] != 9:
            digits[-1] += 1
            return digits
        
        idx = 0
        for i in range(len(digits)-1, -1, -1):
            if digits[i] != 9:
                idx = i
                break
            if digits[i] == 9:
                digits[i] = 0
                carry = 1
        
        if idx != 0 or digits[idx] != 0:
            digits[idx] += 1
            return digits
        else:
            ans.appendleft(1)
            for i in range(len(digits)):
                ans.append(digits[i])
            return ans

우선 맨 마지막 값이 9 가 아니면 그냥 1 더해서 return

9 라면 digits 를 거꾸로 보면서 9 가 아닌 자리를 찾아감
그동안 9 들은 0 으로 바꿔줌
찾았을 경우, 그때의 인덱스 값이 맨 앞자리 & 값이 0 이 아니면 자릿수를 늘릴 필요가 없으므로 그냥 1 만 더해서 return
맨 앞자리 & 값이 0 이라면 자릿수를 늘려야 하므로 ans 에다 1 추가 후 나머지는 복사

---

833. Find And Replace in String

To some string s, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y. The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y. If not, we do nothing.

For example, if we have s = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string s, we will replace it with "ffff".

Using another example on s = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string s[2] = 'c', which doesn't match x[0] = 'e'.

All these operations occur simultaneously. It's guaranteed that there won't be any overlap in replacement: for example, s = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.

My Answer 1: Wrong Answer (30 / 52 test cases passed.)

class Solution:
    def findReplaceString(self, s: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
        ans = s
        length = 0
        
        for i in range(len(indexes)):
            for j in range(indexes[i]+1, len(s)+1):
                key = s[indexes[i]:j]
                if key in sources:
                    idx = sources.index(key)
                    length = len(targets[idx])
                    ans = ans.replace(key, targets[idx])
                    break
        
        return ans

s 에서 source 값인 key 값을 찾고 target 값으로 바꿔서 ans 에 적용

But... replace 를 해줬더니 중복되는 문자열이 있을 때, 해당 인덱스값이 아닌 다른 값까지 바뀌어서 안됨..

Solution 1: Accepted (Runtime: 64 ms - 6.57% / Memory Usage: 14.3 MB - 77.74%)

class Solution:
    def findReplaceString(self, s: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
        
        # indexes 를 기준으로 거꾸로 정렬
        for i, so, t in sorted(zip(indexes, sources, targets), reverse=True):
            s = s[:i] + t + s[i + len(so):] if s[i:i + len(so)] == so else s
            
        return s

indexes 를 기준으로 내림차순 정렬하면... 간단하게 풀리는 거였음;

if s[i:i + len(so)] == so else s => original 엔 없는 source 면 s = s

sources 값이 모두 s 에 포함된다는 것을 기억할 것..

---

56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

My Answer 1: Wrong Answer (15 / 168 test cases passed.)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ans = []
        tmp = []
        tmp2 = []
        
        for i in range(len(intervals)):
            if intervals[i][0] not in tmp:
                tmp2.append(intervals[i][0])
            for j in range(intervals[i][0], intervals[i][1]+1):
                if j not in tmp:
                    tmp.append(j)
        
        tmp.append(float('inf'))
        tmp.sort()
        prev = 1
        
        for i in range(len(tmp)-1):
            if tmp[i] + 1 != tmp[i+1] or tmp[i+1] in tmp2:
                ans.append([prev,tmp[i]])
                prev = tmp[i+1]
        
        return ans

그냥 tmp 리스트에 intervals 범위의 모든 값들을 저장
ex) [1,3] => 1,2,3 저장

그러고 정렬한 후에 연속이 끊기는 구간마다 잘라서 ans 에 추가

But.. [1,4] & [5,6] 처럼 겹치진 않지만 연속되는 경우는 처리가 안됨...

My Answer 2: Accepted (Runtime: 92 ms - 28.57% / Memory Usage: 16.2 MB - 9.17%)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        result = []
        
        for i in range(len(intervals)):
            if intervals[i][0] == -1:
                continue
                
            for j in range(i+1, len(intervals)):
                if intervals[j][0] == -1:
                    continue
                
                if intervals[i][0] <= intervals[j][0] and intervals[j][0] <= intervals[i][1]:
                    intervals[i][1] = max(intervals[i][1], intervals[j][1])
                    intervals[j][0] = -1
        
        for i in range(len(intervals)):
            if intervals[i][0] != -1:
                result.append(intervals[i])
        
        return result

이건 저번에 내가 푼 방식인데...

intervals 를 순서대로 정렬한 후,
intervals[i] 범위에 속하는 intervals[j] 값이 있으면 i 로 포함시킴
범위가 커져야 하는 경우는 intervals[i][1] 값을 intervals[j][1] 로 늘려줌
포함된 intervals[j] 의 [0] 값은 -1 로 바꿔준다.

맨 마지막에 [0] 이 -1 값이 아닌 값들만 result 에 넣어주고 리턴

이렇게 잘 풀었었는데... why... 점점 퇴화하는 것일까...^^