- 질문 게시판입니다.
Date | 19/10/03 22:00:24 |
Name | kaestro |
Subject | c++ 에서 unordered map을 pair를 key로 사용할 때 순회 |
문제가 지도상에 상하좌우로 증식하는 세포가 주어질 때[맵의 크기 제한 없이] 일정 시간이 지난 후 살아있는 세포의 수를 세는 문제를 풀고 있는데, 솔루션에서는 문제 상에서 숫자 제약조건 때문에 나올 수 있는 최대보다 큰 배열을 이용해서 문제를 해결했는데, 저는 실제로 map 자료구조를 이용해서 문제를 풀어보고 싶어 그렇게 문제를 풀었습니다. c++ map을 써서 돌아가는 코드는 만들었는데, 크기가 커지면 시간 제약 조건을 통과하지 못해서, 그럼 unordered map을 쓰면 되지 않을까? 하는 생각에 unordered_map으로 자료구조를 바꿨는데 지금 insert를 하고 나서 순회를 하면 문제가 생기더라구요. 아래 코드에서 simulation에서 iterator가 breeding을 하고 나면, 저장되어있는 simulation의 구조가 변형이 되면서 아직 순회해야하는 세포는 건너뛰거나, 아까전에 순회했던 세포를 재차 순회하는 문제가 발생하고 있습니다. 이 문제를 해결하려고 map을 따로 copy 뜨는 식으로 문제도 풀어봤는데, 이건 map을 copy하는게 오래 걸려서 그런지 기존의 map을 이용한 풀이보다 속도가 떨어지더라구요. 이런 경우에 unordered_map에 새로운 노드를 추가하면서, 아직 순회하지 않은 노드를 순회하고, 기존의 unordered_map을 카피하지 않는 방법이 있을까요? 감사합니다. void simulate() { for (int i = 0; i < timeLimit; ++i) { for (myMap::iterator it = simulation.begin(); it != simulation.end();++it) { if (it->second.active == DEAD || it->second.lifetime == -1) continue; if (it->second.active == ACTIVE) { const ii& pos = it->first; const StemCell& sc = it->second; breed(pos, sc); it = simulation.find(pos); } } for (myMap::iterator it = simulation.begin(); it != simulation.end(); ++it) { it->second.increment(); } } } void breed(const ii& pos, const StemCell& st) { for (int d = 0; d < direction.size(); ++d) { ii nextPos = { pos.first + direction[d].first, pos.second + direction[d].second }; myMap::iterator it = simulation.find(nextPos); if (it == simulation.end()) { simulation[nextPos] = StemCell(-1, st.healthPoint); } else if (it->second.lifetime == -1){ if (it->second.healthPoint < st.healthPoint) { it->second.healthPoint = st.healthPoint; } } } } ps. 전에 이런 질문 올렸을 때 코드 전문을 올려달라 하신 분이 계셨어서, 링크를 달아 둡니다. (stl map 사용) https://github.com/kaestro/algorithms/blob/master/swexpert%20academy/5653.cpp (stl unorderd_map 사용) https://github.com/kaestro/algorithms/blob/master/swexpert%20academy/5653_unordered.cpp 0
이 게시판에 등록된 kaestro님의 최근 게시물 |