qkfrdma91   8년 전

algospot에서 풀던 문제인데 질문드려도 될까요?

zeroone이라는 문제인데요

----------------------------------------------------------------------------------------------------------------------------------------------------------

문제

0과 1로 구성된 수열이 있다. 수열의 길이가 N이라 하고, 각각의 수열의 원소마다 순서대로 번호를 매길 경우 첫 번째 숫자는 0번이 되고 두 번째 숫자는 1번, 그리고 마지막 숫자는 N-1이 된다. 임의적으로 0이상 N-1이하의 2개의 숫자 i,j를 잡고 i번째부터 j번째 까지의 숫자 중에서의 최대값과 최소값을 찾아서 두 값이 일치하는지 알아보고자 한다.

입력

첫 번째 줄에는 최대 길이 1,000,000의 수열이 들어온다. 수열의 사이에는 빈칸이 없다. 그 다음 줄에는 질문의 개수를 뜻하는 정수 N(N<=100,000)이 입력된다. 그 다음줄부터 해당구간 i,j를 의미하는 2개의 숫자가 N개의 줄로 입력된다.

출력

각각의 질문의 순서대로 해당구간 i,j의 최대값과 최소값이 같을 경우 Yes를, 그렇지 않을 경우는 No를 출력한다.

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
이런 문제 입니다.저는 실행속도가 너무 느려서 처음 수열만 BufferedReader로 받고 나머진 Scanner로 받았는데요범위안에 숫자중에 처음 숫자와 다른 값이 있으면 No, 모두 같은 값이면 Yes로 출력하도록 코딩을 해봤습니다.그런데 오답처리가 나옵니다.여러가지 예제도 해보고 알고리즘을 찬찬히 봐도 왜 오답인지 모르겠네요ㅠ.ㅠ

joonas   8년 전

https://www.acmicpc.net/board/view/1563

혹시 답변이 된다면 좋겠습니다.

qkfrdma91   8년 전

죄송해요 글을 봐도 잘 모르겠네요ㅠㅠ

실행시간은 439m로 빠르게 나옵니다.

joonas   8년 전

각 테스트케이스마다 매번 [i, j] 구간을 매번 훑어보는게 맞나요?

그렇다면 나중에 엄청 큰 데이터에 대해서 시간초과가 나실 거 같네요.

예를 들면 1,000,000 크기의 수열에 대해서 0 100000 을 물어보는 질문이 100,000 개인거죠.

그리고 BufferedReader 랑 Scanner 랑 같이 쓸 수 있나요? 제가 자바를 잘 못해서 지금 해보는 데 런타임 에러가 뜨네요.

joonas   8년 전

와 이거 자바로 정말 힘들군요 ㅋㅋㅋ 댓글 읽어보니 자바로는 시간초과인 것 같네요. O(N) 인 소스를 제출했는데 시간초과라니요...

qkfrdma91   8년 전

네 i~j 까지 다 훑어 보는거 맞구요

이문제에 대해서 생각해본 알고리즘은 수열의 크기가 많아도 다 훑어보는 방법밖에는 생각이 안나서 그렇게 짰어요ㅜㅜ

BufferedReader와 Scanner는 같이 쓸수 있는걸로 알고 있구 제가 실행해봤을때는 잘돌아가고 예시에 대한 결과값도 잘 나옵니다.

실행시간은 algospot사이트에서는 500ms는 안넘게 계속나오구 오답이라고만 뜨네요.

qkfrdma91   8년 전

네 계속 시간초과가 나서 BufferedReader를 쓴건데 이제는 오답이 되네요ㅠㅠ

joonas   8년 전

일단 C++ 로 고쳐서 내봤는 데 시간초과 나오네요. C++ 로 고친 소스 첨부합니다.

qkfrdma91   8년 전

c++로 해도 시간초과면 알고리즘을 다시짜야될거 같네요ㅠ.ㅠ

감사합니다!!

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