Welcome to My IT World

Letter Combinations of a Phone Number - LeetCode

문제요약

2-9의 숫자로 이루어진 문자열이 주어지면, 해당 숫자들로 표현가능한 가능한 문자 조합을 모두 반환

입력

0 <= digits.length <= 4

digits[i] is a digit in the range ['2', '9'].

출력

return string[]

(in any order)

어떻게 풀지?

1. 데이터 전처리 : dict로 각 숫자별 사용가능한 char 정리
2. 파이썬의 product 라이브러리를 사용하자
3. 이 때, map문법과 파이썬의 스프레드 문법(*)을 사용

느낀 점

이번 문제는 문법과 라이브러리만 잘 알면 바로 풀 수 있는 문제였다.

특히, 이번 문제에서 product안에 숫자별 가능한 알파벳 리스트를 담아줄 때, JavaScript의 map과 스프레드 문법이 생각났다.

파이썬에서 map 문법이 있는 건 알았지만, 스프레드 문법은 그간 쓸 일이 없어서 써본 적이 없었고 있는지도 몰랐는데 역시나 있었다.

하나의 언어에 기본적으로 있는 기능은 다른 언어에도 기본적으로 있을 확률이 높은 것 같다.(특히 나중에 나왔을수록…파이썬은 아마 거의 다 있을듯)

다른 언어도 알면 이런 점이 좋구나 생각했다.

- python map

https://www.geeksforgeeks.org/python-map-function/

- python spread operator

https://how.wtf/spread-operator-in-python.html

내 코드

from itertools import product

digits = '23'

def solution(digits):
    if digits == '':
        return []
    dict = {}
    dict['2'] = ['a', 'b', 'c']
    dict['3'] = ['d', 'e', 'f']
    dict['4'] = ['g', 'h', 'i']
    dict['5'] = ['j', 'k', 'l']
    dict['6'] = ['m', 'n', 'o']
    dict['7'] = ['p', 'q', 'r', 's']
    dict['8'] = ['t', 'u', 'v']
    dict['9'] = ['w', 'x', 'y', 'z']
    def find_strs(int_str):
        return dict[int_str]
    print(list(digits))
    print(list(map(find_strs, list(digits))))
    res = list(product(*list(map(find_strs, list(digits))), repeat=1))
    answer = [''.join(x) for x in res]
    return answer

print(solution(digits))

Valid Triangle Number - LeetCode

문제요약

정수배열이 주어질 때, 삼각형을 만들 수 있는 경우의 수를 구하시오.

입력

1 <= nums.length <= 1000

0 <= nums[i] <= 1000

출력

return int

어떻게 풀까?

1. 삼각형을 만들 수 있는 조건?

삼각형의 세 변의 길이 A, B, C 중에서 한 변의 길이를 뽑았을 때, 나머지 두 변의 길이의 합 보다 작아야 한다.(세 변의 길이 모두 부합하여야 함)

⇒ 이 규칙을 좀 더 간단히 해보면?

⇒ “가장 큰 변의 길이 < 나머지 변의 길이의 합”이 부합한다면, 나머지 2조건은 자동적으로 성립할 것

2. 가장 간단하게 푸는 방법?

정수 배열로 가능한 모든 순열 조합을 뽑아 낸 후에 삼각형 만들 수 있는 조건 검토

⇒ O(3N^3)으로 불가능

3. 시간복잡도는 얼마나 수용 가능한가?

⇒ O(10N^2) 정도까지 수용 가능할 것

4. 좀 더 단순화 해본다면?

제약조건을 걸어서 선택지를 좁혀보자

⇒ 가장 큰 숫자를 고정시키고 해당 숫자를 바탕으로 가능한 나머지 숫자 2개의 조합을 찾기

⇒ for largest_idx in range(len(nums)) : O(N)

⇒ 나머지 숫자를 찾는 방식을 O(N)으로 끝내야 함

⇒ 한 배열을 1번만 돌면서 가능한 두 숫자의 조합을 찾아야 함

⇒ Two Pointers 알고리즘 활용

5. 풀이방식

1. 데이터 전처리 : 배열 오름차순 정렬
2. 배열 뒤에서부터 돌면서 가장 큰 값 고정시켜줌
3. 가장 큰 값이 고정된 상태에서 나머지 두 값 찾기
   1. right값을 기준으로 가능한 최소 left값을 찾아서 그 사이의 값들은 해당 right값과 무조건 조건에 부합한다는 방식으로 찾기

어려웠던 점

1. right값과 left값을 찾음에 있어서도 한 값을 기준으로 생각해야하는데, 처음에 두 개 모두 기준으로 생각해서 혼란이 왔다.
2. 중간에 더 시간복잡도를 줄이기 위해, 어느 하나의 largest_idx에서 가능한 조합이 0개가 나오면 더 이상 확인할 것도 없다는 생각에 곧바로 answer를 return해줬는데, [3, 19, 22, 24, 35, 82, 84] 와 같은 경우도 있을 수 있기 때문에 해당조건은 걸어두면 안 되었다.

느낀점

항상 느끼는 거지만, 코딩테스트 문제는 부지런히 풀어야 익숙해지는 것 같다.

내 코드

#largest_idx 주어질 때, 가능한 조합 찾는 함수
def find_possible_triangles(largest_idx, nums):
    #가장 큰 값의 idx가 2미만이면 return
    if largest_idx < 2: return 0
    #largest 바로 앞 숫자 2개 더해서 largest보다 작으면 바로 0 return
    if nums[largest_idx-1]+nums[largest_idx-2] < nums[largest_idx]:
        return 0
    #가장 큰 값 지정
    largest_num = nums[largest_idx]
    #right, left idx 지정
    right = largest_idx-1
    left = 0
    res = 0
    #left가 right보다 작은 한 반복
    while left < right:
        #left값과 right값이 largest보다 큰 최소 right위치 찾기
        #어느 정도까지 가능할지 확인하기 위해 right값 내리기
        if nums[left] + nums[right] > largest_num:
            #해당 right값과 가능한 left값 조합은 현재 left 사이의 값은 모두 가능(오름차순)
            res += (right - left)
            right -= 1
        #반대의 경우엔 left값을 올려보자
        else: left += 1
    return res

def solution(nums):
    answer =0
    #오름차순 정렬
    nums.sort()

    #뒤에서부터 largest num 고정 후 나머지 두 값 찾기
    for i in range(len(nums)-1, -1, -1):
        res = find_possible_triangles(i, nums)
        answer += res
    return answer

print(solution(nums))