원티드 주관 코딩테스트를 22년 1회차 문제를 풀어보게 되었다.
https://www.wanted.co.kr/events/showmethecode
2회차가 6월 30일까지 신청을 받고 있고 7월 2일에 예정되어 있어서 연습겸해서 풀어보게 되었다. 문제의 난이도는 엄청 어렵다고 할 수는 없겠지만 나한테는 어려웠다…

boj1094

A번

https://www.acmicpc.net/problem/24954
A번 문제는 브루트포스로 모든 조건을 찾아주면서 풀어주면 가능하다.
처음에 풀 때 deepcopy를 이용했는데 deepcopy가 시간을 많이 잡아먹는줄 몰랐다.
그래서 문제 시간이 여유로움에도 시간 초과가 나게 되었다.
slicing하는 것으로 바꿔서 통과하게 되었다.

풀이

from itertools import permutations
import sys; input=sys.stdin.readline
n=int(input())
sale=[]
val=list(map(int,input().split()))
index={} # index값을 dict로 만들어서 넣어주도록 했다.
for i in range(len(val)):
    index[val[i]]=i

# sale값 넣어주기
for i in range(n):
    p=int(input())
    temlist=[]
    for j in range(p):
        temlist.append((list(map(int,input().split()))))
    sale.append(temlist)

ans=100001
# permutations을 이용해서 전체 순회
for i in permutations(val,n):
    s=0
    tempval=val[:]
    for j in i:
        for x,y in sale[index[j]]:
            tempval[x-1] = 1 if tempval[x-1]-y<=1 else tempval[x-1]-y 
        s+=tempval[index[j]]
    ans=min(s,ans)
print(ans)

어렵지 않게 풀수 있을 것 같았는데 너무 뱅뱅 돌아서 푼 감이 있는 것 같다.

B번

https://www.acmicpc.net/problem/24955
이 문제는 이해하는데 시간이 정말 오래걸렸다.
혹시 이런저런 예외가 있지는 않을까 하면서 생각을 많이 했는데 하지만 결국에는 dfs, bfs문제였다.

풀이

from collections import deque
import sys; input=sys.stdin.readline
n, q = map(int, input().rstrip().split())
arr = [""]+input().rstrip().split() # index 1서부터 시작
road={}
for i in range(n+1):
    road[i]=[] 
for i in range(n-1):
    a,b=map(int,input().split())
    road[a].append(b); road[b].append(a) # dic-list로 연결
for i in range(q):
    visited=[False]*(n+1)
    queue=deque()
    x,y=map(int,input().split())
    visited[x]=True
    queue.append((x,arr[x]))
    while queue:
        c,d=queue.popleft()   
        if c==y:
            print(int(d)%1000000007)
            break
        for adj in road[c]:
            if not visited[adj]: # 방문 확인
                visited[adj]=True
                queue.append((adj,d+arr[adj]))

많이 풀어본 듯한 bfs문제이지만 문제 지문이 어려워서 이해하기 힘들었고 시간이 오래걸렸다.

C번

https://www.acmicpc.net/problem/24956
처음시도한 풀이는 단순하게 이렇게 했다.

from math import pow
n=int(input())
s=input()
d={"W":[], "H":[], "E":[]}
for index, ch in enumerate(s):
    if ch=="W":
        d["W"].append(index)
    elif ch=="H":
        d["H"].append(index)
    elif ch=="E":
        d["E"].append(index)
ans=0
for a in d["W"]:
    for b in d["H"]:
        count=0
        if a<b:
            for c in d["E"]:
                if b<c:
                    count+=1
            if count >= 2:
                ans+=int((pow(2,count)-count-1))%1000000007 # 이항계수의 성질 이용
print(int(ans)%1000000007)

이항계수의 성질인 2^n = nC0+nC1+nC2+...nCn-1+nCn 을 이용해서
2^n-n-1 = nC2+...nCn-1+nCn 이렇게 풀려했다.

그런데 시간초과도 아닌 overflow에러가 나버렸다.
파이썬으로 문제를 풀었는데 overflow라니….
알고보니 pow가 반환형이 float이여서 overflow가 발생하게 되는 것이였다.

그래서 math.pow가 아니라 그냥 pow를 썼는데 (math.pow는 반환형이 float pow는 int) 여기서는 시간초과가 나게 되었다.
내장함수 pow가 시간복잡도가 O(n)이기에 발생하는 일이였다.

def power(a,b,m):
    result = 1
    while b > 0:
        if b % 2 != 0:
            result = (result * a) % m
        b //= 2
        a = (a * a) % m
    return result

그래서 이런식으로 power라는 함수를 만들어서 제곱하는 log(n)으로 끝내보려했지만 여기서도 시간초과가 나게 되었다.
여기서 생각한것이 반복문을 너무 많이 도는구나 생각이 들어서 풀이의 방향을 조금 틀게 되었다.

def power(a,b,m):
    result = 1
    while b > 0:
        if b % 2 != 0:
            result = (result * a) % m
        b //= 2
        a = (a * a) % m
    return result
W=[0]*200001; E=[0]*200001
w_count=0; e_count=0
n=int(input())
s=input()

for idx,ch in enumerate(s):
    if ch=="W":
        w_count+=1
    elif ch=="E":
        e_count+=1
    W[idx]=w_count; E[idx]=e_count
ans=0
for i in range(len(s)):
    if s[i]=='H':
        if W[i]>0:
            p=e_count-E[i]
            if p >=2: 
                ans+=((power(2,p,1000000007)-p-1)*W[i])%1000000007
print(ans%1000000007)

이런식으로 W[], E[]에다가 index별 가지고 있는 숫자를 기억해서 풀게 되었다.
이렇게 해서 nlog(n)으로 풀게 되었다.
다른 분들 풀이 보니까 O(n)으로 풀던데 엄청 대단했다. 어떻게 그런 생각을 하게되는지 신기했다.

다 풀고 나니까 쉬워보이지만 푸는 순간에는 너무 답답하고 어려웠다.
조금 더 훈련이 필요할 것 같다.

Comments

You May Also Enjoy