코딩 인터뷰 준비

Coding
Coding, Interview, Python

코딩 인터뷰 준비

##문제 1

66.Plus One

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

1 <= digits.length <= 100
0 <= digits[i] <= 9
digits does not contain any leading 0's.

Solution

배열로 숫자가 전해지고 단순히 1을 더하여 그 결과의 숫자를 다시 배열로 내보내는 것.
배열을 숫자로, 숫자를 배열로 바꾸는 방법을 물어보는 듯했다.
나는 리스트의 전체 크기를 보고 몇자리수까지 채워지는지 보고, 10의 n승을 곱하면서 숫자를 만들어주고 작업을 진행했다.

1
2
3
4
5
6
7
8
9
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        sum = 0
        length = len(digits)-1
        for i, d in enumerate(digits):
            sum += d*10**(length-i)
        sum+=1
        result = list(map(int, str(sum)))
        return result

map을 어떻게 활용하는지 좀 헷갈린다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 리스트에 값을 하나씩 더해서 새로운 리스트를 만드는 작업
myList = [1, 2, 3, 4, 5]

# for 반복문 이용
result1 = []
for val in myList:
    result1.append(val + 1)

print(f'result1 : {result1}')


# map 함수 이용
def add_one(n):
    return n + 1


result2 = list(map(add_one, myList))  # map반환을 list 로 변환
print(f'result2 : {result2}')

함수의 동작은 두 번째 인자로 들어온 반복 가능한 자료형 (리스트나 튜플)을 첫 번째 인자로 들어온 함수에 하나씩 집어넣어서 함수를 수행하는 함수입니다.

출처: https://blockdmask.tistory.com/531 [개발자 지망생:티스토리]

내가 이렇게 할 수도 있지 않을까라고 해서 찾아본 솔루션.
각각 곱하기 더하기를 해주는 것으로 배열을 숫자로 가져오는 것이 아닌
더 단순한 방법으로 배열을 숫자로 가져오는 방법.

1
2
3
4
5
6
7
8
9
class Solution:
    def plusOne(self, digits):
        strings = ""
        for number in digits:
            strings += str(number) # digits안에 있는 숫자들을 str화 하여 빈 string안에 넣어주고

        temp = str(int(strings) +1) # int로 잠깐 변환시켜 준 후 +1을 해준뒤

        return [int(temp[i]) for i in range(len(temp))] # str들을 int 배열로 바꾼 뒤 리턴.

금방 풀 수 있었지만 조금 아쉬웠던 문제

하지만 이 문제에서 시간을 시간 정도 쏟아부었음에도 세번째 에러 케이스는 해결하지 못했다.
그 원인도 찾아보지 못함. 아마 내 알고리즘에서의 문제였을 것임.

##문제 2

833. Find And Replace in String)
Medium

You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.

To complete the ith replacement operation:

Check if the substring sources[i] occurs at index indices[i] in the original string s.
If it does not occur, do nothing.
Otherwise if it does occur, replace that substring with targets[i].

For example, if s = “abcd”, indices[i] = 0, sources[i] = “ab”, and targets[i] = “eee”, then the result of this replacement will be “eeecd”.

All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.

For example, a testcase with s = "abc", indices = [0, 1], and sources = ["ab","bc"] will not be generated because the "ab" and "bc" replacements overlap.

Return the resulting string after performing all replacement operations on s.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = “abcd”, indices = [0, 2], sources = [“a”, “cd”], targets = [“eee”, “ffff”]
Output: “eeebffff”
Explanation:
“a” occurs at index 0 in s, so we replace it with “eee”.
“cd” occurs at index 2 in s, so we replace it with “ffff”.

Example 2:

Input: s = “abcd”, indices = [0, 2], sources = [“ab”,”ec”], targets = [“eee”,”ffff”]
Output: “eeecd”
Explanation:
“ab” occurs at index 0 in s, so we replace it with “eee”.
“ec” does not occur at index 2 in s, so we do nothing.

Constraints:

1 <= s.length <= 1000
k == indices.length == sources.length == targets.length
1 <= k <= 100
0 <= indexes[i] < s.length
1 <= sources[i].length, targets[i].length <= 50
s consists of only lowercase English letters.
sources[i] and targets[i] consist of only lowercase English letters.

Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import copy
import re

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        result = ''
        new_s = copy.deepcopy(s)
        for i, c in enumerate(sources):
            l = []
            for z in re.finditer(c,s):
                l.append(z.start())
            if len(l) > 1:
                for n in l:
                    if n not in indices:
                        l.remove(n)
            if c in s:
                if l[0] in indices:
                    new_s = new_s.replace(sources[i], targets[i])
        return new_s

어떻게든 문제를 풀어가는 쪽으로 알고리즘을 짜다보니까 처음에 생각했던대로 코딩이 되지 않았다.
원래 문자열에서 시키는 대로 대체 시키고, 변화되지 않은 것들을 지우고 착실히 해나갔어야 했는데..
문제 조건을 제대로 읽지 못해서 indices, sources, targets의 길이가 항상 같다는 것도 못 알아챘다.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findReplaceString(self, S, indices, sources, targets):
        """
        :type S: str
        :type indexes: List[int]
        :type sources: List[str]
        :type targets: List[str]
        :rtype: str
        """

        modified = list(S)
        for index, source, target in zip(indices, sources, targets):
            if not S[index:].startswith(source):
                continue
            else:
                modified[index] = target
                for i in range(index+1, len(source) + index):
                    modified[i] = ""

        return "".join(modified)

modified라는 배열을 하나 만들어 준다음,
모든 길이가 같은 indices, sources, targets를 같이 써주면서 modified를 철저하게 바꿔나갔다.

조건까지는 나도 초반에는 써봤지만, 감을 잃었던 것 같다.
1
2
3
4
5
아무튼 ```modified[index] = target```까지는 바로 이해가 갔는데, 

```python
for i in range(index+1, len(source) + index):
  modified[i] = ""

가 잘 이해가 안 간다.
modified가 리스트니까, index부분을 targets로 바꿔준 뒤, modified[index+1]의 부분에 d가 남아있으면 안되기 때문에 source의 length만큼 “”빈칸으로 처리해준 것..
소스를 보면 바로 이해가 가지만, 저런 처리방법을 생각하지 못했다. 습득하기.

Share 0 Comments