복습하기 1

그룹애너그램, 가장긴 팰린드롬 부분문자열, 세수의 합, 배열 파티션

03/11/2022

그룹애너그램

처음으로 본 문제.

#문자열 배열을 받아 애너그램 단위로 그룹핑하라.
ex)
*입력
["eat", "tea", "tan", "ate", "nat", "bat"]
*출력
[
["ate", "eat", "tea"],
["nat", "tan"],
["bat"]
]

# 내풀이생각: 첫번째, 각 문자들 단어 체크해서 같은 문자있는 단어끼리 묶어주기.
# 두번째, 묶은 단어끼리, 각 문자 바꿨을때 말이되는 단어되게 만들어주기

#정석풀이: 정렬하여 비교. sorted -> join -> append 정렬하고 합치고 붙여라.
#정렬: ['ate', 'bat', 'eat', 'nat', 'tan', 'tea'] sorted 사용시 print(sorted(example))
#합치고: atebateatnattantea join 사용시 print(''.join(sorted(example)))
#정답
#해쉬맵 위주로 생각할것 이런문제들은
import collections

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
def group_anagram(strs):
    anagrams = collections.defaultdict(list)

    for word in strs:
        anagrams['_'.join(sorted(word))].append(word)
        print(anagrams)
    return list(anagrams.values())
print(group_anagram(strs))

가장 긴 팰린드롬 부분 문자열

#역순
# word = "eever"
# def isPalindrome(word):
#     reversed_word = ' '
#     for a in word:
#         reversed_word = a + reversed_word
#     return reversed_word
# print(isPalindrome(word))


#Q. 알파벳 소문자로만 이루어진 문자열 S가 주어졌을 때, S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 구하는 프로그램을 작성하시오.
'''
ex)
*입력    *출력
abab -> 3
banana -> 5
baekjoon -> 2
online -> 1
eevee -> 5
투포인터 사용?
'''
#팔린드롬
def longest_Palindrom(ss):
    for num in range(len(ss),0,-1):
        for num2 in range(len(ss)-num+1):
            if ssiba[num2:num2+num] == ss[num2:num2+num][::-1]: #슬라이싱 첫번째: 시작, 두번째: 끝, 마지막: 띄우는느낌 오프셋 / 문자열쓸때
                return num                                          #기존에 있는거 할때 쓰는거!

# print(longest_Palindrom("banana"))

세 수의 합

'''
Q. 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.
입력.
nums = [-1, 0, 1, 2, -1, -4]
출력.
[
[-1, 0, 1],
[-1, -1, 2]
]
sort 쓰고, if문쓰고, 고정값쓴다음에 투포인터쓴다
lef, right
'''
nums = [-1, 0, 1, 2, -1, -4]
def threeSum(nums):
    result = []
    nums.sort() #nums = [-1, 0, 1, 2, -1, -4] -> [-4, -1, -1, 0, 1, 2]
    length = len(nums) #6
    for i in range(length - 2):
        if nums[i] > 0 or (i > 0 and nums[i] == nums[i - 1]):
            continue #이거 생각해냈다. 이 케이스같은 경우 [(-1, -1, 2), (-1, 0, 1), (-1, 0, 1)] 이렇게 중복된 답 두개 나오기때문에 붙어서 중복되는거 건너뛴다고 하는거였다.
        left, right = i + 1, length - 1
        while  left < right:
            sum = nums[i] + nums[left] + nums[right]
            if sum < 0:
                left += 1
            elif sum > 0:
                # 여기서 elif 가 아닌 if 로 처리하면 뒤의 esle 문과 맞물려 에러가 발생한다. else 가급적 쓰지말고 조건문을 추가해야될듯
                right -= 1
            else:
                result.append((nums[i], nums[left], nums[right]))
                # print(result)

                while left < right and nums[left] == nums[left + 1]: #while문 살짝 if문이랑 for문 합친느낌
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1

    return result
nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))

배열 파티션

제일 풀기가 쉬웠다

'''
n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라.
입력: [1, 4, 3, 2]
출력: 4
'''
#오름차순형식
nums = [1, 4, 3, 2]
print(nums.sort()) #sort()는 none 무조건 리턴하고, 원래 리스트 영향 sorted() 는 값을 리턴한다 그리고 원래 리스탑 영향 안준다
def array_partition():
    sum = 0
    pair = []
    nums.sort()
    for n in nums:
        pair.append(n)
        if len(pair) == 2:
            sum += min(pair)
            pair = []
    return sum
#짝수형식
def array_partition2():
    sum = 0;
    nums.sort()
    for i, n in enumerate(nums): #
            if i % 2 == 0:
                sum += n
    return sum

#파이썬스러운방식이야
def array_partition3():
    return sum(sorted(nums)[::2])## start, stop, step -> 슬라이싱 구문.