log 2021-09-10
title
sport
2021 kakao intern
1
py solution
keys = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']
vals = ['0','1','2','3','4','5','6','7','8','9']
dic = {}
def solve(s):
ans = []
pos = 0
slen = len(s)
for i in range(10):
dic[keys[i]] = vals[i]
# print(dic)
while pos < slen:
l1 = s[pos]
# print('l1', l1)
if(is_int(l1)):
ans.append(str(l1))
pos+=1
# print('ADD')
continue
l3 = s[pos:pos+3]
l4 = s[pos:pos+4]
l5 = s[pos:pos+5]
if(l3 in dic):
pos+=3
ans.append(dic[l3])
# print('t1')
elif(l4 in dic):
pos+=4
ans.append(dic[l4])
# print('t2')
elif(l5 in dic):
pos+=5
ans.append(dic[l5])
# # print('t3')
# print(ans)
return int(''.join(ans))
2
py solution
dr = [1,0,0,-1]
dc = [0,1,-1,0]
def solve(places):
ans = []
for t in places:
# print('T', t)
maps = create2DArray(5,5,-1)
for rr,row in enumerate(t):
for cc,c in enumerate(row):
maps[rr][cc] = row[cc]
# print('maps',maps)
# 어떻게 해야 노가다 구현을 피할 수 있을까
# 음...
fail = False
for sr in range(5):
for sc in range(5):
c = maps[sr][sc]
if(c == 'X'):
continue
cnts_man = 0
for i in range(4):
nr,nc = sr+dr[i], sc+dc[i]
if((0<=nr<5) and (0<=nc<5)):
if(maps[nr][nc] == 'P'):
cnts_man+=1
if(c == 'O' and cnts_man>=2):
fail = True
pass
elif(c == 'P' and cnts_man >= 1):
fail = True
if fail:
ans.append(0)
else:
ans.append(1)
return ans
3
py solution
def solve(n,k,cmd):
# print(n,k,cmd)
# U, D 이동
# C 삭제, 다음 행 또는 마지막 행이면 이전 행 선택
# Z 가장 최근 삭제 복구, 선택 행은 보존
# 리턴: 각 행별 삭제 여부 OX 표시 문자열
# 제한:
# n ~ 100만
# cmd ~ 20만
# 다음 행, 이전 행에 대한 정보 및 현재 선택 행에 대한 정보가 필요
# 효율적으로 이동하려면, C로 삭제를 할 때 위아래를 연결시켜야 하는데,
# 그러면 다시 복구할때 복잡해진다.
# 또, 복구할 때 진짜 어려운 것은 커서를 어떻게 관리하느냐다.
# 삭제시에는 커서를 직접 옮겨주는데,
# 복구시에는 그대로 두면 되나??
table = {}
cursor = k+1
for i in range(1, n+1):
# prev, next, alive
newr = [i-1 if i != 1 else -1, i+1 if i != n else -1, 1, i]
table[i] = newr
# print('table', table, 'cursor', cursor)
def move(direction, amount):
nonlocal cursor
if(amount <= 0):
return
if(direction == 'U'):
next_cursor = table[cursor][0]
else:
next_cursor = table[cursor][1]
if(next_cursor != -1):
cursor = next_cursor
amount-=1
move(direction, amount)
pass
def remove():
nonlocal cursor
cur = table[cursor]
my_prev, my_next, val, num = cur
nextc = cur[1]
cur[2] = 0
# link prev's next to my next
if(my_prev != -1):
# print('table[my_prev][1] = my_next', table[my_prev][1], my_next)
table[my_prev][1] = my_next
# link next's prev to my prev
if(my_next != -1):
table[my_next][0] = my_prev
if(nextc != -1):
cursor = nextc
else:
cursor = cur[0]
return cur
def recover(target):
# nonlocal cursor
# recover
target[2] = 1
cur = table[target[3]] = target
# cur[2] = 1
my_prev, my_next, val, num = cur
# recover my prev's next to me
if(my_prev != -1):
table[my_prev][1] = target[3]
# recover my next's prev to me
if(my_next != -1):
table[my_next][0] = target[3]
pass
stack = []
for i,cmdstr in enumerate(cmd):
cmds = cmdstr.split(' ')
# print(cmds)
typ = cmds[0]
if typ == 'C':
target = remove()
stack.append(target)
elif typ == 'Z':
target = stack.pop()
# print('target',target)
recover(target)
else:
move(cmds[0], int(cmds[1]))
# print('table', table, 'cursor', cursor)
# print(''.join([str('C' if x == cursor else ('O' if table[x][2] == 1 else 'X')) for x in table]))
ans = ''.join([str('O' if table[x][2] == 1 else 'X') for x in table])
return ans
4
방식은 이해했는데, cpp에서는 map<tuple<int, map<int, int>>, bool>이런 복잡한 구조를 가지는 맵(사전) 구조를 이용하여 푸는데, 파이썬에서는 dict에 dict를 키로 사용하려 하면 nonhashable 관련 에러가 나서 안 된다.
게다가, 트릭을 사용한 hashabledict를 만들어서 시도해봐도 이중 인덱싱이 defaultdict와 겹쳐 제대로 체크되지가 않는다..
py wrong solution
class hashabledict(dict):
def __hash__(self):
return hash(tuple(sorted(self.items())))
def solve(n,start,end,roads,traps):
from collections import defaultdict
import heapq
import json
gf = defaultdict(list)
gr = defaultdict(list)
toggle_state = hashabledict()
traps_set = set()
costs = [defaultdict(lambda: 999999999999) for x in range(n+1)]
for i,v in enumerate(roads):
p,q,s = v
gf[p].append((q,s))
gr[q].append((p,s))
for v in traps:
toggle_state[v] = 1
traps_set.add(v)
def get_state_val(state, node):
nonlocal traps_set
# print('state', state)
if(node in traps_set):
return state[node]
else:
return 1
# print(gf)
# print(gr)
# print(toggle_state)
# cur_pos, cur_cost, toggle_state
init_state = toggle_state
init = (0, start, init_state)
q = []
heapq.heappush(q, init)
costs[start][init_state] = 0
# q.append(init)
while len(q)>0:
# pos, cost, state_str = q.pop()
cost, pos, state = heapq.heappop(q)
if(pos == end):
# print('END', end, cost)
return cost
# calc avail edges from current pos
forwards = gf[pos] # 현재 노드에서 나가는 집합.
backwards = gr[pos] # 현재 노드로 들어오는 집합
costs[pos][state] = cost
print('costs', costs)
# 각 on/off 상태의 state 맵으로부터,
# 현재 노드로부터 갈 수 있는 edge들을 계산.
# 일단 그러려면, 각 엣지에 대해, 연결된 노드들을 알아야 하고,
# 각 노드들의 state는 알고 있으므로 적용해주면 된다.
# 문제는, 각 엣지에 대해 연결된 노드들을 어떻게 표현할 것인가이다.
# 그리고, 모든 엣지에 대해 하면 비효율적이므로, 현재 노드에 연결되고, 들어오는 간선에
# 대해서만 검사하는게 효율적이다.
# forwards[i] : 현재 노드 state * 연결 노드 state > 0이면 가능
# backwards[i] : 현재 노드 state * 연결 노드 state < 0 이면 가능?
next_edges = []
cur_state_v = get_state_val(state, pos)
for fwd in forwards:
nn, ww = fwd
if(cur_state_v * get_state_val(state, nn) > 0):
next_edges.append((nn, ww))
for bwd in backwards:
nn, ww = bwd
if(cur_state_v * get_state_val(state, nn) < 0):
next_edges.append((nn, ww))
for next_edge in next_edges:
new_state = copy.deepcopy(state)
nn, ww = next_edge
print('test nn', nn, 'ww',ww, 'state', state)
if(nn in traps_set):
new_state[nn] *= -1
if(cost+ww < costs[nn][new_state]):
q.append((cost+ww, nn, new_state))
else:
if(cost+ww < costs[nn][new_state]):
q.append((cost+ww, nn, new_state))
pass
blog
테스트 데이터를 만드는 쪽에서도 이렇게 어려운 작업이 필요하단 것을 알았다. 신기하다. http://www.secmem.org/blog/2019/01/09/wrong-dijkstra/
Comments