- 질문 게시판입니다.
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


목록
번호 제목 이름 날짜 조회 추천
7964 경제이번 WTO 공기압밸브건은 어떻게 봐야하나요? CONTAXND 19/10/01 3266 0
7965 경제개인은 디플레이션에 어떻게 대응하면 좋을까요? 5 고파파 19/10/01 3429 0
7966 문화/예술못쓰는 후라이팬을 화로 대용으로 쓰려고 합니다 잘 될까요? 3 흥차넷 19/10/01 3237 0
7967 문화/예술드립커피 도전하려고하는데 장비 이륙해도 될까요? 31 야근하는밤비 19/10/01 4252 0
7968 가정/육아제주도 해천탕/해신탕 맛집 아는 곳 있으신지요? 흥차넷 19/10/02 4369 0
7969 의료/건강알레르기 검사 및 주사면역치료가 궁금합니다. 12 TheORem 19/10/02 7249 0
7970 여행명절에 에어텔 조금이라도 싸게 사는 방법 있을까요? 2 절실한사람너였어 19/10/02 3517 0
7972 의료/건강의대 외래교수 위상이 궁금합니다. 6 [익명] 19/10/02 3180 0
7973 기타석류즙 질문입니다 2 김치찌개 19/10/02 2976 0
7974 IT/컴퓨터c++ 에서 unordered map을 pair를 key로 사용할 때 순회 7 kaestro 19/10/03 4267 0
7975 IT/컴퓨터미국 사는 사람들은 채용공고를 어디서 보나요? 8 [익명] 19/10/04 2632 0
7976 의료/건강정신과 방문 및 검색 관련 11 치유 19/10/04 2813 2
7977 IT/컴퓨터갤럭시 와이드 3 vs. V20 9 매일이수수께끼상자 19/10/04 3832 0
7978 경제우리나라가 일본 경제를 잡는게 현실적으로 가능한가요? 59 원영사랑 19/10/04 3983 0
7979 IT/컴퓨터홍차넷에 맥북 쓰시는 분 계신가요? 9 한신 19/10/04 4368 0
7980 IT/컴퓨터갤럭시 폴드 자성 질문입니다. Might 19/10/04 3305 0
7981 철학/종교잠깐 웹서핑을 그만둬야 할까요? 7 [익명] 19/10/04 2709 0
7982 IT/컴퓨터갤럭시 S9+ 액정 교환 질문입니다. 11 메존일각 19/10/04 3099 0
7983 교육문제풀이 반타작 탈출하려면.. 11 셀레네 19/10/05 4948 1
7984 기타세계적인 경제불황이 머지 않았다고 생각하시는지요...? 5 [익명] 19/10/05 3959 0
7985 문화/예술일러스트 포즈 사전 같은 게 있으려나요? 2 불타는밀밭 19/10/05 2703 0
7986 문화/예술풀정장에 어깨끈 서류가방 괜찮을까요? 5 [익명] 19/10/05 2892 0
7987 진로선사에서는 무엇을 하나요? [익명] 19/10/05 2451 0
7988 여행4년뒤 몰디브 여행을 계획중입니다. 항공권 문의드립니다. 2 Kurtz 19/10/06 3638 0
7989 의료/건강채혈침 사용 회수에 대한 질문 7 알겠슘돠 19/10/06 3231 0
목록

+ : 최근 2시간내에 달린 댓글
+ : 최근 4시간내에 달린 댓글

댓글