괄호변환
문제풀이
- 동빈북한테 배울 점
- 완전괄호 형태를 찾을 때 나는 요소들을 stack에 넣고 빼면서 확인했는지 동빈북은 count라는 int변수를 증감시키면서 해결했다는 점
- u, v로 분리할 때도 나는 left, right 변수를 줬는데 동빈북은 left 변수 하나로 증감시키면서 해결했다는 점
- 똑똑이 풀이한테 배울 점
- '('를 ')'로 혹은 그 반대로 바꾸는 과정에 대해서 나는
u = u[1:-1] #똑똑이(solution2)풀이는 lambda를 이용해서 한줄로 new_u = '' for c in u : if c == '(': new_u += ')' else: new_u += '(' u = new_u- 똑똑이는
list(map(lambda x:'(' if x==')' else ')',p[1:i])))
연산자 끼워넣기
내 풀이
permutation으로 해줬다.
set을 안하면 통과 x인데
set 하면 통과
재귀로 풀었을 때랑 시간차이가 5배 정도 난다
동빈북풀이
- 이거 재귀로 중복을 허용한 조합의 수를 구하는 방식
- 이 풀이에 저번 문제에서 동빈북은 dfs로 순열 구하는 방식 이용했는데 같이 보면 좋을 것 같다.
def dfs(i, now):
print("=============")
global min_value, max_value, add, sub, mul, div
print(i, add, sub, mul, div)
if i == n:
min_value = min(min_value, now)
max_value = max(max_value, now)
else:
if add > 0 :
add -= 1
dfs(i+1, now + data[i])
add += 1
if sub > 0 :
sub -= 1
dfs(i+1, now - data[i])
sub += 1
if mul > 0:
mul -= 1
dfs(i+1, now * data[i])
mul += 1
if div > 0:
div -= 1
dfs(i+1, now // data[i])
div += 1 - 이 풀이를 보면서 이렇게 되면 전역변수가 계속 바뀌어서 다음 turn에서 전역변수가 바뀌어야 하는 것 아녀? 했는데 아니다.
- 재귀가 될 때 해당 데이터들을 복사해서 들고 가서 가능한 풀이같다. 자바에서는 어떤지 궁금하다. 풀어보고 싶다.
전역변수일 경우,
한 depth 들어갈때(Depth1) 복사본을 저장합니다. (데이터가 map1이라고 하겠습니다.)
다음 depth 들어갈때(Depth2) 또 복사본을 저장하고 (map2) 나올때 복원하면 전역변수에 저장된 map2가 복원됩니다.
depth1으로 나와서 다시 return 될때에는 전역변수의 값으로 복원할텐데 이미 Depth2에서 map2로 덮어써졌기 때문에
다시 복원된 결과가 map2가 됩니다.
https://www.acmicpc.net/board/view/19295
product 이용한 풀이가 있는데 잘 모르겠다.
감시피하기
파이썬 이중포문 빠져나오는 방법
https://stackoverflow.com/questions/653509/breaking-out-of-nested-loops
- else: continue를 이용한다
for x in xrange(10):
for y in xrange(10):
print x*y
if x*y > 50:
break
else:
continue # only executed if the inner loop did NOT break
break # only executed if the inner loop DID break동빈북 풀이
- 나는 dfs를 써보고자 combinations를 안쓰고 했는데 동빈북은 combinations를 사용했다.
인구이동
- 문제
- 옛날코드
- 시간초과 해결 못함 pypy로 풀었을 때 통과
- 두번째 풀었을 때 코드
- 시간초과 해결
- 동빈북풀이
지금 풀이
일단 시간을 줄이는 방법에서 2가지가 있었다.
1. for문을 2번씩 while문으로 도는 것이 아니라 추가할 친구들만 넣어주는 것. 이번 초에서 변경이 안된 친구들은 다음판에 굳이 확인할 필요가 없다.
- 만약 주변이 바뀌어서 나랑 그 주변에 차이가 경계가 열리는 범위 안에 들어간다고 해도 그 주변이 바뀐 친구를 검사하면서 포함될 것이다.
- 주변도 하나도 안바뀌고 나도 안바뀌었으면 여전히 난 주변인들과 범위 차가 범위 안에 들지 않아 검사할 필요가 없다.
그래서 아래 코드에 search()로 넣어 주었다.
- visited를 매 초마다 그래프를 생성하지 않고 방문한 초를 저장하도록 하면 이번판에서 방문 안한 친구들이 구분할 수 있다.
그런데 중요했던 건, 이 visited를 언제 처리해줄지에 따라서 답이 달랐다.
지금 풀이 자바
와 너무 오래걸렸어. 파이썬 푼 방법으로 풀면 안풀리고 그냥 동빈북 풀이 응용해서 풀었다. 파이썬 풀이는 도대체 왜 자바에서 안되는 것일까
옛날 풀이
- 나는 DFS를 이용해서 풀었는데 그렇게 되면 런타임에러가 났다. 왜그런지 이렇게 저렇게 찾아보니 RecursiveError : maximum recursion depth exceeded while pickling an object 일 것이라고 생각했다.
- https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=luiz4our&logNo=220642911892 여기를 보고
- import sys
sys.setrecursionlimit(10000) - 이를 작성하여 늘려줬더니 해당 부분은 통과했지만 시간 초과가 났다.
- 이 문제는 Queue를 이용해서 풀어야 하나보다. 언제 DFS를 쓸지 고민이 된다.
spring, java학습