[정글/시험] 2주차 시험 회고

이번 시험은 쉽게 나온 편이라고 하셨다.

나도 풀면서 많이 어렵게 느껴지지는 않았다.

다만 큐 라이브러리 사용하는 연습을 안 해서 라이브러리 임포트하고 함수 사용하는 데 시간을 많이 썼던 것 같다.

1. 숫자 카드

https://www.acmicpc.net/problem/10815

문제 의도는 이분 탐색이지만 set으로 풀어도 되는 문제이다.

해시함수를 이용해서 각 값의 인덱스를 구한 후 그 곳에 저장하면 O(1)의 속도로 접근할 수 있다.

import sys

n = int(sys.stdin.readline())
arr1 = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
arr2 = list(map(int, sys.stdin.readline().split()))

arr1.sort()
result = []

for val in arr2:
    left = 0
    right = n-1

    while left<=right:
        mid = (left+right)//2
        if val == arr1[mid]:
            result.append(1)
            break
        if val > arr1[mid]:
            left = mid + 1
        else:
            right = mid - 1
    if left > right:
        result.append(0)

for r in result:
    print(r, end=" ")

2. 프린터 큐

https://www.acmicpc.net/problem/1966

큐에 하나의 값이 아닌 데이터 쌍을 push, pop할 수 있는지 확인하는 문제였다.

push, pop의 기준이 되는 값과 우리가 출력해야 하는 값이 분리되어 큐 안에서 데이터 쌍으로 움직인다.

import sys
from collections import deque

tc = int(sys.stdin.readline())

for _ in range(tc):
    cnt = 0
    q = deque()
    n, m = map(int, sys.stdin.readline().split()) # n 문서 개수 m 현재 찾는 문서의 위치
    w = list(map(int, sys.stdin.readline().split())) # 문서의 중요도

    if n==1:
        print(1)
        continue

    for i in range(n):
        q.append([w[i],i+1])

    while q:
        max_val = max(list(q))[0]
        first_element = q[0][0]

        if max_val == first_element:
            tmp = q.popleft()
            cnt += 1

            if tmp[1]==m+1:
                print(cnt)
                break
        else:
            q.append(q.popleft())

 

3. 문자열 폭발

https://www.acmicpc.net/problem/9935

시간 내에 못 풀었던 문제이다. 

스택 문제임은 알겠는데 디테일한 부분까지 설계하기 어려웠다.

import sys

string = sys.stdin.readline()
target = sys.stdin.readline()
arr = list(string[i:i + 1] for i in range(0, len(string) - 1))
stk = []
cnt = 0


def is_same(a: list, b: string):
    for i in range(len(a)):
        if not a[i] == b[i]:
            return False
    return True


while stk:
    for val in arr:
        if len(stk) == len(target) and is_same(stk, target):
            for _ in range(len(stk)): stk.pop()
        stk.append(val)

여기까지 쓰고 제출함 (사실 2번을 오래 잡고 있어서 15분정도밖에 없었다)

 

시험이 끝나고 다시 30분을 재고 풀어봤는데 또 실패했다.

 

실패한 설계 :

문자열의 앞에서부터 하나씩 스택에 넣다가 그 값이 폭발물의 맨 앞글자와 일치하면 그 때부터 폭발물 길이만큼 for문을 순회하며 문자열을 push받는다. 이 값이 폭발물과 일치하면 폭발물 길이만큼 pop하고 아까 발견한 인덱스+1 부터 다시 똑같이 진행한다.

폭발물과 일치하지 않으면 폭발물 길이-1만큼 pop하고 아까 발견한 인덱스+1 부터 똑같이 진행한다.

 

이 방법을 사용하면 CC44와 같은 경우를 찾지 못한다. 중간의 C4가 폭발되고 다시 문자열이 합쳐져서 또 C4가 생기는데 

폭발물의 첫 글자인 C를 기준으로 찾으면 해결할 수 없다.

 

import sys

string = sys.stdin.readline()
target = sys.stdin.readline()
s = list(string[i:i+1] for i in range(0, len(string)-1))
t = list(target[i:i+1] for i in range(0, len(target)-1))

stk = []
i=0
found = 0 # 폭탄을 찾은 개수

for i in range(len(s)):
    stk.append(s[i])
    if stk[-1]==t[len(t)-1]: # target의 끝 글자와 같으면 스택에서 target만큼 꺼내서 target과 같은지 확인
        flag = False
        if len(stk)>=len(t):
            stk_value = stk[i-len(t)+1-(found*len(t)):i+1-(found*len(t))]
            if stk_value == t:
                flag = True
        if flag :
            found += 1
            for _ in range(len(t)):
                stk.pop()

if len(stk)==0:
    print('FRULA')
else:
    for i in stk:
        print(i,end="")

 

정답 코드이다. 

 

문자열을 스택에 넣다가 폭발물의 끝 글자와 일치하는 값을 발견하면 스택의 top에서 폭발물 길이만큼 추출한 값이 폭발물과 일치하는지 확인한다. 일치한다면 폭발물 길이만큼 pop한다.

 

그 후 다음 문자열을 계속해서 스택에 넣기 때문에 CC44와 같은 경우를 해결할 수 있다.

CC4 -> 4가 폭발물 마지막 글자와 같으므로 마지막 C4 제거

C

C4 -> 다음 문자로 4가 들어오기 때문에 또 C4가 만들어짐 -> 폭발물로 인식해서 제거됨

 

import sys

string = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()
stk = []

for s in string:
    stk.append(s)
    if s == t[-1]: # 스택에 넣은 값이 타겟의 마지막 값과 같으면
        if stk[-len(t):] == list(t): # 스택에서 target 개수만큼 꺼내서 target과 같은지 확인하기
            for _ in range(len(t)): # 같으면 target 개수만큼 pop
                stk.pop()

if not stk:
    print('FRULA')
else:
    for i in stk:
        print(i,end="")

 

더 개선된 코드이다.

 

내가 짠 코드는 아무리 생각해도 스택의 부분 문자열을 구하는 과정이 너무 복잡해서 분명히 더 간단한 방법이 있을 것 같았다.

그래서 같은 팀원한테 물어봤는데 파이썬 특징을 살려서 너무 간단하게 구현하셔서 나도 비슷하게 줄여봤다.

훨씬 보기 좋은걸?