moner_ari   1년 전

먼저, 제가 작성한 코드의 구현 전략은 다음과 같습니다.

--------

1. 포켓몬 정보 받기

먼저 문제에서 N(최대 20만)종류의 포켓몬의 정보가 9개로 나뉘어서 입력되는데, 도감 번호까지 총 10개의 data를 받아줘야 합니다. 이에 대응하기 위해 구조체 Pokemon에서 해당 정보들을 받아줬습니다. num은 도감 번호, name은 이름, type1/type2는 포켓몬의 타입, hp/att/def/s_att/s_def/speed는 체력부터 스피드까지에 해당합니다.

포켓몬의 타입은 type2가 없는 경우 type2의 값을 -1로 설정했으며, 존재하는 타입에 대해서는 원본 문자열 중 가장 앞 3글자만으로 변별이 가능하다는 점을 이용해서 get_tar2() 함수를 통해 숫자로 변환해서 구조체 객체에 넣어줬습니다.

--------

2. 쿼리 처리

다음으로 최대 20만 개나 되는, Q개의 쿼리가 주어집니다. 어떤 명령어가 주어졌느냐에 따라 다음과 같이 나누어 처리했습니다.

  • sort(): 문제에서 존재할 수 있는 최대 정렬 종류가 14가지에 불과한 반면, 최악의 경우 대략 19.9만 개의 sort() 명령어가 주어질 수 있기 때문에, sort_crit[14]에 정보를 담아주는 방식으로 처리했습니다. 그리고 flush()가 주어지면 flush() 명령어 직전 정렬 상태가 가장 우선시되는 정렬 순서이기 때문에, sort() 명령어가 주어지면 가장 최근에 주어진 시점을 기록해줬습니다.
  • filter(): name이 주어진 경우에는 접두사를 수정했고, type이 주어진 경우에는 타입을 수정했습니다. 둘 다 아닌 경우에는 get_tar1() 함수를 통해 fil_range에 접근할 index 번호를 얻었습니다. 이때 fil_range[14]는 주석에 적어둔 바와 같이 {하한, 상한} 저장을 의도했습니다.
  • resize(), cursor(): 커서의 위치를 수정하거나 화면 크기를 수정하는 것으로, 일단 처리하지 않고 해당 정보를 move_cur에 넣어뒀습니다. 단, resize()의 경우 last_w, last_h에 마지막에 입력된 w, h의 값을 넣어줍니다.
  • flush(): 해당 명령어가 주어지면 일단 sort_crit에서 sc_temp로 복사해준 후 정렬해서 정렬 기준의 우선 순위를 잡아줍니다. 이후 해당 순서에 맞게 com_P라는 functor를 이용해서 포켓몬 전체 목록(list)을 정렬해 줍니다. 이후 filter 조건에 맞는 포켓몬의 번호만 따로 good에 넣어둔 후, 문제 조건에 맞게 적절하게 처리합니다.

특히 sort()와 filter()는 커서의 위치를 강제로 1로 고정하기 때문에, move_cur 안에 있는 쿼리가 더 이상 필요가 없으므로 move_cur를 비워주면 되며, last_w, last_h의 값을 w, h에 넣어줘서 갱신해 줍니다.

--------

3. 최적화에 대한 생각

위에서 설명한 것 외에도, 실행 시간 및 불필요한 코드 실행 방지를 위해 다음과 같이 추가적으로 조치해 줬습니다.

  • vector와 같은 동적 배열을 사용하는 대신 전역 범위에 정적 배열을 선언하기. 배열을 비워주는 것은 cur_cnt와 같은 값들을 0으로 설정하는 것으로 가능합니다.
  • if문 분기에 else if를 사용해서 최대한 반복문 확인 횟수를 줄이기.
  • 문자열을 직접 비교하지 않고, 1글자씩 비교하기.

그런데도 대략 80%대까지 진행되다가 '시간 초과'가 나고 있습니다. C++로 제출하신 분 중에서 꽤 빠른 실행 시간으로 문제를 풀이하신 분도 있는 만큼, 제가 작성한 코드 중 어딘가 비효율적으로 작동하는 부분이 아직 남아 있다고 생각합니다. 일단 제가 크게 의심하고 있는 부분은 아래 37~57번 줄에 있는 com_P입니다.

해당 부분 외에도 추가적으로 최적화를 적용할 수 있는 곳이 있는지, 아니면 거기에 Fast I/O를 적용해줘야 문제 풀이가 가능할지 잘 모르겠습니다. 혹시 제가 놓치고 있는 부분이 있다면 조언해 주시면 감사하겠습니다.

dsafdsaf132   1년 전

sort의 기준을 14가지가 아니라 7가지로 생각해보세요

att asc

def asc

att desc

순서대로 정렬하면

att asc 정보는 더이상 필요하지 않습니다

dsafdsaf132   1년 전

추가로 sort의 비용이 filter의 비용보다 크므로 순서를 바꿔보시는 것도 좋을 듯 합니다

moner_ari   1년 전

조언해 주셔서 감사합니다. 덕분에 문제 해결에 성공했습니다.

조언해주신 대로 sort의 기준을 14가지가 아니라 7가지로 줄일 수 있었습니다. att asc -> def asc -> att desc 순서대로 정렬해야 한다고 가정한다면, att asc에서 두 포켓몬의 값이 서로 같다고 판정된 경우 att desc에서도 두 포켓몬의 값이 서로 같기 때문에, 둘 중 더 최근에 나온 것을 기준으로 덮어씌워도 됩니다. 이러한 점을 기반으로 com_P functor를 최적화해주니, 최적화 전에는 84% 쯤에서 시간 초과가 터지던 것이, 최적화 후에는 1초 조금 안되는 실행 시간으로 "맞았습니다!!"를 받았습니다.

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