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://swexpertacademy.com/main/solvingProblem/solvingProblem.do

코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N, A, B = map(int,input().split())
    answer = -1
    for r in range(1,N+1):
        c = 1
        while r*c <= N:
            cond = A * abs(r-c) + B*(N-r*c)
            if answer == -1:
                answer = cond
            else:
                answer = min(answer, cond)
            c += 1
    print("#%d %d" %(test_case, answer))

풀이

answer 를 -1 로 초기화하고 최소값을 비교하며 답을 구한다.

매번 테스트 케이스마다 N, A, B 를 입력받는다.

r*c 직사각형으로 정사각형을 만들어야 한다.

r을 포문을 돌면서 포문 안에서 r*c 가 N보다 같거나 작을 때까지 c를 하나씩 더해가며 

문제에서 요구하는 A X lR – Cl + B X (N - R X C) 를 구한다.

https://swexpertacademy.com/main/talk/solvingClub/problemView.do

코드

def myPow(N,M):
    global n,m,answer
    if M == m:
        answer = N
        return
    myPow(N*n, M+1)
     
for _ in range(10):
    t = int(input())
    n,m = map(int,input().split())
    myPow(n,1)
    print("#%d" %t, answer)

풀이

재귀함수로 거듭제곱을 구현하라는 쉬운 문제였다.

SWEA 를 처음 써봐서 import sys가 안된다는 것도 몰랐다. ㅎㅎ...

여기서는 input() 사용하자.