[Leetcode] Remove Element / Maximum Subarray / Length of Last Word / Plus One / Valid Palindrome

Remove Element

오답 😔

def removeElement(self, nums: List[int], val: int) -> int:
    for i in range(len(nums)):
        if nums[i] == val:
            nums.pop(i)
    return len(nums)

• [IndexError]: pop() 과정에서 요소들이 하나씩 빠지면서 리스트의 길이가 짧아짐. for문이 리스트의 길이만큼 실행되기 때문에 인덱스 에러 발생.
  👉 해당 요소를 삭제하는 대신 다른 문자로 치환해서 for문을 마친 후 치환된 문자들을 제거하도록 코드 수정
  
  

정답 🥳

    def removeElement(self, nums: List[int], val: int) -> int:
        for i in range(len(nums)):
            if nums[i] == val:
                nums[i] = "x"
        while True:
            try: nums.remove("x")
            except: break	#ValueError 발생시 while문 빠져나감
        return len(nums)

remove(x)에서 x는 인덱스가 아닌 value가 들어가야 함!

다른 solution 😮

def removeElement(self, nums, val):
    try:
        while True:
            nums.remove(val)
    except:
        return len(nums)

이걸 보고 나니까 내가 쓴 코드가 바보같았다😩 굳이 val을 다른 값으로 치환하고 없앨 필요 없이 그냥 처음부터 val을 없애면 되는 거였는데....
+) try 안에 while True가 들어가는 형태도 신기함!

배운 것 💪✨

• pop([index]): 파라미터가 없으면 맨 마지막 요소를, 인덱스를 넣을 경우 해당 요소 리턴 후 제거함.

• remove(value): 리스트에서 해당 값을 가진 첫 번째 요소 제거. 해당 값을 가지는 모든 요소를 제거하려면 반복문을 활용해야 함!

• 오류 발생 전까지 반복시키는 코드

while True:
    try: ...
    except: break
return ...

try:
    while Ture:
except: return ...

Maximum Subarray

오답 😔

def maxSubArray(self, nums: List[int]) -> int:
    sums = []
    if len(nums) < 1:	#리스트 요소가 1개 이하이면
    	return: sum(nums)
    else:
        for i in range(len(nums)):
            if nums[i]<0: continue	#subarray의 시작점은 양수여야 함
            else:
                for l in range(i+1, len(nums)):	#시작점으로부터 만들 수 있는 모든 subarray를 테스트하기 위해
                    sums += [sum(nums[i:l])]	#subarray 요소 합 목록에 담기
        return max(sums)	#가장 큰 요소 합 추출

• [Wrong Answer] input=[5,4,-1,7,8]일 때 23이 아닌 15 리턴
  👉 why? range(x, y)와 list[x:y] 둘 다 y를 미포함하기 때문에 마지막 요소가 대입되지 않는 것 같다,.....
  분명 easy인데... 왤 케 어 려 워 ㅠ!?!????!??!!!?!
  
  

(다른사람이 푼) 정답 😮

def maxSubArray(self, nums: List[int]) -> int:
    for i in range(1, len(nums)):
        if nums[i-1] > 0:	#앞 수가 양수이면
            nums[i] += nums[i-1]	#뒷 수에 앞 수를 더해 줌
    return max(nums)

왼쪽에서부터 두 수의 합이 커지는 경우에만 연속적으로 더해서(음수가 되면 중단하고 다시 시작) 가장 큰 값을 리턴하도록 하는 방법

다른 solution

for i in range(1,len(nums)):
    nums[i] = max(nums[i], nums[i-1] + nums[i])
return max(nums)

원리는 위와 같음!
사고력을 기르기 위해 노력해야겠다 😔

Length of Last Word

오답 😔

def lengthOfLastWord(self, s: str) -> int:
    #두 단어 이상일 경우
    if len(s.split())>1:
        return len(s.split()[-1])
    #한 단어(+공백)일 경우
    elif s.isalpha(): return len(s)
    #단어가 없을 경우
    else: return 0

• [Wrong Answer] s.isalpha()로 "s에 문자(알파벳)가 있는 경우"를 표현하고 싶었지만... s.isalpha()는 "s내 모든 요소가 알파벳"일 때만 True였음
  👉 s.split()(=리스트)의 길이를 0, 1, 1이상인 경우로 수정
  
  

정답 🥳

def lengthOfLastWord(self, s: str) -> int:
    li = s.split()
    if len(li)>1:
        return len(li[-1])
    elif len(li)==1:
        return len(li[0])
    else: return 0

그런데...! li=1인 경우와 li>1인 경우를 하나로 합쳐도 되는 거였다. 리스트 요소가 1개일 때 인덱스로 -1을 호출하면 IndexError가 발생할 줄 알았는데, 그냥 인덱스 0인 값을 리턴해 줌.

다른 solution 😮

def lengthOfLastWord(self, s):
    return len(s.strip(' ').split(' ')[-1])

👉 split()와 split(' ')는 다르다!
" ".split()=[] 이지만 " ".split(' ')=['']

배운 것 💪✨

• s.isalpha(): s 요소가 모두 알파벳인 경우에만 True

• len(list) = 1일 때 list[-1] = list[0]

• .split(' ')
  • 공백이 연속되면 두 공백 사이에 '' 리턴
  • 문장 시작/끝에 공백이 있어도 '' 리턴 ▶ strip()/rstrip()/lstrip()을 쓰면 방지할 수 있음

예)
print("a  b  c".split())	#['a', 'b', 'c']
print("a  b  c".split(' '))	#['a', '', 'b', '', 'c']
print(" abc ".split(' '))	#['', 'abc', '']
print(" abc ".rstrip().split(' '))	#['', 'abc']

Plus One

정답 🥳

def plusOne(self, digits: List[int]) -> List[int]:
    digits[-1] += 1	
    for i in range(len(digits)-1, -1, -1):	
        if digits[i]==10:
            digits[i]=0
            if i!=0: digits[i-1]+=1
            else: digits.insert(0, 1)
    return digits

마지막 요소에 +1을 한 후 리스트 뒤에서부터 for문을 이용해 요소가 10인 경우 0으로 수정하고, 그 앞 요소에 +1. 만약 맨앞(인덱스 0) 요소가 10이면 0으로 수정하고 그 앞에 1이라는 요소를 새로 추가.

다른 solution 😮

def plusOne(self, digits):
    if len(digits) == 0:
        digits = [1]
    elif digits[-1] == 9:
        digits = self.plusOne(digits[:-1])
        digits.extend([0])
    else:
        digits[-1] += 1
    return digits	

👉 함수의 재귀(recursion)를 이용한 방법!
맨 마지막 요소가 9일 경우
1. 해당 요소를 뺀 리스트(digits[:-1])로 plusOne 함수 실행 ▶ 기존 함수의 뒤에서 두 번째 요소에 1을 더함
2. 그 후 리스트 마지막 요소로 0을 더해 줌 (extend([0]))
*9인 요소가 나올 때마다 plusOne 함수를 반복 실행해서 처리해 줌!

배운 것 💪✨

• 리스트 요소도 +=, -= 연산자 사용 가능

• 리스트 뒤에서부터 탐색하는 for문
  for i in range(list(len)-1, -1, -1):

• list.insert([위치], 삽입할 데이터) :순서 바뀌지 않게 주의!

• append() VS. extend()
  append는 요소를 통째로 추가하고, extend는 iterable한 요소를 나누어서 하나씩 리스트에 추가

list = ['a','b','c']
1. list.append(['d','e','f'])	#list=['a','b','c',['d','e','f']]
2. list.extend(['d','e','f'])	#list=['a','b','c','d','e','f']
3. list.append('def')		#list=['a','b','c','def']
4. list.extend('def')		#list=['a','b','c','d','e','f']

Valid Palindrome

오답 😔

def isPalindrome(self, s: str) -> bool:
    chars = [i for i in s if i.isalpha()]
    return chars == chars.reverse()

• [Wrong Answer] reverse()의 반환값은 리스트가 아닌 이터레이터
  👉 list()로 감싸줘야 함!

• 수정 후 ▶ 그래도 false... 대소문자 처리를 안 해서였다
  👉 .lower()함수 추가

• 수정 후 ▶ 그래도 false(ㅠ!!!) 문제를 다시 읽어보니 인풋 스트링에 숫자도 들어갈 수 있다고 함("alphanumeric characters")
  👉 if i.isalpha() or i.isdigit()으로 수정
  
  

정답 🥳

def isPalindrome(self, s: str) -> bool:
    chars = [i.lower() for i in s if i.isalpha() or i.isdigit()]
    return chars == list(reversed(chars))

다른 solution 😮

def isPalindrome(self, s: str) -> bool:
    s = s.lower()
    s = re.sub('[^a-z0-9]', '', s)
    return s == s[::-1]

👉 정규식의 치환기능으로 불필요한 문자 제거(a-z 또는 0-9가 아닌 것 -> '') 후 리스트 슬라이싱을 통해 비교

배운 것 💪✨

• list.reverse() VS. reversed(list)
  list.reverse()는 해당 리스트의 순서를 바꾸고(반환값 없음), reversed(list)는 바뀐 객체를 반환한다. 반환되는 객체는 리스트가 아닌 list_reversediterator이기 때문에 리스트 형식으로 출력하려면 list() 함수를 이용해야 함.

list = ['a', 'p', 'p', 'l', 'e']
list.reverse()		#list = ['e', 'p', 'p', 'l', 'a']
print(list.reverse())	#None
reversed(list)		#list = ['a', 'p', 'p', 'l', 'e']
print(reversed(list))	#<list_reverseiterator object at 0X7...>

• isalnum(): 알파벳 또는 숫자인지 검사하는 함수. isalpah() or isdigit()과 같음!

• re.sub('찾을 문자열(패턴)', '치환할 문자열', '전체 문자열')

풀리면 재밌고 안 풀리면 아주그냥 짱나는 알고리즘...^^ㅠ