say repository

https://programmers.co.kr/learn/courses/30/lessons/17680#

출처 : 프로그래머스

코드

def solution(cacheSize, cities):
    answer = 0
    cache = []
    if cacheSize == 0:
        return len(cities) * 5
    else:
        for city in cities:
            city = city.lower()
            if not city in cache:
                if len(cache) < cacheSize:
                    cache.append(city)
                    answer += 5
                else:
                    cache.pop(0)
                    cache.append(city)
                    answer += 5
            else:
                cache.pop(cache.index(city))
                cache.append(city)
                answer += 1

    return answer

풀이

LRU (Least Recently Used) 알고리즘

캐시 사이즈만큼 cities를 저장할 수 있다.

캐시 사이즈보다 작으면 캐시에 저장할 수 있고,

아니면 캐시에 있는 것을 빼야한다.

이 때, 최근에 사용하지 않은 ( 즉, 가장 사용 안하는 것) 것부터 캐시에서 제거한다. -> 그래서 큐를 쓴다.

찾는 데이터가 캐시에 있으면 cache hit

없으면 cache miss가 발생한다.

다만 이 문제는 캐시사이즈가 0일 때도 있다.

캐시사이즈가 0이면 모든 데이터에서 miss 가 발생해서 데이터 길이 * 5를 리턴해주면 된다.

https://programmers.co.kr/learn/courses/30/lessons/42890

출처 : 프로그래머스

 코드

from itertools import combinations
def solution(relation):
    row = len(relation)
    col = len(relation[0])
    comb = []
    # 모든 후보키 경우의 수 
    for c in range(1, col+1):
        comb.extend(combinations(range(col), c))
    
    candidate_keys = []
    for c in comb:
        tmp = [tuple(rela[cc] for cc in c) for rela in relation]
        # print(tmp)
        # 유일성 : 중복 제거 
        if len(set(tmp)) == row:
            flag = True
            # 최소성
            for k in candidate_keys:
                if set(k).issubset(set(c)):
                    flag = False
                    break
            if flag:
                candidate_keys.append(c)
    return len(candidate_keys)

 풀이

relation의 열과 행의 개수를 모두 구해둔다.

그리고 가능한 후보키의 인덱스 조합을 모두 구해둔다.

후보키를 구할 때는, 유일성을 먼저 고려해보고 유일성을 고려한 조합 중에서 최소성을 만족하는 키만 candidate_keys에 삽입한 후,

이 배열의 길이를 return 해준다.

가능한 후보키의 인덱스 조합에 해당하는 relation의 값을 tuple 리스트로 tmp에 저장한다.

tmp에 set()을 적용하여 중복을 제거하고, row와 길이가 같다면 유일성을 만족한다.

이렇게 유일성을 만족하는 조합이 조합의 부분집합인지 issubset()을 사용해 확인한다.

부분집합이면 최소성을 만족하지 않으므로 flag 를 False 로 표시해준다.

유일성과 최소성을 모두 만족해야 flag가 True 이다.

이 key만 최종적으로 후보키가 될 수 있다.

 배운 점

• issubset() : 부분집합인지 확인
• issuperset() : 상위집합인지 확인

https://programmers.co.kr/learn/courses/30/lessons/12905

출처 : 프로그래머스

코드

def solution(board):
    answer = 0
    row = len(board)
    col = len(board[0])

    for r in range(1,row):
        for c in range(1,col):
            if board[r][c] == 1:
                board[r][c] = min(board[r][c-1], board[r-1][c], board[r-1][c-1])+1
                answer = max(answer, board[r][c])
    for b in board:
        if max(b) > answer:
            answer = max(b)
        
    return answer**2

풀이

dp 문제이다.

현재 찾아야 하는 해는 최대 넓이의 정사각형이 될 수 있는 변의 길이다.

해를 구해 answer 에 넣고 **2 를 해서 넓이를 return 한다.

정사각형을 구할 때, board를 돌면서 1이면 정사각형이 가능하다.

하지만, 주변에도 1이 있어야 최대의 정사각형이 된다.

정사각형이 되려면? 현재 위치의 위, 왼쪽, 왼쪽 위 대각선 의 위치에도 1이 있어야 한다.

            if board[r][c] == 1:
                board[r][c] = min(board[r][c-1], board[r-1][c], board[r-1][c-1])+1

현재 위치의 위, 왼쪽, 왼쪽 위 대각선의 위치의 가장 작은 수의 +1 을 해주는 이유는

모두 같은 수라면 +1 해서 커질 것이고

하나라도 0이 있거나 작은 수가 있으면 정사각형은 작아질 것이다.

https://programmers.co.kr/learn/courses/30/lessons/17686#

출처 : 프로그래머스

코드

def solution(files):
    answer = []
    for file in files:
        flag = False
        head = ''
        number = ''
        tail = ''
        for i in range(len(file)):
            if file[i].isdigit():
                number += file[i]
                flag = True
            elif flag == False:
                head += file[i]
            elif flag == True:
                tail = file[i:]
                break
        answer.append([head, number, tail])
        
    answer.sort(key = lambda x: (x[0].upper(), int(x[1])))
    return [''.join(t) for t in answer]

풀이

파일명을 head, number, tail 세가지 부분으로 분류를 한 후 정렬비교 해야한다.

숫자가 나오기 전까지가 head 이고 숫자가 끝나면 tail이다.

이 때, tail 이 없을 수도 있다.

그래서 head와 number + tail 을 크게 비교하고 숫자면 flag를 True 로 체크해준다.

그 후, tail에 넣어준다. 

정렬할 때, tail은 입력순으로 들어가기 때문에 나중에 sort 하면 되니 큰 상관은 없다.

이제 최종 sort를 하는데, head가 대소문자가 구분 없으니, upper()로 대문자로 비교한다.

sort의 우선순위는 head, 그 다음이 number 다.

그렇게 정렬 해주고, 구분한 head, number, tail을 다시 합치면 된다.

https://programmers.co.kr/learn/courses/30/lessons/17683

출처: 프로그래머스

코드

def change(melody):
    if 'A#' in melody:
        melody = melody.replace('A#','a')
    if 'C#' in melody:
        melody = melody.replace('C#','c')
    if 'D#' in melody:
        melody = melody.replace('D#','d')
    if 'F#' in melody:
        melody = melody.replace('F#','f')
    if 'G#' in melody:
        melody = melody.replace('G#','g')
    return melody

def solution(m, musicinfos):
    answer = []
    for musicinfo in musicinfos:
        info = musicinfo.split(',')
        start = info[0].split(':')
        end = info[1].split(':')
        running = (int(end[0]) - int(start[0]))*60 + int(end[1]) - int(start[1])
        melody = change(info[3])
        melody = melody * (running // len(melody)) + melody[:running%len(melody)]

        if change(m) in melody:
            answer.append([info[2], running])
            
    if not answer:
        return "(None)"
    else:
        answer = sorted(answer, key = lambda x: (-x[1]))
        return answer[0][0]

풀이

 문자열을 비교해야하는 문제이다.

하지만, 단순하게 비교하자면 C#처럼 #이 붙어져 있는 문자열을 비교할 때 문제가 생긴다.

따라서, #이 포함되어 있는 코드는 모두 소문자로 바꿔주는 change 함수를 생성한다.

그리고 musicinfos 에 있는 곡 정보를 토큰화한다.

멜로디를 change 함수를 적용한 후, 재생 시간에 맞게 반복적인 멜로디를 생성해둔다.

이 멜로디와 m 문자열을 비교하면 된다.

https://programmers.co.kr/learn/courses/30/lessons/72412?language=python3 

출처 : 프로그래머스

https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

코드

from collections import defaultdict
from bisect import bisect_left
from itertools import combinations

def solution(info, query):
    answer = []
    dic = defaultdict(list)
    for i in info:
        i = i.split()
        cond = i[:-1]
        score = int(i[-1])
        for i in range(5):
            cases = list(combinations([0,1,2,3],i))
            # print(cases)
            for case in cases:
                tmp = cond.copy()
                for c in case:
                    tmp[c] = '-'
                key = ''.join(tmp)
                dic[key].append(score)
    # print(dic)
    
    for val in dic.values():
        val.sort()
    
    for q in query:
        q = q.replace("and ", "")
        q = q.split()
        target_cond = ''.join(q[:-1])
        target_score = int(q[-1])
        cnt = 0
        if target_cond in dic:
            target_list = dic[target_cond]
            # print(target_list)
            idx = bisect_left(target_list, target_score)
            cnt = len(target_list) - idx
        answer.append(cnt)
    return answer

풀이

query 문과 info의 조건을 모두 비교해서 풀면 효율성에서 합격하지 못한다.

효율성에서 통과되지 못해서 카카오 풀이를 참고했다.

1) info 에 있는 조건으로 만들 수 있는 모든 경우의 수를 key로 갖고있는 defaultdict를 생성해야한다.

key는 모든 조건, 값은 score 로 갖는 defaultdict 를 생성한다.

2) 이렇게 생성된 dic는 score 값을 기준으로 오름차순 정렬한다.

3) 이제 query와 비교하여 찾는다.

query에 조건이 info의 key로 있다면 score 값들을 target_list 로 가져온다.

4) 여기서 또, 하나하나 찾는다면 효율성에 문제가 생긴다.

빠르게 탐색하기 위해 순차탐색 보다는 이진탐색을 활용하자.

bisect_left 를 이용하여 target_list 에서 target_score 가 있는 인덱스를 구하고

이 인덱스를 전체 target_list 에서 빼준다면 정답에 추가할 cnt 가 된다.

https://programmers.co.kr/learn/courses/30/lessons/42860

출처 : 프로그래머스

코드

def solution(name):
    answer = 0
    # 최소 이동은 문자열 길이 -1
    move = len(name)-1
    
    # 조이스틱 상하 이동으로 알파벳 최소 차이
    for i, alp in enumerate(name):
        answer += min(ord(alp)-ord('A'), ord('Z')-ord(alp)+1)
        
        # 연속된 'A' 발견하면 넘어가기
        moving_idx = i + 1
        while moving_idx < len(name) and name[moving_idx] == 'A':
            moving_idx += 1
            
        # 현재 최소 이동과 조이스틱 좌로 움직이거나 우로 움직이는 것 간의 최소 이동 횟수 구하기
        move = min([move, i*2 + (len(name)-moving_idx), i + 2*(len(name)-moving_idx)])
        
    answer += move
    return answer

풀이

그리디 알고리즘이라기보다는 부르트포스 알고리즘이다.

가능한 경우는 모두 탐색한다.

최소 이동은 처음부터 -> 로 계속 이동하는 경우로 문자열 길이 -1 이다.

이제는 조이스틱을 상하 로 이동하는 알파벳 이동의 개수를 구해보자.

A~Z 사이에 있는 알파벳은 A 부터의 조이스틱 이동 횟수와 Z 에서 시작한 조이스틱 이동 횟수의 최소값으로 구한다.

        answer += min(ord(alp)-ord('A'), ord('Z')-ord(alp)+1)

그리고 다시 조이스틱 좌우 이동횟수를 구해야한다.

이 때, A가 있으면 넘어가야한다.

그리고 현재 최소 이동 ( 문자열 길이 -1) 와 

A 기준으로 왼쪽에서 움직이거나 A 기준 오른쪽에서 움직이는 이동 횟수 중 가장 최소 값을 구해서

최종 answer에 더해준다.

        # 현재 최소 이동과 조이스틱 좌로 움직이거나 우로 움직이는 것 간의 최소 이동 횟수 구하기
        move = min([move, i*2 + (len(name)-moving_idx), i + 2*(len(name)-moving_idx)])