초기 설계
1. for(x)문에서 케이스 배열을 순환하며 x를 start로 기억해서
이것과 같은 경우만 같은 그룹으로 생각하여 설계
2. n퀸 처럼 판단을 먼저 한 뒤에 값을 변경하고 싶었다.
ㄴ> 다만 이렇게 하면 같은 그룹에 속해있는지를 분간할 방법이 없음
초기설계에 대한 확실할 반례
1
5
2 3 4 5 4
1
3
2 3 2
일단 돌면서 자기 자신을 만났을 때만 그룹이 유효하지 않다.
화살표가 중간에 자기들끼리 연결되어 있는 경우가 있기 때문. >>> 초기1의 잘못된 경우
또한 서로가 서로를 가르키는 형국일때 초기설계는 값을 미리 변경하면서 판단하기 싫어서 기록하지 않았는데,
이러면 계속해서 Stack에 담게 된다.
4 5 4 5 이런식으로 >> 메모리초과
그렇게 하지 않고 그룹의 값을 주고 만들어지는 경우에 한 해 스택에서 뽑아내고
순환하지 않는 부분부터는 그룹화이 지정되지 않았음을 명시할 필요가 있었고
값을 계속넣어왔지만 사실상 스택에 다 담겨있으니 pop하면서 내가 담았던 값을 변경해주면 문제가 없을 것으로 생각하였음
구현
import sys
n = int(input())
case = [] #Like L
ansarr = []
for _ in range(n):
k = int(input())
ansarr.append([0] * (k+1))
case.append([0])
case[_].extend(list(map(int,sys.stdin.readline().strip().split())))
def f_stack(L,arr):
cnt = 0
for ind in range(1,len(L)):
if arr[ind]:
continue
st = ind
stack = []
stack.append(st)
cnt+=1#스택을 다 덜어내야할때 증가한거에서 빼는게 맞나?
arr[ind] = cnt
while(stack):
vec = L[stack[-1]]
if arr[vec]: ##이런 판판단 중중에 arr이 이미 있으면 스택에 있는건 전부
########################################################
if arr[vec] == arr[stack[-1]] : #while 2check rem vec!
end = vec #유효한 그룹까지 기억할 필요가 있었음
while(stack[-1]!=end):
stack.pop()
stack.pop() #end
while(stack):
temp = stack.pop()
arr[temp] = 100010
else:
while(stack): #every to 100001
temp = stack.pop()
arr[temp] = 100010
cnt-=1
else:
stack.append(vec)
arr[vec] = cnt
ans = 0
for x in arr:
if x == 100010:
ans+=1
return(ans)
for cind in range(n):
print(f_stack(case[cind],ansarr[cind]))메모리 초과일때 메모리 누수뿐 아니라,
무한루프격으로 계속 넣어주는 케이스가 있을 수가 있다는 점을 생각해야한다.
선 판단.후 방문(변경)이 항상 옳지만은 않았다.
DFS라고 해서 반드시 중간중간 값을 변경하지 않는 것은 아니다.
42Seoul