[SW정글] Week 02 개발일지

 

Week 02 개발일지

이진 탐색

• 정렬된 배열에서만 사용 가능
• 시간 복잡도 O(logN)
• Python Bisect 라이브러리

분할 정복

Stack

• LIFO
• push, pop, top

Queue

• FIFO
• enqueue, dequeue, front, rear
• Ring buffer(원형 큐)
• Deque
  • 양방향으로 삽입과 삭제가 가능한 자료구조
  • Python collections 라이브러리의 deque

Priority Queue

• 대표적으로 Heap Tree
• 데이터에 우선순위를 부여하여 우선순위가 높은 데이터부터 Dequeue하는 방식
•  

기타

• Line Sweep 알고리즘
  • 정렬된 요소들을 한번만 순회하면서 연산을 하면 답이 나오는 알고리즘
• 던더 함수(Double Underscore Function)
  • obj.len() → len(obj)
  • obj.contain(x) → x in obj

Test

5904번: Moo 게임

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

# n번째 글자가 있을 수 있는 moo수열 길이와 사이 문자열 계산
now = 3
between = 3
while n > now:
    between += 1
    now = (now * 2) + between


def moo(now, between, n):
    if now == 3:
        return "m" if n == 1 else "o"

    # moo = pre_moo + between + pre_moo
    # 바로 전 moo수열 길이 계산
    pre_moo = (now - between) // 2

    # n이 양쪽 pre_moo 수열 부분에 있을 때 재귀
    if n <= pre_moo:
        return moo(pre_moo, between - 1, n)
    elif n > pre_moo + between:
        return moo(pre_moo, between - 1, n - pre_moo - between)

    # n이 between 부분에 있을 때 반환
    else:
        return "m" if n - pre_moo == 1 else "o"


print(moo(now, between, n))

9935번: 문자열 폭발

import sys

input = sys.stdin.readline

string = input().strip()
bomb = input().strip()


def bomb_string(string, bomb):
    stack = []
    bomb_length = len(bomb)
    last_bomb_char = bomb[-1]

    for char in string:
        stack.append(char)

        # bomb의 마지막 문자만 체크하다 발견시 bomb 문자열 확인
        if char == last_bomb_char and stack[-bomb_length:] == list(bomb):
            del stack[-bomb_length:]

    if not stack:
        return "FRULA"
    return "".join(stack)


print(bomb_string(string, bomb))

1933번: 스카이라인

from heapq import *
import sys

input = sys.stdin.readline

n = int(input())
b_arr = [list(map(int, input().split())) for x in range(n)]


def skyline(b_arr):
    arr, heap, result = [], [], []

    # 건물 시작점(True), 끝점(False)을 구분해서 리스트 생성
    # idx는 b_arr 인덱싱을 통해 건물 높이와 끝점 찾기 위함
    for idx, b in enumerate(b_arr):
        arr.append([b[0], True, idx])
        arr.append([b[2], False, idx])

    # 정렬
    # 우선순위 1 : x좌표. 오름차순 -> Sweeping
    # 우선순위 2 : 시작점, 끝점. 시작점 먼저 -> 끝점과 시작점이 겹치는 경우 시작점 우선
    # 우선순위 3 : 건물의 높이. 내림차순 -> 시작점이 겹치는 경우 건물 높이 큰 것 우선
    arr.sort(key=lambda x: (x[0], -x[1], -b_arr[x[2]][1]))

    for x in arr:
        height = b_arr[x[2]][1]
        end = b_arr[x[2]][2]

        # 시작점일 때
        if x[1]:
            # 건물이 하나도 없거나 시작하는 건물의 높이가 현재 최대 높이보다 높을 때
            # Log 작성
            if not heap or height > -heap[0][0]:
                result.append([x[0], height])

            heappush(heap, [-height, end])

        # 끝점일 때
        else:
            # 끝나는 건물의 높이가 현재 최대 높이 때
            if heap and -heap[0][0] == height:
                heappop(heap)

                # 이미 끝난 높이들 끝점 위치를 통해 heap에서 삭제
                while heap and heap[0][1] <= end:
                    pop = heappop(heap)

                if heap:
                    # 높이가 같은 두 건물의 시작점과 끝점이 겹칠 때
                    # Log 출력 없이 이어지게 하기 위해서
                    if -heap[0][0] != height:
                        result.append([x[0], -heap[0][0]])
                else:
                    result.append([x[0], 0])

    return result


for i, j in skyline(b_arr):
    print(i, j, end=" ")