FilesExpand file tree

 main

/

lylaminju.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

71 lines (58 loc) · 2.29 KB

 main

/

lylaminju.py

Top

File metadata and controls

• Code
• Blame

71 lines (58 loc) · 2.29 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

# encode 메서드:

# 시간 복잡도: O(N)

# - 각 문자열을 한 번씩 순회하며 길이와 내용을 처리하므로, 모든 문자열 길이의 합에 비례.

# 공간 복잡도: O(N)

# - 인코딩된 결과 문자열을 저장하기 위해 추가 공간 사용.

# decode 메서드:

# 시간 복잡도: O(N)

# - 인코딩된 문자열을 처음부터 끝까지 한 번 순회하며 파싱하므로, 입력 문자열 길이에 비례.

# - s.find('#', i)는 인덱스 i부터 다음 #를 찾음.

# - 여러 번의 find 호출이 있더라도 각 호출마다 전체 문자열을 다시 탐색하지 않고 이전 탐색 이후의 부분만 탐색하게 되어, 모든 find 호출을 합한 전체 탐색 거리는 인코딩된 문자열의 전체 길이 n에 해당함. 전체 시간은 O(n)에 수렴.

# 공간 복잡도: O(N)

# - 디코딩된 문자열 리스트를 구성하기 위해 추가 공간 사용.

class Solution:

"""

@param strs: a list of strings

@return: encodes a list of strings to a single string.

"""

def encode(self, strs):

encoded_str = ""

for s in strs:

encoded_str += (str(len(s)) + "#" + s)

return encoded_str

"""

@param s: A string

@return: decodes a single string to a list of strings

"""

def decode(self, s):

decoded_list = []

i = 0

while i < len(s):

j = s.find("#", i)

length = int(s[i:j])

i = j + 1

decoded_list.append(s[i:i + length])

i += length

return decoded_list

def main():

sol = Solution()

# 테스트 예시 1

input_strings1 = ["lint", "code", "love", "you"]

print("===== Example 1 =====")

print("Original: ", input_strings1)

encoded_str1 = sol.encode(input_strings1)

print("Encoded: ", encoded_str1)

decoded_list1 = sol.decode(encoded_str1)

print("Decoded: ", decoded_list1)

print()

# 테스트 예시 2

input_strings2 = ["1234567890a", "we", "say", "#", "yes"]

print("===== Example 2 =====")

print("Original: ", input_strings2)

encoded_str2 = sol.encode(input_strings2)

print("Encoded: ", encoded_str2)

decoded_list2 = sol.decode(encoded_str2)

print("Decoded: ", decoded_list2)

print()

if __name__ == "__main__":

main()