(TIS) 20210512

HEYDAY7·2021년 5월 11일

Today I Solved

목록 보기

2/9

문제 Level 2

프로그래머스 '위장'

dict를 통해서 깔끔하게 문제를 해결할 수 있다.

collections의 Counter를 이용하였다.

프로그래머스 '가장 큰 수'

삽질하다 못 푸는중 time complexity가 너무큰가? 생각중 / 임시보류

프로그래머스 'JadenCase 문자열 만들기'

문제에 대한 설명이 살짝 아쉽다. 다만 뭐 질문하기를 통해 문제를 새로 이해한 후에는 쉽게 풀었다. 그다지 어렵진 않았다.

프로그래머스 'N개의 최소공배수'

a와 b의 최소공배수는 a*b / 최대공약수(a, b) 인 점을 활용해서 해결하였다.

프로그래머스 '피보나치 수'

일반적인 피보나치 문제와 나머지개념이 합쳐졌다.

A + B를 1234567로 나눈 나머지는 A와 B를 각각 1234567로 나눈 나머지의 합을 1234567로 나눈 나머지와 같다.!

프로그래머스 '숫자의 표현'

pass

프로그래머스 '행렬의 곱셈'

zip의 새로운 사용방식이다. list형태의 matrix를 transpose 하고 싶을 때 zip(* arr)을 사용하자!

arr = [[1,2,3], [4,5,6]] 
arr_t = list(zip(*arr))

arr_t는 [[1,4],[2,5],[3,6]]가 된다.

프로그래머스 "최솟값 만들기"

간단했다.

프로그래머스 "올바른 괄호"

stack을 이용해서 쉽게 해결할 수 있었다.

프로그래머스 "전화번호 목록"

문제
기존에 접근할 때는 아래와 같이 접근했다.

def solution(phone_book):
    from collections import defaultdict
    
    dct = defaultdict(list)
    for num in sorted(phone_book, key=len):
        first = num[0]
        for word in dct[first]:
            if len(word) < len(num):
                if num.startswith(word):
                    return False
            else:
                break
        dct[first].append(num)

    return True

이 경우 다 통과하지만 효율성 마지막 테스트에서 걸려서 고생을 좀 했다.

그러다 질문하기를 통해 너무나도 간단한 해법을 찾았다.
숫자들을 단순 sorting을 하면 str형태로 sorting하게 되면 모든 숫자들의 앞자리 기준 정렬이 되고, 앞자리가 같을 경우 그 다음 자리 기준으로 알아서 정렬이 된다. 즉 ['123', '12', '13', '1', '333']의 경우 단순 sorting을 하면 ['1', '12', '123', '13', '333']이 되는 것이다. 따라서 이 경우에는 자기 바로 뒷 숫자가 자신으로 시작하지 않으면 가능성이 없기 때문에 바로 뒷 숫자만 확인하면 되서 timecomplexity를 줄일 수 있다.

def solution(phone_book):
  phone_book.sort()
      for i in range(len(phone_book)-1):
          if phone_book[i+1].startswith(phone_book[i]):
              return False

      return True

또한 문제는 원래 해쉬 문제라서 도움이 될 만한 해쉬 풀이도 가져왔다.

def solution(phone_book):
    s = set(phone_book)
    for number in phone_book:
        temp = ''
        for num in number:
            temp += num
            if temp in s and temp != number:
                return False
    
    return True