오늘부터 알고리즘 주차를 시작했다
제대로 알고리즘을 배운게 아마 5년전인거 같다.
5년만에 새로운 언어를 이용해 새롭게 배우려 하니 머리속이 하해진다.
머리속이 이리저리 복잡해 지면서 꼬이는 걸 보면 내 노력이 충분하지 않았는 듯 하다.
[알파벳]
text = list(input())
result = [-1]*len(string.ascii_lowercase)
for i in range(len(text)):
textIndex = ord(text[i])-97
if result[textIndex] == -1 :
result[textIndex] = i문자에 대한 순서 처리시 아스키 코드를 사용하면 간편하다는 것을 배웠다.
앞으로 자주 쓰게 될 것 같은 .join에 대해서도 숙지를 해야겠다.
[그룹 아나그램]
def groupAnagramsDict(self, strs: List[str]) -> List[List[str]]:
anagrams = collections.defaultdict(list)
for word in strs:
anagrams[''.join(sorted(word))].append(word)
return list(anagrams.values())collections에 존재와 딕셔널리에 기본값을 지정하는 것을 몰라서 고생을 했다.
또한 딕셔널리에서 list를 넣고 꺼낼시 속성에 접근을 하지 못했다.
예를 들어
list_dict["test"] = list_dict["test"].append("내용")딕셔널리 안에 밸류가 list를 넣어놔서, list_dict["test"]로 접근한뒤 .을 찍고 append로 기능을 호출하려 했지만 잘 되지 않았다.
[가장 긴 팰린드롬]
def longestPalindromeExpand(self, s: str) -> str:
# 팬린드롬 판별 및 투 포인터 확장
def expand(left: int, right: int) -> str:
while left >=0 and right <len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]
# 해당 사항이 없을 때 빠르게 리턴
if len(s) < 2 or s == s[::-1]:
return s
result = ''
# 슬라이딩 윈도우 우측으로 이동
for i in range(len(s) - 1):
result = max(result, expand(i, i + 1), expand(i, i+2), key=len)
return result짝수와 홀수를 동시에 고려하다보니 for문이 중첩되고 난잡해졌었음
예시를 보니 별도 함수로 선언한 뒤, 단순히 이동값을 +2해주는 것으로 해결 가능했음
별도 모듈을 선언하고 호출하는 점을 배웠음
그리고 포인트의 이동에 대한 이해를 좀더 배웠음[세가지 수]
def threeSum2Pointer(self, nums: List[int]) -> List[List[int]]:
results = []
nums.sort()
for i in range(len(nums) - 2):
#중복된 값 건너뛰기
if i > 0 and nums[i] == nums[i - 1]:
continue
# 간격을 좁혀가며 합 sum 계산
left, right = i + 1, len(nums) - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum < 0:
left += 1
elif sum > 0:
right -= 1
else:
# sum = 0 인 경우 정답 및 스킵처리
results.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return results제법 어려운 문제였는지 다른것과 다르게 소스가 제법 김
기준점을 잡을 수에다가 간격을 좁혀가는 포인트를 계산하고, 중간 범위를 넘지 않도록 신경써야하는 복잡함이 있었음
이것도 투 포인트 체제의 중요함을 깨달을 좋은 기회였음
점점 쌓여가면 나중에 새로운 알고리즘에서도 활용할 다양한 기술이 생길듯 함
다음에도 기준을 하나 잡고 포인트 2개를 운용해야하는 일이 있을 때,
먼저 기준점으로 계산을 하고, 중복된 값 건너뛰는 걸 염두에 둬야겠음
[배열 파티션 1]
def arrayPairSumMyway(self, nums: List[int]) -> int:
result = 0
nums.sort()
for i in range(0, len(nums), 2):
result += min(nums[i], nums[i+1])
return result
def arrayPairSumAscend(self, nums: List[int]) -> int:
sum = 0
pair = []
nums.sort()
for n in nums:
#앞에서부터 오름차순으로 페어를 만들어서 합 계산
pair.append(n)
if len(pair) == 2:
sum += min(pair)
pair = []
return sum
def arrayPairSumEven(self, nums: List[int]) -> int:
sum = 0
nums.sort()
for i, n in enumerate(nums):
#짝수 번째 값의 합 계산
if i % 2 == 0:
sum += n
return sum
def arrayPairSumPython(self, nums: List[int]) -> int:
return sum(sorted(nums)[::2])
간단하면서도 다양한 방법이 있었기에 흥미로웠음
참고로 맨 위에 내 소스코드가 제일 느렸음(충격)
나름 for 연산을 줄이자고 절반으로 나눴는데, 오히려 나눈다고 포기한 기술들 때문에 처리 시간이 늘어나 버림
짝수 계산을 한걸 볼때는 좀더 문제에 대해서 파악을 해보는 시간을 더 늘려도 괜찮다고 생각이 들었음
다음에 한줄짜리도 가볍게 만든 가장 빠른 소스코드를 봤을때 기본 기술을 이해하는 것도 중요하나는 생각이 들었음
[총평]
오늘 느낀점은 일단 생각을 너무 많이 한다는 것이었음,
또한 생각을 덜 하고 바로 소스코드를 써도 좋지만, 먼저 로직을 그리는 것이 좋다고 생각이 듬
코드가 아닌 글로 써내려 가면서 로직을 구상해도 좋을 듯 함
초기에 빠르게 로직을 구상하고
그 로직에 맞는 기술이 있는지 확인하고
코드를 짜내리는 것이 좋을 것 같음
