[정글 WEEK02_알고리즘] 개발 일지 - 시험

1. 10815_숫자카드

 ms의 각 요소 m이 ns에 존재하는지 확인할 때, 이분탐색을 쓰기 위해서 list로 구성한 ns를 정렬했다.
만약 m이 ns에 존재한다면 bisect_left(ns, m)의 결과는 기존 인덱스의 왼쪽 값, bisect_right(ns, m)의 결과는 기존 인덱스의 오른쪽 값이 나와 서로 다를 것이다. 이 때는 result에 1 추가한다.
m이 ns에 존재하지 않는다면 bisect_left 결과값과 bisect_right 결과값이 같을 것이고 이 때는 result에 0을 추가한다.
그리고 매번 print하면 시간초과가 나기 때문에 한번에 result를 언패킹한 결과를 print 했다.

 

또다른 풀이법으로는 ns를 dict 또는 set으로 구성하고 m이 ns에 있는지 m in ns로 조회하는 방법도 있다.

 

list + bisect과 set을 쓰는 방식 중 set 방식이 두배 정도 더 빠른데, 그 이유는 set은 해시 테이블을 만들어서 더 많은 메모리를 사용하지만 그 덕분에 조회 속도는 O(1)로 훨씬 빠르고, list + bisect는 메모리를 적게 쓰지만 매번 O(log N)의 이진 탐색 연산 수행이 필요하기 때문이다. 

 

import sys
import bisect

input = sys.stdin.readline
N = int(input())
ns = sorted(list(map(int, input().split())))
M = int(sys.stdin.readline())
ms = list(map(int, input().split()))

answer = []
for m in ms:
    if bisect.bisect_left(ns, m) != bisect.bisect_right(ns, m):
        answer.append(1)
    else:
        answer.append(0)

print(*answer)

 

 

2. 1966_프린터 큐

 먼저 weigted_vals에서 가장 큰 중요도를 가진 요소가 0번째 인덱스에 올 때까지 왼쪽 방향으로 rotation 하고 0번째 인덱스에 왔다면 popleft()를 하는 로직을 print 순서를 파악하고 싶은 요소의 중요도가 가장 커질 때까지 반복한다.

 
 rotation을 쉽게 구현하기 위해서 list 대신 deque를 쓰고, 핵심 로직은 아래와 같다.

• 첫번째 요소보다 중요도가 큰 요소가 있으면 첫번째 요소를 마지막으로 보낸다.
• 첫번째 요소보다 중요도가 큰 요소가 없으면 첫번째 요소를 출력
• 출력한 요소가 찾는 요소이면 출력하고 종료

자세하게는
큰 분기는 weighted_vals에서 가장 큰 중요도를 가진 요소가 0번째 인덱스가 아닌 상황과 0번째 인덱스에 있는 상황으로 나눠진다.

 

먼저, weighted_vals에서 가장 큰 중요도를 가진 요소가 0번째 인덱스가 아닐 때, importance를 왼쪽으로 rotation해주고 n을 추적하기 위해서 n이 0이 아닐 경우 n을 -1 해준다. 인덱스가 하나씩 앞으로 이동하기 때문이다. n이 0이라면 n에 len(rotation) -1을 할당해서 맨 뒤 인덱스를 할당해준다.

 

이렇게 하다보면 가장 중요도가 큰 요소가 맨 앞에 온 순간이 올 것이고, 그럼 importance에서 가장 큰 중요도를 가진 요소가 0번째 인덱스인 상황을 처리하는 분기를 타게 된다.

일단 가장 큰 중요도를 가진 요소를 pop 해주고 count + 1 해준다. 이 때 n이 0이라면 우리가 찾는 요소를 찾은 것이기 때문에 count를 return 해주고 아니라면 idx를 -1 해준다.

 

이 과정을 찾고 있는 요소의 중요도가 가장 커질 때까지 반복하고 해당 count 값을 출력한다.

from collections import deque

def find_print_order(idx: int, weighted_vals: deque) -> int:
    count = 0
    while True:
        # max 가중치가 0번째 인덱스에 위치하지 않은 경우
        if weighted_vals[0] < max(weighted_vals):
            if idx == 0:
                idx = len(weighted_vals) -1
            else:
                idx -= 1
            weighted_vals.rotate(-1)

        # max 가중치가 0번째 인덱스에 위치한 경우
        else: 
            weighted_vals.popleft()
            count += 1
            if idx == 0:
                return count
            else:
                idx -= 1

N = int(input())

for _ in range(N):
    n, idx = map(int, input().split())
    weighted_vals = deque(map(int, input().split()))
    print(find_print_order(idx, weighted_vals))

 

3. 9935_문자열 폭발 

 첫 번째 풀이는 재귀로 했다. 폭탄이 문자열에 있다면 bomb을 빈 문자열로 바꾸는 작업을 재귀적으로 수행하고, 폭탄이 문자열에 없다면 return한다.

 

 두 번째는 스택으로 풀었다. 문자열 하나하나를 스택에 넣은 후 스택의 길이가 폭탄의 길이보다 클 때부터 -폭탄의 길이부터 마지막 요소까지 슬라이싱 후 join한 결과과 폭탄이라면 -폭탄의 길이부터 마지막 요소까지 삭제한다.

이후 스택에 요소가 남아있으면 요소들을 join하고, 스택에 요소들이 남아있지 않다면 "FURLA"를 출력한다. 

def explode_recursive(string: str, bomb: str) -> str:
    if bomb not in string: 
        return string
    string = string.replace(bomb, "")
    return explode_recursive(string, bomb)

def explode(string: str, bomb: str) -> str:
    stack = []
    bomb_len = len(bomb)

    for s in string:
        stack.append(s)

        if len(stack) >= bomb_len and ''.join(stack[-bomb_len:]) == bomb:
            del stack[-bomb_len:]
    
    return  ''.join(stack) if stack else 'FRULA'

string = input()
bomb = input()
print(explode(string, bomb))