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


목록
번호 제목 이름 날짜 조회 추천
공지 질문 게시판 이용 규정 11 토비 15/06/19 22548 4
15728 기타치아를 물티슈로 닦아도 괜찮나요? 5 + Hard Rock Cafe, 24/03/29 274 0
15727 기타만화를 찾습니다. 7 whenyouinRome... 24/03/28 311 0
15726 IT/컴퓨터클리앙 난민들은 보시오 27 + 헬리제의우울 24/03/28 1336 2
15725 경제엔화 신권 1 2024 24/03/27 326 0
15724 기타강남 인근 좋은 식당 추천 부탁드립니다. 2 아이캔플라이 24/03/27 311 0
15723 의료/건강제가 잘못알고 있었나요? 약먹으면 일주일 안먹으면 7일 아니였읍니까??? 10 허윤진남편 24/03/26 765 0
15722 기타모자 보관함 질문입니다 김치찌개 24/03/26 166 0
15721 문화/예술종로3가 이북에서 8인 이하로 맥주 즐길 수 있는 곳 어딜까요? 2 化神 24/03/26 375 0
15720 IT/컴퓨터카카오톡에서 엑셀 붙여넣을때? 13 매뉴물있뉴 24/03/25 614 0
15719 경제코인과 주식 차트 지표 추천 받습니다 6 마우스노동러 24/03/25 472 0
15717 가정/육아제가 지금 좀 위태로운 상태인 것 같습니다. 11 [익명] 24/03/24 1358 0
15715 문화/예술수호지나 초한지 드라마 추천 받습니다. 1 mathematicgirl 24/03/23 173 0
15714 기타성시경 막걸리(경탁주) 드셔보신분 계시읍니까? 5 Groot 24/03/22 459 0
15713 연애사내 연애 빌드업 질문입니다. 7 [익명] 24/03/22 820 0
15712 의료/건강개한테 물렸습니다. 9 얌전한 고양이 24/03/21 640 0
15711 IT/컴퓨터에어팟 선물 2 카라멜마끼아또 24/03/21 321 0
15710 경제국제경제를 슬슬 볼 만한 유튜브 등이 있을까요? 4 골든햄스 24/03/20 625 0
15709 체육/스포츠주 5일 3KM 달려도 될까요? 10 활활태워라 24/03/20 631 0
15707 진로공무원 이직 관련 문의드립니다. 6 [익명] 24/03/20 741 0
15706 IT/컴퓨터사설에서 아이폰 배터리 교체시에 암호를… 3 마우스노동러 24/03/19 367 0
15705 법률부모님이 이혼하셨는데 재산분할 관련 질문입니다. 2 [익명] 24/03/19 657 0
15704 과학차 블박 usb 연결부위가 너무 민감해서 자꾸 후방카메라 연결이 끊깁니다 1 2024 24/03/19 234 0
15703 의료/건강수면다원검사를 받아보려고 합니다. 6 자몽에이슬 24/03/19 275 0
15702 경제m포인트 질문임당… 12 Echo-Friendly 24/03/19 377 0
목록

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

댓글