ehdghks709   1년 전

a는 1부터 100000까지의 숫자가 push되었는지를 나타내는 배열입니다. n이 입력되었으면 a[n]=1, 아니면 0입니다.

숫자 n까지 push되면 num은 n이 됩니다.

nownum은 pop되는 순간의 위치를 알려줍니다.

b는 +, -를 저장하는 배열입니다.

각 단계에서 cmd가 추가되며 b[cmd]에 + 또는 -를 저장합니다.

x는 새로 입력받는 값이며 y는 한 단계 전에 받았던 x값입니다.

x와 y, 즉 새로 입력받은 값과 전 단계에서 입력받은 값을 비교해 x값이 더 크면 num을 추가시키고 b[cmd]에 +를 입력하고 a[num]을 0으로 만들어 num을 pop했다는 표시를 해 줍니다.

y>x면 j가 nownum부터 시작해 arr[j]가 0이 아닐 때까지 j를 낮춰갑니다. arr[j]=1일 때 j값이 x와 같으면 논리적 오류가 없으므로 계속 진행하고, j과 x가 다르면 불가능한 경우가 되기 때문에 No를 출력하게 됩니다.

궁금한 점은 지금부터입니다.

처음에 b 배열의 길이를 100002로 했습니다.

그 상태로 제출하니 시간 초과가 떴습니다.

그런데, b 배열의 길이를 200002로 하고 제출하니까 맞았다고 하네요.

배열 길이가 잘못된 상태였으면 +, -를 충분히 저장하지 못하므로 틀렸습니다 내지는 런타임 에러가 떠야 하지 않나요?

시간 초과의 의미를 어떻게 받아들여야 할지 모르겠습니다..

djm03178   1년 전

배열의 범위를 초과하는 건 undefined behavior입니다. 말 그대로, 무슨 일이 일어날지 모르는 게 맞습니다.

보통 변수들은 연속된 공간에 할당이 되기 때문에 배열의 범위를 초과하면 주변에 있던 다른 변수의 값을 건드릴 가능성이 높습니다. 이렇게 되면 런타임 에러는 안 나는데 원했던 것과 전혀 다른 결과를 얻을 수도 있습니다. 예를 들어 배열의 원소를 0으로 바꾸는 연산을 하는데 하필 그 값이 for문을 돌리던 i였다면, for문이 다시 처음부터 돌게 되겠죠.

ehdghks709   1년 전

@seaoffizier 말씀의 뜻을 잘 모르겠습니다 ㅜㅜ

@djm03178 그렇게 생각하니 이해가 가네요.. 어떤 값을 잘못 건드려서 무한 루프가 되지 않았나 싶네요. 감사합니다.

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