Jinho Tech

오늘은 프로그래머스에서 진행되는 코테 모의고사 2차 문제를 풀어봤다. 난이도가 조금 쉬운 것 같다.

1차도 풀긴 했는데 시험 종료하면 문제랑 코드를 못 본다는 사실을 몰랐어서 그냥 종료해버렸다ㅜ 

https://career.programmers.co.kr/competitions/2627

1번

설명할 필요도 없을 듯 하다. python의 combinations를 쓰면 조합을 바로 구할 수 있다.

from itertools import combinations

def solution(number):
    return len([s for s in combinations(number, 3) if sum(s) == 0])

2번

처음에 그냥 리스트를 쪼개고 set 함수를 사용해서 풀었는데 시간 초과가 나왔다

EX) len(set(topping[:i]) == len(set(topping[i:])

딕셔너리를 사용해서 해결했다. 역시 빠르다 우리 사전!

from collections import Counter, defaultdict

def solution(topping):
    front, back = defaultdict(int), dict(Counter(topping))
    ans = 0
    
    for t in topping:
        front[t] += 1
        back[t] -= 1
        if back[t] == 0:
            del back[t]
        if len(front) == len(back):
            ans += 1

    return ans

3번

문제의 글만 보면 군인들이 목적지로 향하는 상황이지만

우리가 문제를 풀 때는 목적지가 군인들을 찾아간다고 생각하는 것이 풀기 쉽다.

목적지 기준으로 bfs 알고리즘을 사용해서 다른 모든 위치까지의 거리를 구하면 사실상 끝이다.

from collections import deque

def solution(n, roads, sources, destination):
    graph = [[] for _ in range(n+1)]
    ans = []
    
    for s, e in roads:
        graph[s].append(e)
        graph[e].append(s)

    check = [-1 for _ in range(n+1)]
    check[destination] = 0
    q = deque([destination])
    while q:
        i = q.popleft()
        for node in graph[i]:
            if check[node] == -1:
                check[node] = check[i]+1
                q.append(node)

    for s in sources:
        ans.append(check[s])

    return ans

수학 & 이분 탐색 문제이다.

위 그림에서 w1 : c = w : h2, w2 : c = w : h1라는 점을 통해

w1 = c*w / h2, w2 = c*w / h1 

w = w1 + w2 = c*w / h2 + c*w / h1 = c*w*(h1+h2) / (h1*h2) 

-> 1 = c*(h1+h2) / (h1*h2) -> c = h1*h2 / (h1+h2)

h1 = (x**2-w**2)**0.5, h2 = (y**2-w**2)**0.5 임을 알 수 있다.

앞에서 밑줄 친 3개의 공식을 사용해서 이분 탐색을 해주면 된다.

def f(x, y, w):
    h1 = (x**2-w**2)**0.5
    h2 = (y**2-w**2)**0.5    
    c = h1*h2 / (h1+h2)
    return c
    
x, y, c = map(float, input().split())
s, e = 0, min(x, y)
res = 0
while e-s > 0.000001:
    m = (s+e)/2
    if f(x, y, m) >= c:
        res = m
        s = m
    else:
        e = m
print(res)