절대 arr = [[0]*n]*n으로 초기화 X

출처 : https://zetawiki.com/wiki/%ED%8C%8C%EC%9D%B4%EC%8D%AC_join()

▶ 출처 : https://ourcstory.tistory.com/414

▶ 출처 : https://lar542.github.io/Python/2019-07-11-python2/

▶ re.findall

# re.findall(pattern, string) : 매칭되는것들을 배열로 리턴 

import re

inputString = 'aa1b2c3' 

# []: []사이의 문자들과 매칭 
p = '[a-zA-Z]'
result = re.findall(p, inputString)
print(result) # ['a', 'a', 'b', 'c']

# .은 \n을 제외한 모든 문자와 매치 
p = 'a.1'
result = re.findall(p, inputString)
print(result) # ['aa1']

p = '[0-9]'
result = re.findall(p, inputString)
print(result) # ['1', '2', '3']

st = '\d'
p = re.compile(st) 
result = re.findall(p, inputString)
print(result) # ['1', '2', '3']

p = '[^0-9]'
result = re.findall(p, inputString)
print(result) # ['a', 'a', 'b', 'c']

p = '[a-zA-Z0-9]'
result = re.findall(p, inputString)
print(result) # ['a', 'a', '1', 'b', '2', 'c', '3']

p = '\w'
result = re.findall(p, inputString)
print(result) # ['a', 'a', '1', 'b', '2', 'c', '3']



inputString = 'ct'

# *은 * 바로 앞에 있는 문자 a가 0부터 무한대로 반복될 수 있다는 의미이다.
p = 'ca*t'
result = re.findall(p, inputString)
print(result) # ['ct']

# +는 최소 1번 이상 반복될 때 사용한다. 즉 *가 반복 횟수 0부터라면 +는 반복 횟수 1부터인 것이다.
p = 'ca+t'
result = re.findall(p, inputString)
print(result) # []



inputString = 'caat'

# {2} : 반드시 2번 반복
p = 'ca{2}t'
result = re.findall(p, inputString)
print(result) # ['caat']

# {2,5} : 2~5번 반복
p = 'ca{2,5}t'=
result = re.findall(p, inputString)
print(result) # ['caat']



inputString = 'ac'

# ? : 있어도 되고 없어도 된다
p = 'ab?c'
result = re.findall(p, inputString)
print(result) # ['ac']

▶ re.sub

# re.sub(pattern, repl, string) : string에서 pattern과 매치하는 텍스트를 repl로 치환한다

# 문제) 
# aabbbca -> ['aa', 'bbb', 'c']         -> 2a3bc
# aabbbca -> ['aa', 'bbb', 'c', 'a']    -> 2a3bca
# abbcabb -> ['a', 'bb', 'c', 'a', 'bb']      -> a2bca2b

# 풀이)
import re

inputString = 'aabbbca'

p = r'(.)(\1+)'
repl = lambda c: str(len(c.group())) + c.group(1)

result = re.sub(p, repl, inputString)

print(result) # 2a3bca

# r : Raw String. 컴파일해야하는 정규식이 'Raw String'임을 알려줌 
# 괄호()를 써서 묶은 부분은 '1번부터 시작하는 그룹'으로 참조할 수 있다.
  (.)	-> 1번 그룹 
# 앞서 매치한 그룹을 '패턴 내에서 재사용'하려면 \1과 같이 그룹번호를 역슬래시로 이스케이프하여 표현한다. 

▶ re.match

# re.match(pattern, string) : string에서 pattern과 매치하는 텍스트를 탐색한다

# 문제) 
# MAC Address는 항상 0~9,A~F사이의 값으로만 2개씩 총 6묶음으로 이루어져 있다. 
# MAC Address는 항상 똑같은 형식, 똑같은 길이를 갖는다.

# 풀이)
import re

inputString = "00-1B-63-84-45-E6"

p = '^([\dA-F]{2}-){5}([\dA-F]{2})$'

result = bool(re.match(p, inputString))
print(result) # True

# \d : 숫자를 나타냄
# {2} : 반드시 2번 반복 
# ^ : 문자열의 처음
# $ : 문자열의 끝 
# 문자열 처음 ~ 끝 지정해주는 이유 ? : 무조건 여기서 범위는 문자열의 처음~끝 으로 고정으로 해야 예외가 안생김

lst = ['1', '2', '3']

lst = list(map(lambda x: int(x), lst))

print(lst) # [1,2,3]

▶ 출처 : https://www.youtube.com/watch?v=rI8NRQsAS_s

문제1) 배열의 특정 연속된 구간을 처리하는 경우 ( 시간제한: O(n) )

ex) [1,2,3,2,5]중에서 합이 5인 '연속 수열의 개수'를 구하는 문제 

▶ 투 포인터를 활용한 알고리즘 코드

# 데이터 개수:n, 부분연속수열의 합: m
n = 5
m = 5
data = [1,2,3,2,5]

start = 0
end = 0
result = 0
sum_val = data[0]

end_flag=0 # end는 범위를 넘어버릴 가능성이 있으므로 while조건 체크후, flag체크후 sum_val 늘려주기

while start < n and end < n:

    if end_flag == 1:
        sum_val += data[end]
        end_flag=0

    print(start, end, sum_val)

    if sum_val < m:
        end += 1
        end_flag = 1
    elif sum_val > m:
        sum_val -= data[start]
        start += 1
        start_flag = 1
    elif sum_val == m:
        print('>>find!')
        result += 1
        end += 1
        end_flag = 1

print(result)

'''
n, m = 5, 5 # 데이터 개수:n, 부분연속수열의 합: m
data = [1,2,3,2,5]

result = 0
sum_val = 0
end = 0

for start in range(n):
    # end를 가능한 만큼 이동시키기
    while sum_val < m and end < n:
        sum_val += data[end]
        end += 1
    # 부분합이 정확히 m일때 카운트 증가
    if sum_val == m:
        result += 1
        print('현재 인덱스: start, end=', start, end)

    # 다음 start넘어가기 전에 data[start]를 sum_val에서 빼주기 
    sum_val -= data[start]

print(result)
'''

문제2) 구간 합 빠르게 계산하기 ( 시간제한: O(n+m) )

ex) [10,20,30,40,50]에서 Left와 Right정보가 들어왔을때 구간합 계산하기

▶ Prefix Sum을 활용한 알고리즘 코드

n = 5 # 데이터 개수:n
data = [10,20,30,40,50]

# Prefix Sum 배열 계산후 저장
sum_val = 0
prefix_sum = [0]
for a in data:
    sum_val += a
    prefix_sum.append(sum_val)

# left = 2, right=4 일때 구간 합 계산 ?
left = 2
right = 4

print(prefix_sum[right] - prefix_sum[left-1])