songmoro   1년 전

본문 예제랑 질문글의 반례들 한 번씩 돌려봤을 때는 올바르게 나오는데 제출하면 출력 초과가 발생해서 어떤 반례에서 출력 초과가 생기는 건지 궁금합니다.

adfsfsf   1년 전

아래와 같은 반례가 있습니다.

출력 부분은 다음과 같습니다.

스택 상태 -> 출력, i의 값

실제 답과는 다르게 출력됩니다.

여기에서 시작의 10과 끝의 9 사이에, 9 미만의 수들을 추가할수록 오류의 크기는 더욱 커집니다.

이 크기가 2자리 이상만 되어도 출력이 초과됩니다.

물론 출력 초과가 문제가 아니라, 답 자체가 잘못 나오고 있죠.

이 문제를 해결하기 위해서는 스택에 값만 넣는 것이 아니라 인덱스를 함께 넣어줘야 합니다.

즉, 스택 s를 한 항에 2개의 값을 갖도록 작성해야 합니다.

adfsfsf   1년 전

아, 설명을 잘못 적었네요. 정확히는 아래와 같은 형태로 된 입력이 들어오면 문제가 됩니다.

1. 적당히 큰 수 A가 있다고 하겠습니다.

2. A와 마지막 수보다 작지만, 나머지 수들보다는 작은 값 B를 두겠습니다.

3. B의 위치가 충분히 멀고, B 바로 다음이 마지막 수라고 하겠습니다.

4. 그러면 최종 위치에 대한 출력은 1이 되어야 하지만 (B의 위치) - 1이 됩니다.

예시를 같이 적습니다.

adfsfsf   1년 전

스택에 남은 원소의 개수는 현재 입력 이전에 입력된 수들의 개수를 반영하지 못합니다. 따라서 이 개수를 별도로 줘야 한다는 점을 이해하시면 된다고 봅니다. 한 번에 못 적고 여러 번 나눠서 적어서 죄송합니다.

songmoro   1년 전

조언 해주셔서 감사합니다. 스택을 페어 쌍을 사용해서 해결했습니다.

별개로 본문에서 "실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다." 라고 했으니 값이 같은 입력에 대해선 고려 안해도 됐었겠죠?? 다른 분들 질문에 반례로 중복되는 값이 들어가는 경우가 있어서 헷갈리네요

adfsfsf   1년 전

높이가 같은 탑이면 당연히 수신이 가능하지 않을까요? 하지만 어차피 작성하셨던 코드는 같은 경우에도 수신받도록 되어 있으니 상관 없었을 거에요.

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