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


원본 문제를 보지 않고 쓰는 답변이라 영 이상한 소리가 될지도 모르겠습니다만, 일단 아는 한에서 적어보겠습니다.
----------------------------------------------------------------------------

1. 일단 iterator를 사용할때 iterator를 수정하면 의도치 않은 동작을 하기 쉽습니다.
최대한 for문 내부에서는 대상을 변경하지 않도록 합시다.
변경이 필요하면 대상 자체의 iterator 대신 다른 변수를 사용해서 for문을 구현하는것이 좋습니다.

2. ... 더 보기
원본 문제를 보지 않고 쓰는 답변이라 영 이상한 소리가 될지도 모르겠습니다만, 일단 아는 한에서 적어보겠습니다.
----------------------------------------------------------------------------

1. 일단 iterator를 사용할때 iterator를 수정하면 의도치 않은 동작을 하기 쉽습니다.
최대한 for문 내부에서는 대상을 변경하지 않도록 합시다.
변경이 필요하면 대상 자체의 iterator 대신 다른 변수를 사용해서 for문을 구현하는것이 좋습니다.

2. c++에서 unordered_map 이 생각보다 성능면에서 장점이 별로 없습니다.
단순한 키에서는 ordered_map 보다 성능이 더 안나오는 경우도 많고요.

3. 문제를 보지 못해서 단언하지는 못하겠지만,
아무래도 시간 복잡도를 계산해 보면 unordered_map이건, ordered_map이건 시간을 초과하는 상황이 아닐까 싶습니다.
그렇지 않더라도 vector나 map같은 콘테이너의 오버헤드로 인한 시간초과가 날 수도 있고요.
가능하다면 문제도 같이 링크걸어주시면 더 자세히 알려드릴 수 있을거 같습니다.
kaestro
아뇨, 몰랐던 이야기들이고 굉장히 도움이 많이 됐습니다. 감사합니다.
unordered_map이 ordered_map보다 단순한 키에서 성능이 안 나오는 경우에 성능이 안 나오는 경우가 많다면 아마 이것도 비슷한 경우일 수도 있겠네요.
질문 올리고서 답변들 받으면서 추가로 구현한 방법도 몇 가지 있었는데 이것도 시간초과가 발생하더라구요.
문제가 단순히 링크만 드리면 회원가입을 하지 않고 들어가 볼 수가 없는데, 회원가입을 하시는게 싫으실 경우 이메일을 쪽지로 보내주시면 제가 html 파일을 보내드리겠습니다.
일단 링크는 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo 입니다.
아 sw expert academy였군요...
저도 계정이 있으니 다음에 시간이 되면 풀어보고 알려드리겠습니다 ㅎㅎ
kaestro
사실 그냥 맵사이즈 크게 잡고, offset잡으면 풀리는 문제고 실제로 돌아다니는 solution 보면 다 그렇게 풀긴 하는 것 같더라구요...
제가 요즘 stl 쓰는 연습하는 중이라 혹시 이렇게 풀 방법은 없을까하고 좀 뻘짓해보는 중인 거긴 해서 ㅎㅎ...
지금까지 답변주신거로도 도움이 많이 됐습니다. 일단 이번 하반기에 시험을 보게 된다면 이렇게 풀면 안될거라는 것 정도는 확실히 알아가는 것 같네요...
감사합니다
1
Azurespace
굳이 map을 써야 할 이유를 잘 모르겠는데... 굳이 이렇게 풀고 싶으시다면, 맵에 새로 들어가게 될 cell들을 저장할 vector를 하나 마련하시고 순회가 끝난 다음에 map에 한번에 insert하세요.
1
kaestro
많은 분들이 말씀해주셔서 일단 그런식으로도 해결했는데 그것도 time limit 을 통과 못하더라구요
말씀하신대로 굳이 map을 써야하냐는 말을 다들 하셨는데, map을 안 쓰면 제한조건에 맞춰서 가능한 것보다 훨씬 큰 array 혹은 vector를 잡아서 음수로도 진행하는게 아니면 처음에 주어진 것보다 큰 영역까지 추가할 방법을 몰라서 이렇게 구성해봤습니다.
처음에 크기가 2by2로 주어진 상태에서 매 시간마다 계속해서 커질 수 있는 상태에서 map을 쓰거나, 그것보다 큰 arry를 잡은 다음 가운에서 시작하는 것 이외에 다른 방법이 있을까요?
Azurespace
이 맵 제한을 없애고 싶으시다면... 저라면 일단 시간 1마다의 변화를 모두 에뮬레이션하려고 시도하지 않을 것 같습니다. 시간 순서대로 정렬되는 우선순위 큐를 활용해서 일종의 메시지 큐를 만들겠어요.
목록
번호 제목 이름 날짜 조회 추천
694 법률회사에서 행사를 1박으로 짰을 때, 반드시 참석해야 하나요? 20 매일이수수께끼상자 16/01/06 5253 0
10939 IT/컴퓨터고사양 노트북 질문입니다. 20 토오끼코오끼리 21/02/02 5253 0
2543 기타이 치즈 어떻게 먹나요? 20 성의준 17/03/21 5254 0
14090 기타생각하는 시야를 넓히는 수단으로 독서가 적절할까요? 26 설탕 22/11/02 5254 0
5939 문화/예술내 인생을 망치러 온 나의 구원자 28 우리온 18/11/21 5255 0
6401 기타서효원 소설들 믿고 읽어도 됩니까? 10 덕후나이트 19/01/27 5255 0
10699 IT/컴퓨터네 카카오 서비스 내의 각 아이콘의 바탕색이 다 다른 것인가요? 5 알겠슘돠 20/12/24 5255 0
12438 기타전기차? 내연기관차 고민 21 로하이참치 21/10/20 5255 1
12913 IT/컴퓨터노트북 구매 문의드립니다 6 야망 22/02/01 5255 0
2555 기타결혼식 복장 어떻게 하고 가시나요? 18 그럼에도불구하고 17/03/25 5256 0
12189 기타불황일 때 돈 버는 방법은 어떤 게 좋을까요...? 13 홍당무 21/09/04 5256 0
227 홍차넷홍차넷 게시판에 사진 두 개 이상, BGM 넣는 방법 아시나요? 4 수박이두통에게보린 15/08/12 5257 0
4141 여행서울 또는 근교에서 혼자놀기 좋은곳 (차있음) 추천 바랍니다. 6 [익명] 18/02/10 5257 0
12940 가정/육아요리 초보가 할 수 있는 요리 25 면이면옥 22/02/07 5257 0
14287 기타유독 전라도에 눈이 내리는 이유? 6 모아트루 22/12/23 5257 0
4112 기타머리 큰 사람이 맞을만한 안경/선그라스 브랜드 있나요? 9 [익명] 18/02/06 5258 0
8333 의료/건강당뇨 말고 다른 이유로 혈당이 오를 수 있나요? 6 loliloli-love 19/11/24 5258 0
9393 기타천정형에어컨 청소업체 금액차이가 왜 이렇게 편차가 큰가요? 7 오리꽥 20/05/13 5258 0
10293 의료/건강온수매트 추천해주세요!!! 11 제루샤 20/10/18 5258 1
10367 기타5만원이하 와인 혹은 고량주 추천부탁드립니다! 14 시뮬라시옹 20/11/01 5258 0
3455 기타아반떼XD 차량 질문입니다 6 김치찌개 17/10/01 5259 0
3676 법률애인을 강제추행하던 치한을 폭행했을 시 각각의 양형이 궁금합니다. 9 tannenbaum 17/11/13 5259 0
7918 기타한 사람에게 매년 선물할 경우 선물 리스트 어케하시나요 17 알료사 19/09/24 5259 1
10505 진로Data 분야로 취업시 석박사 필수이죠? 17 NIKES 20/11/26 5259 0
12091 의료/건강라섹 10년차 시력이 많이 떨어졌습니다. 재수술 하신분? 4 Picard 21/08/20 5259 0
목록

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

댓글