0xdeadbeef   3년 전

먼저 djm님이 올리신 AC FAQ 필독부터 읽어보았습니다. 

  1. R 명령이 들어온다고 진짜로 배열의 모든 원소를 뒤집으면 절대로 안 됩니다. N개의 원소의 순서를 정말로 바꾸면 당연히 그 원소 수만큼 시간이 걸리고, 그걸 최대 10만 번 수행해야 하니 테스트 케이스 1개만으로도 100억번의 연산이 수행됩니다. R 명령의 핵심은 실제로 원소를 뒤집지 않고도 뒤집힌 것과 같은 효과를 내도록 구현하는 것입니다. C++의 std::reverse(), Python의 a[::-1] 역시 사용해서는 안 됩니다.
    -> reverse나 [::-1]은 마지막에 딱 한번만 사용했습니다.

  2. D 명령에 대해서 보통 배열의 맨 앞 원소를 무작정 지워서는 안 됩니다. C++의 vector::erase(), Java의 ArrayList.remove(), Python의 list.pop() 등으로 배열의 첫 번째 원소를 지울 시, 그 뒤에 있는 모든 원소들을 전부 한 칸씩 앞으로 당겨오게 되므로, 그 시간 역시 원소의 수에 비례하여 소요됩니다. 라이브러리 함수는 호출만 하면 N개의 원소를 기적같이 O(1)에 처리해주는 마법사가 아닙니다. 저렇게 원소를 당겨오는 작업 없이도 D의 기능을 구현할 수 있어야 합니다.
    -> deque로 처리하였습니다.
  3. 빈 배열은 []로 출력해야 합니다. 아무것도 출력하지 않거나, error를 출력하거나, 무조건 원소를 하나 출력하고 시작하려고 하면 안 됩니다.
    -> R [] 이나 D [1] 같은 애들로 테스트 해보았을때 둘다 []를 잘 출력했습니다. 이 부분에서도 딱히 문제를 못 찾겠습니다.
  4. 배열이 비어있는데 R을 하는 건 에러가 아닙니다. D만 에러입니다.
    -> 처리하였습니다.
  5. 테스트 케이스마다 초기화가 잘 됐는지 확인하세요. 그리고 매 케이스마다 개행 문자를 항상 출력하는지 확인하세요.
    -> 매 테스트 케이스마다 P와 X는 새로 읽어들여 초기화 하도록 했고, 현재 뒤집힌 상태인지 아닌지 확인하는 변수도 매 테스트 케이스마다 False로 초기화가 됩니다.
    기본적으로 Python print는 마지막에 개행문자를 넣어주므로 이것도 확인했습니다. 
  6. 처음 배열의 상태에 대한 문자열의 길이는 최대 400001자입니다. 입력 문자 배열 크기를 잘 설정하세요.
    -> 이것도 어차피 동적으로 읽어들이므로 문제 없을것이라 생각했습니다.
  7. 처음 배열의 상태로 빈 배열이 주어지는 경우를 조심하세요. 수가 무조건 하나 이상 있다고 가정하고 코드를 작성하면 이런 경우를 제대로 처리하지 못할 수 있습니다.
    -> 빈 배열에 R, D, RD, DR, DD를 넣어봤을때 각각 [], error, error, error, error, [] 가 나오는 것을 확인하였습니다.
  8. 조건문 안에 strlen(str) 를 절대로 넣지 마세요. strlen은 문자열의 처음부터 널 문자가 나올 때까지 한 글자씩 확인하므로, 반복문을 한 바퀴 돌 때마다 문자열의 길이만큼의 시간이 걸립니다.
    -> len(X)를 넣었으나 현재 TLE가 아닌 WA고 len(deque)은 O(1)이라 괜찮다 생각합니다.
  9. 단순히 R과 D의 개수만 세고 나중에 몰아서 처리하는 건 당연히 안 됩니다. R을 할 때마다 D를 했을 때 지워지는 원소가 달라지기 때문입니다.'
    -> 몰아서 처리하지 않았습니다.
  10. 배열에 들어있는 수는 최대 100입니다. 무조건 한 글자로 가정하고 구현하면 안 됩니다. 참고로, 예제에도 두자리의 수가 하나 등장하지만 어차피 지워지는 원소이기 때문에 한 글자로 가정해도 "예제는" 답이 잘 나올 수 있습니다. 예제를 믿지 마세요.
    -> 넵 알겠습니다.

이외에도 게시판을 1페이지부터 7페이지까지 돌며 올라온 반례들을 모두 시도했으나 잘못된 부분은 찾지 못했습니다.
어떤 부분이 잘못된걸까요?

---

접근법을 빼먹어 추가합니다. 처음은 뒤집히지 않은 상태입니다. 이때 D를 하면 앞에서 원소를 뺍니다.(popleft) R이 들어오면 현재 상태를 뒤집습니다. (is_reversed = not is_reversed, 실제로 큐를 뒤집진 않음) 이 상태에선 원소를 빼게되면 뒤에서 원소를 뺍니다. (pop) 만약 모든 연산이 끝났는데 현재 상태가 뒤집힌 상태라면 출력하기 전에 한번 뒤집습니다. 알고리즘에 문제가 있는건지 입력/출력 부분에서 문제가 있는지 모르겠습니다.

shg9411   3년 전

예제조차 답이 다르게 나옵니다.,

0xdeadbeef   3년 전

답이 어떻게 나오시는건가요?
저는 입력 4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]에 대해 

[2,1]
error
[1,2,3,5,8]
error
를 출력합니다.

0xdeadbeef   3년 전

앗 맙소사... 저희 둘이 서로 같은 입력에 다른 결과를 받는것에서 혹시 입력 형태에 문제가 있는건가 했습니다.

그래서 매번 line을 읽어들이는 부분을 아래와 바꿨더니 바로 통과가 되었습니다.

gen_line = (line.strip() for line in lines)

shg9411님 도움 감사드립니다.

shg9411   3년 전

입력 수정하시라고 댓글 남기려고했는데..! 다행이네요

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