citizen   6년 전

2316번 문제를 풀다가 우연히 알게되었는데요.

 특정 객체를 담은 배열의 모든 원소를 기본값으로 지정하는 데 있어서 아래와 같이 (1)번처럼 코드를 작성하면 '시간초과'(제 생각에는 단순히 시간적인 문제는 아니라고 봅니다)가 발생하고, (2)번처럼 작성할 경우 통과가 됩니다.


N = new Node[2*n]; // Object 배열이 있을 때

(1)  Arrays.fill(N, new Node()); // 시간초과

(2)  for(i = 0; i < 2*n; i++) N[i] = new Node(); // AC


(1)번과 (2)번의 차이점이 무엇인지 알고 싶습니다. 

chogahui05   6년 전

(1)은 배열 N이 특정 객체의 주솟값으로만 채워지는 것이네요. 예를 들어서, 그 주솟값이 100번지라면

2*n짜리 배열에 100번지만 좌르륵 채워지는 것이네요.

즉, 0<=x,y<2*n인 임의의 x,y에 대해서

N[x]와 N[y]가 같은 객체를 가리키고 있다(?) 는 정도로 해석할 수 있을 듯 싶습니다.


그런데.. 보통은 객체 배열에서

모든 원소가 한 객체를 가리키게끔 코딩하지는 않잖아요..


풀 소스코드가 안 올라가져 있어서 무엇 때문에 시간 초과가 나는 것인지는 잘 모르겠습니다만..

계속 N[i]에 접근하고, 값을 업데이트 하고, 바꾸고 그래야 하는 알고리즘이 들어가 있다면

의도치 않게 N[i]뿐만이 아니라 N[x], N[y]가 가리키는 객체의 값들도 (같은 객체를 가리키고 있으므로) 


모두 업뎃이 되어버리면서 의도치 않은 동작을 수행했고, 그 때문에

시간초과가 나신 듯 싶네요.

댓글을 작성하려면 로그인해야 합니다.