programmers 문제 풀어보기

LV 1. 기초

1. 2016년 특정 요일 구하기

• datetime을 이용한 간단한 풀이
  참고 링크

import datetime
# datetime import하기

def solution(a, b):
    day_string = ["MON","TUE","WED","THU","FRI","SAT","SUN"]
    # 요일을 array로 받고
    return day_string[datetime.date(2016, a, b).weekday()]
    # (2016.a.b).weekday() 로 요일 뽑기

print(solution(5, 24))

2. 배열 중 i~j번째 사이 k번째 수 구하기

참고 링크

def solution(array, commands):
    answer = []
    for command in commands:
    # array를 for loop을 돌리는 것이 아니라 i,j,k을 for loop을 돌려야 한다.
        i, j, k = command[0], command[1], command[2]
        # 인덱스로 정의
        slice = array[i-1:j]
        # 슬라이스
        slice.sort()
        # sort로 순서 정렬해주고
        answer.append(slice[k-1])
        # return 할 빈 배열에 넣어준다.
    return answer

LV2. 기본

1. 캐시와 실행시간 구하기

카카오 문제는 난이도가 너무 높아서 참고만 하려고 가져왔다.

LRU 개념
LRU 개념 2

사용자에게 빠르게 정보를 제공하기 위해 사용하는 캐시에서 새로운 데이터가 발생했을 때, 가장 오래전에 사용된 데이터를 제거하고 새로운 데이터를 삽입하는 알고리즘입니다.
새로운 데이터가 들어온 경우
캐시에 넣어준다.
캐시가 가득차있다면, 가장 오래된 데이터를 제거하고 넣어준다.
존재하는 데이터가 들어온 경우
해당 데이터를 꺼낸 뒤,
가장 최근 데이터 위치로 보내준다

• 예시코드

cacheSize = 3
reference = [4, 2, 3, 4, 5, 6, 5, 4, 7]
cache = []
for ref in reference:
  if not ref in cache:
    if len(cache) < cacheSize:
        cache.append(ref)
        # 새로운 데이터가 들어온 경우 넣어준다.
     else:
        cache.pop(0)
        # 오래된 데이터 제거해주고
        cache.append(ref)
        # 새로 집어 넣어준다.
  else:
    cache.pop(cache.index(ref))
    cache.append(ref)

참고 링크

def solution(cacheSize, cities):
    cities = [i.lower() for i in cities]
    answer = 5
    cache = [cities[0]]
    if cacheSize == 0:
        answer += 5 * (len(cities) -1)
     # 캐시가 없으면 무조건 일단 5를 넣고 거기에 시간을 곱한다.
    else:
        for i in cities[1:]:
            if len(cache) < cacheSize and i in cache:
                cache.pop(cache.index(i))
                answer += 1
            elif len(cache) < cacheSize:
                answer += 5
            elif i in cache:
                cache.pop(cache.index(i))
                answer += 1
            else:
                del cache[0]
                answer += 5
            cache.append(i)
    return answer

2. 전화번호부 앞자리 따른 T/F

1. 시도 : prefix 통한 접근(21.4.28 풀이 참고)

def solution(phone_book):
    
    phone_book.sort()
    shortest = phone_book[0]
    prefix = ''
    
    for i in range(len(shortest)):
        if phone_book[len(phone_book)-1][i] == shortest[i]:
            prefix += phone_book[len(phone_book)-1][i]
        else:
            break
            
    if prefix != '':
        return False
    else:
        return True

• True까지는 찾았으나 False 못 찾았음.

2. 찾은 답

참고 링크

def solution(phone_book):
    answer = True
    for i in range(len(phone_book)):
        prefix = phone_book[i]
        prefix_len = len(prefix)
        for j in range(i+1,len(phone_book)):
            next_len = len(phone_book[j])
            if next_len <= prefix_len:
                target = phone_book[j][:next_len]
                if prefix[:next_len] == target:
                    return False
            else:
                target = phone_book[j][:prefix_len]
                if target == prefix:
                    return False
    return answer

유효성으로 인한 새로운 풀이 찾기

def solution(phone_book):
    phone_book.sort(key=len,reverse=True)
    tuple_book = tuple(phone_book)
    for i, phone in enumerate(phone_book, 1) :
        if phone.startswith(tuple_book[i:]) :
            return False
    return True

(??)

답을 모두 찾긴 했으나 모두 유효성 검사에서 막혀서 실패....일단 답은 나옴

3. 행렬 간 곱셈

참고 링크

import numpy as np

def solution(arr1, arr2):
    
    return (np.matrix(arr1) * np.matrix(arr2)).tolist()

4. (kakao) 조건에 맞는 사람 명 수 구하기

풀이법 나온 블로그

이건 어려워서 그냥 답만 참고하려고 가져왔다. 풀이를 차근 차근 읽어보자.

from bisect import bisect_left
from itertools import combinations

def make_all_cases(temp):
    cases = []
    for k in range(5):
        for li in combinations([0, 1, 2, 3], k):
            case = ''
            for idx in range(4):
                if idx not in li:
                    case += temp[idx]
                else:
                    case += '-'
            cases.append(case)
    return cases

def solution(info, query):
    answer = []
    all_people = {}
    for i in info:
        seperate_info = i.split()
        cases = make_all_cases(i.split())
        for case in cases:
            if case not in all_people.keys(): all_people[case] = [int(seperate_info[4])]
            else: all_people[case].append(int(seperate_info[4]))

    for key in all_people.keys():
        all_people[key].sort()

    for q in query:
        seperate_q = q.split()
        target = seperate_q[0] + seperate_q[2] + seperate_q[4] + seperate_q[6]
        if target in all_people.keys():
            answer.append(len(all_people[target]) - bisect_left(all_people[target], int(seperate_q[7]), lo=0, hi=len(all_people[target])))
        else:
            answer.append(0)

    return answer