qkdtmdeh   4년 전

일단 문제는 맞췄는데요. 작성한 제가 보기에도 말도안되는 짓거리들을 해서 강제로 우겨넣어서 맞춘 느낌이 강하게 들어서요. 다른 문제들을 해결할때에도 좀 써먹을 수 있게 다른 방향이 있을까요?? ㅠㅠ

코드에 주석은 최대한 달아놓았습니다.


일단 제가 한 방법은 간선 리스트를 만들면서 하나의 간선이 만들어질때마다 시작점으로 쓰인 정점의 cnt를 cnt_list를 통해 1씩 증가시켜주고,

간선을 다 만든 후에 그 cnt_list를 2번부터 끝까지 누적합시켜서

간선을 시작점 중심으로 오름차순 정렬시켰을 때,

예를 들어 qx[ed]번 정점에 연결되어있는 간선들이

cnt_list[qx[ed]-1]+1~cnt_list[qx[ed]]에 존재하도록 한 방법입니다.

N이 커서 map으로 만들수 없어서 c_map과 f_map을 만드는 대신 c_list와 f_list를 만들었고

map에서는 걍 인덱스 위치를 바꿔서 역간선에 접근했지만 list바꿔놓고 게다가 그걸 시작점 중심으로 sort까지 해버리니 찾기가 어려워서

r_list에는 각 역간선의 sorting전 index값을 집어넣어주고, k_list에는 그냥 간선순서대로 1,2,3,... 이렇게 넣어주었습니다.

그 후에 시작정점을 중심으로 sorting을 때리면

예를 들어 sorting된 후의 5번째 간선의 역간선이 sorting 되기전 75번에 있었다면 그리고 sorting된 후에는 108번에 있다면

sorting된 후에 r_list[5]=75이고..  k_list[108]=75가 들어가 있게되어 k_list를 한 번 쭉 훑으면서 탐색하여 where배열에 역간선의 위치를 새로 갱신시켜주는 방식을 사용했습니다.

제가 설명해놓고도 무슨 소린지 잘 모르겠네요. 암튼 뭔가 더 최적화된 방법이 분명히 있을거라고 생각하는데, 무언가 방법이 없을까요?/

고수님들 도와주세요.~

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