그냥 코딩하는 사람의 블로그

풀이 과정

1. 정규 표현식을 활용하여 meta 태그에서 자기 사이트 주소를 가져온다.(re.findall)
2. 정규 표현식을 활용하여 모든 a 태그에서 자기가 링크하고있는 사이트 주소들을 가져온다.(re.findall)
   • 이 때, 해당 사이트에 자기가 링크중이라는걸 따로 저장하여 둔다.
3. 정규 표현식을 활용하여 기본 점수를 구한다(re.split)
4. 각 사이트별로 점수를 구한 뒤, 최댓값인 사이트의 인덱스를 리턴한다. 이때, 여러개라면 순번이 작은걸 리턴해주어야 함.

• 정규 표현식에서 문제가 있어서 75점에서 막혔었다.

    <a href=".*"> 는 75점이 나와서 찾아본 결과 <a href="[^"]*">로 해보니 100점이 나오는데..
    url 내에 이상한 테스트 케이스가 존재하는거 같다..

소스 코드

import re

def get_links(page, word, idx, site_index, site_score, site_link_count, site_linked):
    page = page.lower()

    # 자기 사이트 가져오는 파트
    pattern = r'<meta property="og:url" content=".+"/>'
    temp = re.findall(pattern, page)
    mysite = temp[0][len('<meta property="og:url" content="'):-3]

    # 딕셔너리 초기화
    site_score[mysite] = 0
    site_link_count[mysite] = 0
    site_index[mysite] = idx
    if site_linked.get(mysite) == None:
        site_linked[mysite] = []

    # 링크한 사이트들에 자기가 링크중이라고 표시
    pattern = r'<a href="[^"]*">'
    temp = re.findall(pattern, page)
    for t in temp:
        site_link_count[mysite] += 1
        site = t[9:-2]
        if site_linked.get(site) == None:
            site_linked[site] = [mysite]
        else:
            site_linked[site].append(mysite)

    # 기본점수 구함
    pattern = r'[^a-z]' # 알파벳이 아닌 문자로 split 해주어야 함.
    temp = re.split(pattern, page)
    for t in temp:
        if t == word.lower():
            site_score[mysite] += 1

    return temp


def solution(word, pages):
    answer = 0
    max_score = -1
    site_score = dict() # 기본점수
    site_link_count = dict() # 링크 카운팅
    site_linked = dict() # 자기를 링크하고있는 사이트들
    site_index = dict() # 사이트의 인덱스

    for idx, page in enumerate(pages):
        get_links(page, word, idx, site_index, site_score, site_link_count, site_linked)

    for site in site_score.keys():
        linked_score = 0
        for linked_site in site_linked[site]: # 자기를 링크한 사이트들
            linked_score += (site_score[linked_site] / site_link_count[linked_site])

        total_score = site_score[site] + linked_score

        # 전체 점수가 최댓값이라면 갱신
        if total_score > max_score:
            max_score = total_score
            answer = site_index[site]
        elif total_score == max_score:
            answer = min(answer, site_index[site])

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 진입 시점 기준으로 내림차순으로 정렬해주고, 첫번째 진입 시점에 카메라를 둔다.
2. 반복문을 돌면서 현재 진입 시점 ~ 진출 시점
   • 카메라가 있다면 pass
   • 카메라가 없다면 현재 진입 시점에 카메라 한대 추가 설치

• 진입시점 기준으로 내림차순으로 정렬해 주었으므로, 이전 단계의 카메라 위치는 어차피 겹치거나 도달하지 않으므로 필요 없음.

3. 카메라의 개수 리턴

소스 코드

def solution(routes):
    answer = 1
    routes.sort(reverse=True) 
    # "진입 시점 기준으로 내림차순 정렬"
    camera = routes[0][0]

    for i in range(1, len(routes)):
        # 현재 진입 시점~진출 시점 사이에 카메라가 있다면 pass
        # 카메라가 없다면 해당 진입 시점을 카메라의 위치로
        if routes[i][0] <= camera and camera <= routes[i][1]:
            pass
        else:
            answer += 1
            camera = routes[i][0]

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 가장 긴 길이부터 검사
2. 문자열 맨 앞에서부터 구간을 나눠가면서 팰린드롬 검사
   • 뒤집었을때와 같아야 하므로 s == s[::-1]로 검사
3. 팰린드롬이라면 바로 해당 length를 리턴해주면 된다.

소스 코드

def solution(s):
    answer = 1

    for length in range(len(s), 1, -1):
        for i in range(len(s)-length+1):
            if s[i:i+length] == (s[i:i+length])[::-1]:
                return length

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 탑승객 정보를 분단위로 변환 및 정렬
2. 탑승객 정보를 큐에 삽입한다.
3. 셔틀을 하나씩 도착시키면서 인원수 비교
   • 현재 셔틀에 탑승가능하면 큐에서 빼줌
   • 이 때, 탑승 가능한 최대 인원수가 된다면 그 때의 탑승객보다 1분 빨리 오면 된다.
   • 마지막으로, 셔틀에 빈자리가 있는 경우
     • 막차라면, 해당 셔틀 도착 시간에 무조건 타야 함

소스 코드

from collections import deque

def convert(time):
    return 60 * int(time[:2]) + int(time[3:])

def solution(n, t, m, timetable):
    answer = -1
    cv_time = []

    for time in timetable:
        cv_time.append(convert(time))

    cv_time.sort()
    queue = deque(cv_time)
    time = convert("09:00")
    total_people = n * m
    people = 0

    for i in range(n):
        shuttle = time + (t * i) # 현재 도착한 셔틀 시간
        curr_count = 0
        # 현재 시간에 탑승가능한 인원 탑승
        while queue and queue[0] <= shuttle and curr_count < m:
            curr_count += 1
            # 현재 인원이 탑승했을 때, 최대 인원수가 된다면 1분 전에 서있어야 함
            if people + curr_count == total_people:
                answer = queue[0] - 1
                break
            queue.popleft()

        # 현재 인원수가 탑승가능 인원수보다 적다면 맞춰줌
        if curr_count < m:
            curr_count = m

        # 현재 셔틀이 빈자리가 있으면서 마지막 셔틀이라면 도착시간에 타야 함 
        if answer == -1 and people + curr_count >= total_people:
            answer = time + (t * i)

        # 정답을 구했으면 break
        if answer != -1:
            break

        people += curr_count

    if answer == -1:
        answer = time + (t * (n-1))

    # 시간 변환
    temp = answer
    answer = str(temp // 60).zfill(2)
    answer += ':'
    temp = temp % 60
    answer += str(temp).zfill(2)

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이과정

1. 시간을 초단위로 모두 바꾸어 준다.
2. 전날 -> 오늘로 넘어오는 케이스도 있으므로 완료시간(초)에 + 4 해준다.
3. 완료시간으로 시작시간을 구해준다. - 시작 시간 = 완료시간 - 처리시간 + 0.001
4. 시작 시간 기준으로 정렬을 해준다.
5. 시작 시간을 기준으로 반복문을 돌면서, 최소 히프에 완료 시간을 기준으로 넣어준다.
   • 넣어준 다음, 현재 시간 + 1 기준으로 끝난 작업들은 히프에서 빼준다.
6. 히프에 남아있는 요소들의 개수가 현재 겹치는 작업들을 의미하므로 answer을 갱신해준다.

소스 코드

import heapq
import math
def convert_second(s):
    hour = int(s[0:2])
    minute = int(s[3:5])
    second = int(s[6:8])
    msecond = int(s[9:]) / 1000
    return 4 + 3600 * hour + 60 * minute + second + msecond


def solution(lines):
    answer = 0
    cv_list = []
    for line in lines:
        temp = line.split()
        end = convert_second(temp[1])
        start = round(end - float(temp[2][:-1]) + 0.001, 3)
        cv_list.append([start, end])

    cv_list.sort()

    heap = []
    for start, end in cv_list:
        heapq.heappush(heap, [end, start])
        while heap:
            if heap[0][0] + 1 <= start:
                heapq.heappop(heap)
            else:
                break
        answer = max(answer, len(heap))

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. play_time, adv_time, log를 모두 초단위로 변경
2. log의 시작시간엔 +1, 종료시간엔 -1
3. 누적합을 구함 => 현재 시점에서의 시청자 수
4. 다시 누적합을 구함 => 현재 시점까지의 시청자 수 누적합
5. 전체 구간에서 가장 누적 재생시간이 긴 시작시간을 찾으면 된다.
   • (a, b) 구간의 누적합 = 누적합[b] - 누적합[a]

소스 코드

def convert(time):
    return 3600 * int(time[:2]) + 60 * int(time[3:5]) + int(time[6:8])

def r_convert(s):
    hour = str(s // 3600).zfill(2)
    s = s % 3600
    minite = str(s // 60).zfill(2)
    s = s % 60
    second = str(s).zfill(2)
    return hour + ":" + minite + ":" + second


def solution(play_time, adv_time, logs):
    answer = ''
    total = convert(play_time)
    advertise = convert(adv_time)
    consumers = [0] * (total+1)
    n = 0

    for log in logs:
        temp = log.split('-')
        consumers[convert(temp[0])] += 1
        consumers[convert(temp[1])] -= 1

    for i in range(1, total+1): # 현재 시점에서의 시청자 수
        consumers[i] += consumers[i-1]

    for i in range(1, total+1):
        consumers[i] += consumers[i-1]

    people = consumers[advertise-1]
    time = 0

    for start in range(0, total-advertise):
        if people < consumers[start+advertise] - consumers[start]:
            people = consumers[start+advertise] - consumers[start]
            time = start + 1

    answer = r_convert(time)

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. A와 B를 모두 오름차순으로 정렬
2. B를 Queue로 전환한 후, A를 이길때까지 B에서 한명씩 뽑아준다.
3. A의 인원을 이기게 된다면 카운팅 해주고 반복문 종료
4. B의 인원을 모두 뽑게 되면 종료한다.

소스 코드

from collections import deque

def solution(A, B):
    answer = 0
    A.sort()
    B.sort()
    B_queue = deque(B)

    for a in A:
        while B_queue:
            b = B_queue.popleft()
            if b > a:
                answer += 1
                break

        if not B_queue:
            break


    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제 설명

풀이 과정

1. 재귀를 배우게 되면 가장 많이 배우게 되는 하노이의 탑 문제이다.

2. 1번에서 3번으로 맨 아래의 원판을 옮기기 위해서는 다음과 같은 과정을 거친다.
   2-1) 1번에서 자기 위의 원판들을 2번으로 옮겨 둔다.
   2-2) 1번의 가장 아래 원판을 3번으로 이동한다.
   2-3) 2번으로 옮겨둔 자기 위의 원판들을 3번으로 이동시킨다.

3. 위 과정을 재귀로 작성하면 문제가 풀리게 된다.

def hanoii(answer, n, src, temp, dest):
    if n == 1:
        answer.append([src, dest])
    else:
        hanoii(answer, n-1, src, dest, temp)
        answer.append([src, dest])
        hanoii(answer, n-1, temp, src, dest)

def solution(n):
    answer = []
    hanoii(answer, n, 1, 2, 3)
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 최소 비용 신장 트리 문제라고 볼 수 있으므로 Kruskal 알고리즘 사용

2. Cycle을 판단하기 위해 Union-find 알고리즘 사용

3. Kruskal 알고리즘을 사용하여 가중치가 최소인 간선부터 골라가면서 사이클을 형성하는지 체크하고, 사이클을 형성하지 않는다면 해당 간선 사용

4. 가중치가 최소인 간선을 고르기 위해 최소 히프 사용

import heapq

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])

    return parent[a]

def union(parent, a, b):
    t1 = find(parent, a)
    t2 = find(parent, b)
    if t1 != t2:
        parent[t1] = t2

def solution(n, costs):
    answer = 0
    heap = []
    for src, dest, cost in costs:
        heapq.heappush(heap, [cost, src, dest])

    selected_edges = 0
    parent = [i for i in range(n)]

    while heap:
        cost, src, dest = heapq.heappop(heap)
        t1 = find(parent, src)
        t2 = find(parent, dest)
        if t1 != t2:
            union(parent, src, dest)
            answer += cost
            selected_edges += 1
            if selected_edges == n-1:
                break

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. referral이 부모노드를 가리키므로, 반복해서 referral을 타고 올라가면서 -가 나올때까지 10%씩 삭감해주면서 더해주면 된다.

2. 또는 10%가 0원이 된다면 그냥 더한 후 바로 종료해주면 된다.

def solution(enroll, referral, seller, amount):
    answer = [0] * len(enroll)
    people_idx = {key:i for i,key in enumerate(enroll)}
    for idx, sell in enumerate(seller):
        temp = 100 * amount[idx]
        who = people_idx[sell]
        while True:
            answer[who] += temp - temp // 10
            if temp // 10 == 0 or referral[who] == '-':
                break
            temp = temp // 10
            who = people_idx[referral[who]]

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges