coding test

시간 복잡도 줄이기

ron_nie 2023. 6. 17. 11:44
728x90

1. readline() : 입력 속도를 빠르게

프로그래머스에는 입력값을 모두 주지만 실제 시험을 볼때는 입력값을 받는 코드도 구현해야 하는 경우가 있다.

import sys

data = sys.stdin.readline()

2. 리스트 곱셈

미리 할당해 놓은 고정 배열에다가 계산하는 경우에 쓴다. 초기화와 할당을 동시에 할 수 있다.

data1 = [0 for _ in range(1000)]
data2 = [0] * 1000

3. 그외

  • 문자열 합치기 : join()을 사용하자
  • 반복문을 사용할 때는 짧은 것 부터 사용하자
  • 슬라이싱 : 불필요한 연산을 최소로

슬라이싱

kospi_top10 = ['삼성전자', 'SK하이닉스', '현대차', '한국전력',
               '아모레퍼시픽', '제일모직', '삼성전자우', '삼성생명', 'NAVER', '현대모비스']

print(kospi_top10[4])  # 아모레퍼시픽
print(kospi_top10[0:4])  # ['삼성전자', 'SK하이닉스', '현대차', '한국전력'] : 처음부터4번째까지
print(kospi_top10[:4])  # ['삼성전자', 'SK하이닉스', '현대차', '한국전력'] : 처음부터 4번째 까지
# ['아모레퍼시픽', '제일모직', '삼성전자우', '삼성생명', 'NAVER', '현대모비스'] : 4번째부터 끝까지
print(kospi_top10[4:])
# ['삼성전자', '한국전력', '삼성전자우', '현대모비스'] : 처음 포함해서 3의 배수인 index 앞에꺼만 
print(kospi_top10[::3])

4. 표준 라이브러리 사용하기

  • headpq : 우선순위 큐나 최단 거리 알고리즘
  • collections
    • counter : 동일한 원소가 몇개 있는지, 해쉬문제 풀때 유용
    • dequeue(덱) : 덱 자료구조를 구현
  • itertools
    • permutations : 순열
    • combinations : 조합
    • permutations_with_replacement : 중복순열
    • combinations_with_replacemen : 중복조합
  • math : 수학문제 나오면 무조건 이거
  • bisect : 이진 탐색 기능, 특정 범위 안에 원소가 있는지 검사하거나 몇 개가 존재하는지 확인하는데 유용함

리스트 컴프리헨션 vs 제너레이터

1. 리스트 컴프리헨션

data = []
for i in range(1, 11):
    data.append(i)

print(data) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

이 코드를 줄이려면 컴프리헨션을 사용한다

[i for i in range(1, 11)]

형식

[(변수 표현식) for (사용할 변수) in (순회 가능한 연속적인 데이터)]

활용

  1. 바로 앞의 코드에서 짝수만 뽑고 싶을 때
[i for i in range(11) if i % 2 == 0]
  1. 짝수와 5의 배수를 동시에 만족하는 숫자만 필요하다고 할 때(if 중첩 사용)
[i for i in range(11) if i % 2 == 0 if i % 5 == 0]

2. 제너레이터

연속 가능한 자료형을 반환하는 함수로 실행중 yeild를 만나면 값을 반환하고 더 이상 진행할 수 없는 상태가 아니라면 next()가 호출되기 전까지 대기한다.

제너레이터 만드는 방법

  1. return 대신 yeild 쓰기
  2. 대괄호 대신 소괄호 사용하기
(i for i in range(11))

이 함수는 한번에 1부터 10까지 실행하지 않고, 직접 next를 호출해야 1, 2, 3 값이 반환된다.

데이터 돌려쓰기 : 중복 피하기

주어진 데이터 10만개를 제곱하세요

def solution(data):
    answer = data

    for i in range(len(answer)):
        temp = answer[i] * answer[i]
        answer[i] = temp

    return answer
  1. 주어진 데이터를 변수로 받아
  2. 받은 데이터를 순회하여 리스트 컴프리헨션을 사용하여
  3. 항목마다 데이터를 제곱하고
  4. 정답반환

⇒ 너무 복잡함

def solution(data):
    return [i * i for i in data]
  1. 받은 데이터를 리스트 컴프리 헨션으로
  2. 항목마다 제곱하고
  3. 정답 반환
반응형