Programmers LV 2

문제 풀이

뒤에 있는 큰 수 찾기

def solution(numbers):
    answer = [0] * len(numbers)
    idx = []
    for i in range(len(numbers)):
        while idx and numbers[idx[-1]] < numbers[i]:
            answer[idx.pop()] = numbers[i]
        idx.append(i)
    while idx:
        answer[idx.pop()] = -1
    return answer

< 풀이 과정 >
idx라는 인덱스를 저장해주는 빈 리스트와 numbers 길이 만큼의 0으로 채워진 리스트를 생성하여 for문을 돌고 인덱스 별로 numbers를 순회해 뒷 큰수가 현재 인덱스보다 크면 answer에 추가, 아니면 인덱스 리스트만 추가해주는 형식으로 진행

숫자 변환하기

from collections import deque
def solution(x, y, n):
    result = [0] * 1000001
    def bfs(x, y, n):
        queue = deque()
        result[x] = 1
        queue.append(x)
        while queue:
            x = queue.popleft()
            if 0<=x+n<=1000000 and result[x+n] == 0:
                result[x+n] = result[x] + 1
                queue.append(x+n)
            if 0<=2*x<=1000000 and result[x*2] == 0:
                result[2*x] = result[x] + 1
                queue.append(2*x)
            if 0<=3*x<=1000000 and result[3*x] == 0:
                result[3*x] = result[x] + 1
                queue.append(3*x)
    bfs(x, y, n)
    return result[y]-1

< 풀이 과정 >
bfs를 활용하여 빈 리스트를 만들고 값이 계산될 때마다 +1씩 해주어 x -> y 과정의 연산 횟수를 계산해주는 solution 함수 만들어준다.

점 찍기

import math
def solution(k, d):
    answer = 0
    for x in range(0, d+1, k):
        y = math.floor(math.sqrt(d**2 - x**2))
        answer += y // k + 1
    return answer

< 풀이 과정 >
for문으로 점 찍을 수 있는 x축을 계산하면 0~d+1 범위에서 k 단위로 끊는 경우의 수이고, y축은 d^2 - x^2의 내림으로 계산할 수 있다.
이때 정답은 y // k의 수 + x축(1)로 결과를 리턴하면 된다.

후보키

from itertools import combinations

def solution(relation):
    cols = len(relation[0])
    rows = len(relation)
    
    candidatekeys = []
    attribute = [i for i in range(cols)]
    for i in range(1, cols+1):
        candidatekeys.extend(combinations(attribute, i))
    
    uniq = []
    for attr in candidatekeys:
        check = [tuple([row[key] for key in attr]) for row in relation]
        if len(set(check)) == rows:
            flag = True
            for i in uniq:
                if set(i).issubset(set(attr)):
                    flag = False
                    break
            if flag:
                uniq.append(attr)
    return len(uniq)

< 풀이 과정 >
문제 해결에 상당히 오래걸려 다른 사람이 푼 풀이를 참고하고 이해한 문제

1.주어진 속성들로 가능한 경우의 수를 인덱스로 우선 구현한 candidatekeys를 만들어 준다.
2. 인덱스 값으로 만든 candidatekeys를 for문을 돌려 순회하고 check라는 실제 데이터 수가 rows와 일치하면 유일성을 통과하므로 flag라는 boolean을 True로 해준다.
3. 만일 uniq 내 속성 집합이 이미 구성된 attr의 부분집합이라면 최소성을 만족하지 않으므로 flag를 False로 지정한다.
4. flag가 True인 경우, 즉 유일성과 최소성을 만족하는 집합만 uniq에 추가한다.
결과는 모두 만족한 uniq의 개수만 리턴