[Lint Code] Split String

문제 : 문자열이 주어졌을 때 한 개의 문자 혹은 두 개의 문자로 구성된 문자열들로 구성할 수 있는 전체 경우를 구하시오

[예시]

Input -> "123"
 
Output -> [["1", "2", "3"], ["12", "3"], ["1", "23"]]

[풀이]

이 문제는 [start:start+1]과 [start:start+2]의 경우를 DFS를 이용하여 모든 경우의 수를 탐색하여 풀면 된다.

[코드]

class Solution:
    """
    @param: : a string to be split
    @return: all possible split string array
    """
 
    def func(self, s, start, end, row, matrix):
        # 기저사례: end가 문자열 s의 길이면 matrix 배열에 추가 후 종료
        if(end == len(s)):
            matrix.append([])
            for i in range(len(row)):
                matrix[len(matrix)-1].append(row[i])
            return
 
        # end+1이 len(s) 보다 작다면 : case one character
        if end+1 <= len(s):
            # s[end:end+1]를 row에 추가후 재귀호출
            row.append(s[end:end+1])
            self.func(s, end, end+1, row, matrix)
            # s[end:end+1]에 값을 row 배열에서 pop
            row.pop(len(row)-1)
 
        # end+2이 len(s) 보다 작다면 : case two character
        if end+2 <= len(s):
            # s[end:end+2]를 row에 추가후 재귀호출
            row.append(s[end:end+2])
            self.func(s, end, end+2, row, matrix)
 
    def splitString(self, s):
        # write your code here
 
        matrix = []
 
        row = []
 
        # s의 문자열의 길이가 1개이상일 경우 s[0]번째를 row에 넣고 재귀함수 호출 시작
        if len(s) >= 1:
            row.append(s[0:1])
            self.func(s, 0, 1, row, matrix)
 
        # s의 문자열의 길이가 2개이상일 경우 s[0]과 s[1]이 합쳐진 문자열을 row에 넣고 재귀함수 호출 시작
        if len(s) >= 2:
            row = []
            row.append(s[0:2])
            self.func(s, 0, 2, row, matrix)
 
        return matrix
 

list 클래스

파이썬에서 연속적인 데이터를 저장하기 위해 사용하는 클래스이다.

클래스 생성 방법으로는 아래와 같다.

1. list1 = list()

2. list1 = []

3. list2 = list([2,3,4,])

4. list2 = [2,3,4]와 동일

5. list3 = list(["red", "green", "blue"])

6. list3 = ["red", "green", "blue"]

7. list4 = list(range(3, 6))

8. list5 = list("abcd")

list 슬라이싱 [start: end: step]

list 슬라이싱을 이용하여 문자열 추출을 쉽게 할 수 있다.

list1 = [4,2,9,1,32]
 
list1[1:4] // [2, 9, 1]

연결 연산자, 반복 연산자, in/not in

>>> list1 = [4,2,9,1,32]
 
>>> list2 = [3, 3]
 
>>> list1 + list2 // [4, 2, 9, 1, 32, 3, 3]
 
>>> list2 * 3 // [3, 3, 3, 3, 3, 3]
 
>>> 4 in list2 // False
 
>>> 3 not in list2 // False
 
>>> 1 in list1 // True

리스트 복사

파이썬에서 아래와 방식으로 리스트를 복사하게 되면 참조가 된다.

list1 = [1,2]
 
list2 = list1
 
list1[0] = 3
 
//list1과 list2 모두 [0] 번재 원소가 3으로 변경된다.
print(list1, list2)

따라서 리스트를 복사할 때는 아래의 2가지 방법을 이용할 수 있다.

익명 배열에다가 원소를 넣어서 대입하므로 참조가 일어나지 않는다.

list2 = [x for x in list1]
 
list2 = [] + list1

아래의 예시를 보면서 참조에 대한 이해를 해보자

def main():
    x = 1 # x는 int 변수이다.
    y = [1, 2, 3] # y는 리스트이다.
 
    m(x, y) # x, y 인자를 사용하여 m을 호출한다.
 
    print("x is", x) // 1
    print("y[0] is", y[0]) // 5555
 
def m(number, numbers):
    number = 1001
 
    numbers[0] = 5555
 
main()

number와 같은 일반 변수는 참조가 일어나지 않지만 리스트는 참조가 일어남을 확인할 수 있다.