- 질문 게시판입니다.
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 23597 4
16312 기타차량 선택장애가 왔습니다 (카니발 vs 펠리세이드) 4 + 쉬군 24/11/23 121 0
16311 문화/예술안 읽히지만 좋은 책 추천 받읍니다 33 + 빈둥 24/11/22 531 2
16310 가정/육아대학원 동기 출산 선물 12 카르스 24/11/21 388 0
16308 경제부동산 투자 어떻게 공부하면 좋을까요 4 열한시육분 24/11/21 323 0
16307 법률소액사기 신고를 하고 싶습니다. 6 whenyouinRome... 24/11/21 403 0
16306 교육통계/데이터과학 공부하는 방법 6 [익명] 24/11/21 329 0
16305 기타차량에 사제 어라운드뷰 설치해보신 분 계실까요? 7 쉬군 24/11/20 367 0
16304 여행이번주 토요일 오후 단풍, 은행 명소는 어디일까요? 3 化神 24/11/20 244 0
16303 문화/예술근본 있는(?) 추리소설을 추천해 주세요 20 호미밭의파스꾼 24/11/20 446 0
16302 IT/컴퓨터영상 코덱 관련 질문 드립니다..! 4 햄볶는돼지 24/11/19 156 0
16301 IT/컴퓨터빽빽히 내용이 채워진 엑셀파일 출력본을 OCR로 인식하고 싶습니다. 2 FTHR컨설팅 24/11/19 316 0
16300 진로스스로 하고싶지만서도 타인한테 기대고 싶기도 합니다. 9 활활태워라 24/11/19 489 0
16299 경제행복주택에 살고 있는 중인데 영구임대주택에 당첨되었습니다. 17 [익명] 24/11/18 914 0
16298 의료/건강손이 저립니다 11 린디합도그 24/11/18 428 0
16297 기타밀도 있게 일하는 법은 무엇일까요? 3 데굴데굴 24/11/18 452 1
16296 기타디지털 피아노 혹시 아시는 분 있을까요? 18 TEMPLATE 24/11/18 402 0
16295 IT/컴퓨터조금 시끄러운 환경에서 쓸 수 있는 화상회의용 이어폰을 찾고 있습니다. 2 이러사우호 24/11/18 263 0
16294 기타자동차 보험은 한 회사로 쭉 가는게 나은 건가요? 13 퍼그 24/11/18 435 0
16293 IT/컴퓨터400 Bad Request No required SSL certificate was sent 해결방법 있을까요? 4 활활태워라 24/11/18 293 0
16292 체육/스포츠트레드밀에서 쓸 러닝화 뭐가 좋을까요? 6 blu 24/11/17 325 0
16291 IT/컴퓨터개인용 오피스365+원드라이브 유지 어떤 방법이 경제적인가요? 5 열한시육분 24/11/17 399 0
16290 교육토플 vs. 아이엘츠 9 말하는감자 24/11/16 462 0
16289 의료/건강아이에게 녹용 복용을 고려중입니다 15 T.Robin 24/11/15 688 0
16288 IT/컴퓨터테블릿 좀 추천 부탁드리읍니다. 19 24/11/15 461 0
목록

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

댓글