[Today I Learned 06] 1. 백준 (#1992, #9935, #2014)

문제는 #1992, #9095, #1182이다. 이번에도 마찬가지로 3문제 중 1문제 맞추는게 목표였는데, 다행이 1문제를 맞췄다. 하지만 한편으로 저번주는 3문제 맞췄는데 이번주는 1문제만 맞춰서 '공부를 저번주 보다 열심히 안했나?'라는 생각을 가지게 되었다. #1992문제는 시험이 끝나고 3분뒤에 풀긴 했지만 아직 코드를 보고 생각하는 시간하고 구현하는 시간이 오래 걸리는 듯 했다. 차례대로 푼 문제를 리뷰해보자!!

1. 쿼드트리(#1992)

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.
주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

이 문제를 시험이 끝나고 3분뒤에 해결했다. 이번주에 공부했던 색종이 문제와 매우 유사한 문제인데 색종이 문제를 공부를 제대로 안하고 답을 보고 풀어서 다시 생각하면서 풀 때 시간이 오래 걸린 것 같다.

문제 풀이는 간단하게 분할 정복으로 해결할 수 있다.
1. 배열의 첫번째 색상을 뽑아서 배열에 전체를 돈다.
2. 다른 색상이 나오면 '('를 열고 4분면으로 쪼갠다.
3. 같은 색상이 나오면 숫자를 출력한다.
4. 4분면을 다 돌았으면 ')'를 닫는다.
간단한 문제였지만 처음에 쉽게 떠오르지 않았던 것 같다.

from sys import stdin

input = stdin.readline

n = int(input())
arr = [input() for _ in range(n)]

def func(x, y, n):
    color = arr[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != arr[i][j]:
                print('(', end='')
                # 배열의 크기를 반으로 줄인다.
                func(x, y, n//2) # 1사분면
                func(x, y+n//2, n//2) # 2사분면, 2사분면의 처음 색상은 y좌표가 y + n의 반이여야 된다. 
                func(x+n//2, y, n//2) # 3사분면, 3사분면의 처음 색상은 x좌표가 x + n의 반이여야 된다.
                func(x+n//2, y+n//2, n//2) # 4사분면, 4사분면의 처음 색상은 x좌표가 x + n의 반, y좌표가 x + n의 반이여야 된다.
                print(')', end='')
                return
    else:
        print(color, end='')
func(0, 0, n)

2. 문자열폭발(#9935)

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
  상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
  폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

시간안에 유일하게 푼 문제이다. 풀면서 주석을 잘 달아놓았기 때문에 따로 설명을 하지 않는다.

from sys import stdin, stdout
input = stdin.readline
print = stdout.write

str = input().rstrip()  # 입력 문자열
boom = input().rstrip()  # 폭발 문자열
boom_end = boom[-1]  # 폭발 문자열 끝 문자
boom_size = len(boom)  # 폭발 문자열 크기
result = []  # 스택 배열

# 입력 문자열을 하나씩 꺼내여 반복
# 스택에 추가
for s in str:
    result.append(s)
    
    # 현재 문자와 폭발 문자열의 끝자리가 같고 
    # 스택에서 폭발 문자열의 길이 만큼 뺀 문자열이 폭발 문자열과 같으면
    # 폭발 문자열 길이 만큼 pop
    if s == boom_end and "".join(result[-boom_size:]) == boom:
        for _ in range(boom_size): result.pop()

# 스택이 비어있지 않다면 문자열 연결
# 스택이 비어있다면 FRULA 출력
if result:
    print("".join(result))
else:
    print("FRULA")

3. 소수의 곱(#2014)

문제

K개의 소수가 있다. 이때, 이 소수들 중에서 몇 개를 곱해서 얻게 되는 수들이 있을 것이다. 소수들을 선택할 때에는 같은 수를 선택해도 되며, 주어지는 소수 자체도 포함시키자.
예를 들어 세 소수가 2, 5, 7이었다면, 이러한 곱들을 오름차순으로 나타내 보면, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 등이 된다.
K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자. 단 정답은 231보다 작은 자연수이다.

입력

첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제에서 설명한 대로 소수의 곱을 나열했을 때, N번째 오는 것을 출력한다.

이 문제는 읽기도 전에 시험 시간이 끝났다. 끝나고 나서 풀어봤는데 처음에 단순히 모든 경우의 수를 곱해서 set()하고 찾으니깐 시간 초가되었다. 시험이 끝나고 코치님이 우선순위 큐를 이용해서 풀면 된다고 해서 우선순위 큐로 풀어봤다. 자세한 내용은 코드에 주석을 달아놓았다.

from sys import stdin
import heapq
input = stdin.readline

K, N = map(int, input().split()) # K: 배열의 개수, N: 찾을 인덱스
arr = list(map(int, input().split())) # 입력 받은 소수 배열
heap = [] # 힙 배열

# 입력 받은 소수 배열을 힙 배열에 초기화
for i in arr:
    heapq.heappush(heap, i)
    
# 찾을 인덱스 까지 반복
for i in range(N):
    # 힙 배열에서 최소값을 빼줌
    num = heapq.heappop(heap)
    # 입력 받은 소수 배열 반복
    for j in arr:
        # 힙 배열에 소수의 곱을 넣어줌
        new = num * j
        heapq.heappush(heap, new)
        # 효율성을 위해 중복된 수는 아예 넣지 않기 위해 작성
        # 예를 들어 2*3을 했는데 다음에 3*2도 해주지 않게 하기 위해서와
        # 4*2와 6*2는 같은 12이다.
        # 쉽게 말해서 heap 계속 배수를 넣기 때문에 자신의 약수를 만나면 종료
        if num % j == 0: break
else: # 반복문이 다 끝났을 때
    print(num)