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

풀이 과정

1. 현재 위치가 이미 설치된 기지국 내에 있는지 검사.
   • 있다면, 현재 위치를 설치된 기지국 밖으로 바로 점프
2. 현재 위치가 기지국 내에 있지 않다면
   • 현재 위치를 기지국의 가장 마지막 자리라고 생각하고 기지국 배치
   • w가 2라고 가정할때
   • ■□★□□ => 현재 위치가 검은상자일때 별표에 기지국을 설치한다고 생각한다.
   • 다음 위치는 현재 위치 + 2 * w + 1이 된다.

소스 코드

from collections import deque

def solution(n, stations, w):
    answer = 0
    stations = deque(stations)
    x = 1
    while x <= n:
        # deque에 없는 경우 도달 불가능한 큰 수로 임의 설정
        range_x1, range_x2 = int(10e9), int(10e9)
        if stations:
            range_x1 = stations[0]-w
            range_x2 = stations[0]+w
        if x >= range_x1 and x <= range_x2:
        # 이미 설치된 기지국 안에 있는 경우, 기지국 밖으로 점프시켜줌.
            x = range_x2 + 1
            stations.popleft()
        else: # 현재 위치에 기지국 놓아야 하는 경우
            answer += 1
            # 현재 위치가 기지국의 가장 왼쪽에 닿았을 때, 다음 위치는 2 * w + 1칸 뒤다.
            x = x + (2 * w + 1) 
    return answer

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

풀이 과정

1. 트리를 만들어주어야 하는 문제이므로 트리를 구성할 노드 class 정의
2. 모든 노드에 인덱스 달아준 다음, 모든 노드의 좌표를 y 좌표 기준 내림차순으로 정렬
3. 가장 y좌표가 큰 케이스를 루트 노드로 지정
4. 이제 y좌표 순으로 트리에 삽입
   • 삽입하려는 노드의 x좌표가 현재 노드의 x좌표보다 작다면 왼쪽 이동
   • 삽입하려는 노드의 x좌표가 현재 노드의 x좌표보다 크다면 오른쪽 이동
   • 이동 하다가 현재 노드의 left/right가 None이라면 삽입
5. 전위순회 / 후위순회를 recursion으로 구현

트리 만드는거 연습이 필요함.. 어렵게 구현

소스 코드

import sys

sys.setrecursionlimit(10**6)

class tree:
    def __init__(self, element):
        self.left = None
        self.right = None
        self.element = element

def tree_push(root, node):
    # X좌표 비교
    if root == None:
        root = node

    if root.element[0] > node.element[0]:
        if root.left == None:
            root.left = node
        else:
            tree_push(root.left, node)

    elif root.element[0] < node.element[0]:
        if root.right == None:
            root.right = node
        else:
            tree_push(root.right, node)

def preorder(node, answer):
    if node == None:
        return
    answer.append(node.element[2])
    preorder(node.left, answer)
    preorder(node.right, answer)

def postorder(node, answer):
    if node == None:
        return
    postorder(node.left, answer)
    postorder(node.right, answer)
    answer.append(node.element[2])


def solution(nodeinfo):
    answer = [[], []]
    for idx, node in enumerate(nodeinfo):
        node.append(idx+1)
    nodeinfo.sort(key=lambda x:(-x[1], x[0]))

    root = tree(nodeinfo[0])
    for i in range(1, len(nodeinfo)):
        temp = tree(nodeinfo[i])
        tree_push(root, temp)

    preorder(root, answer[0])
    postorder(root, answer[1])
    return answer

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

풀이 과정

1. 최소 히프, 최대 히프를 둔다.
2. 데이터 삽입 시 최소히프, 최대히프에 모두 저장하면서 동시에 index도 같이 둔다.
3. 데이터 삭제
   • 최솟값 삭제하는 경우에는 최소히프에서 삭제 및 index 저장
   • 최댓값 삭제하는 경우에는 최대히프에서 삭제 및 index 저장
   • 삭제하기 전에 히프에서 이미 삭제된 index인지 검사하는 과정 추가
4. 히프가 비어있다면 [0, 0]을, 히프가 비어있지 않다면 [최대히프의 맨 위, 최소히프의 맨 위] 출력

소스 코드

import heapq
def solution(operations):
    answer = []
    max_heap = []
    min_heap = []
    remove_set = set()
    index = 0
    for op in operations:
        temp = op.split()
        operation = temp[0]
        number = int(temp[1])
        if operation == 'I':
            heapq.heappush(min_heap, [number, index])
            heapq.heappush(max_heap, [-number, index])
            index += 1
        elif operation == 'D':
            if number == -1:
                while min_heap:
                    number, idx = heapq.heappop(min_heap)
                    if idx not in remove_set:
                        remove_set.add(idx)
                        break

            elif number == 1:
                while max_heap:
                    number, idx = heapq.heappop(max_heap)
                    if idx not in remove_set:
                        remove_set.add(idx)
                        break

    while min_heap:
        if min_heap[0][1] in remove_set:
            heapq.heappop(min_heap)
        else:
            break

    while max_heap:
        if max_heap[0][1] in remove_set:
            heapq.heappop(max_heap)
        else:
            break

    if len(min_heap) == 0:
        return [0, 0]
    else:
        return [-max_heap[0][0], min_heap[0][0]]
    return answer

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

• 너무 어려워서 다른 사람들이 풀이한 것들을 참고함.. 동적 계획법이 약함.

풀이 과정

1. 각 단계에서 나올수 있는 수를 따로 table에 저장해 둠.
2. 현재 단계로 도달할 수 있는 모든 케이스에 대하여 set으로 저장한 후 table에 저장
   • 현재 단계가 4단계라면, 1단계 + 3단계, 2단계 + 2단계, 3단계 + 1단계로 4단계로 도달 가능하다.
   • 각각의 케이스에 대해 덧셈, 뺄셈, 곱셈, 나눗셈 검사
3. 현재 단계에서 number이 있는지 검사하고 있다면 바로 return

소스 코드

from collections import deque

def solution(N, number):
    answer = -1
    table = []
    for i in range(1, 9):
        middle_set = set()
        middle_set.add(int(str(N) * i)) # 쭉 붙인거는 따로 추가
        for j in range(0, i-1):
            for k in table[j]:
                for l in table[-j-1]:
                    middle_set.add(k + l)
                    middle_set.add(k - l)
                    middle_set.add(k * l)
                    if l != 0:
                        middle_set.add(k // l)
        if number in middle_set:
            return i
        table.append(middle_set)


    return answer

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

풀이 과정

1. 현재 위치를 도달하기 위해서는 n-1cm에서 1cm 뛰거나 n-2cm에서 2cm 뛰어야 함.
   • 따라서, dp[i] = dp[i-1] + dp[i-2]
2. 위 과정을 1~n까지 아래에서 위로 진행하면 된다.
3. dp[n] 리턴

소스 코드

    def solution(n):
    answer = 0
    dp = [1] + [0] * n
    for i in range(1, n+1):
        if i-1 >= 0:
            dp[i] += dp[i-1]
        if i-2 >= 0:
            dp[i] += dp[i-2]
    answer = dp[n] % 1234567

    return answer

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

풀이 과정

1. DP를 사용하는 문제일 거 같아서 처음에는 현재 금액 기준으로 도달할 수 있는 모든 경우의 수를 계산하였음.
   • dp[i] = dp[i] + dp[i-coin[j]] if (i - coin[j] >= 0)
   • dp[0] = 0
2. 위와 같은 방법으로 하게 되면 중복에 대한 처리가 전혀 되지 않아서 안되는 것 같았음.
   • (1, 2, 2)랑 (2, 1, 1)은 같은 방법
3. 고민하다 다른 사람들의 풀이를 보니 동전별로 dp 적용
   • 동전 단위로 DP 적용
   • dp[i] = dp[i] + dp[coin], 루프를 돌면서 하나의 동전만
4. 위처럼 하면 항상 새로운 방식으로만 개수가 세어짐.
   • 4라고 가정하고, 동전이 (1,2,4)일 때 위 방식으로 한다면..
   • 1, 1, 1, 1
   • 1, 1, 2
   • 2, 2
   • 4

소스 코드

    def solution(n, money):
    answer = 0

    dp = [0] * (n+1)
    dp[0] = 1

    for m in money:
        for i in range(1, n+1):
            if i - m >= 0:
                dp[i] += dp[i-m]
            print(dp, m)
    answer = dp[n] % 1000000007

    return answer

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

풀이 과정

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