map을 2개 사용하는 방식이 좋은지 이 방식이 좋은지 궁금하여 질문드립니다!
소스 코드
http://boj.kr/d754f100ea9f49e6b9f3bd0c8f1ec98a저는 map을 <int, pair<int, int>>의 형식으로 사용했는데요, first에는 key, second.first에는 빈도수, second.second에는 입력 순서가 저장됩니다. 강의를 보기 전 문제를 풀어 보았는데 이러한 방식으로 구현하는 것이 map을 2개 사용하는 것보다 효율적일까요?
답변 2
0
안녕하세요 민규님 ㅎㅎ
음.. 비슷하다고 볼 수 있습니다.
보이시는 것처럼 메모리 차이도 그렇게 많이 나지 않습니다.
그래도 민규님이 짜신게 조금은 더 좋다고 볼 수 있습니다.ㅎㅎ
잘 짜셨습니다. ㅎㅎ
다만, unordered_map을 사용할 때는 최악의 경우 O(N)이 걸린다는 점만 주의해서 해주세요. ㅎㅎ
unordered_map
앞서 설명한 map은 정렬이 되는 반면 unordered_map은 정렬이 되지 않은 map이며 메서드는 map과 동일합니다.
map과 unordered_map을 비교하면 다음과 같습니다.
map : 정렬이 됨 / 레드블랙트리기반 / 탐색, 삽입, 삭제에 O(logN)이 걸림
unordered_map : 정렬이 안됨 / 해시테이블 기반 / 탐색, 삽입, 삭제에 평균적으로 O(1), 가장 최악의 경우 O(N)
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다.
송민규님, map을 사용하는 다양한 방식에 대한 질문 감사합니다.
map을
반면에 map을 2개 사용하여 각각 빈도수와 입력 순서를 관리하게 되면, 복잡도가 증가하고 코드가 길어질 수 있으나, 각각의 값에 대해 특화된 연산을 수행할 때는 이 방식이 더 유리할 수 있습니다.
따라서 어느 방식이 효율적인지는 문제의 종류, 처리해야 할 데이터의 양, 알고리즘의 복잡도 등 다양한 요소에 따라 달라지며, 무엇보다도 해당 문제 상황에 적합한지를 고려하여 결정하는 것이 좋습니다.
데이터의 양이 크지 않고, 맵 내의 논리적인 연관성을 중요시하는 상황이라면 하나의 map을 사용하는 것이 바람직할 수 있지만, 각 데이터에 대한 처리 속도가 매우 중요한 경우나, 빈도수와 입력 순서를 별도로 빈번하게 업데이트하거나 접근해야 하는 경우에는 2개의 map을 사용하는 방식이 더 나을 수 있습니다.
최종적으로는 시간 복잡도, 공간 복잡도, 코드 가독성 등을 종합적으로 비교해보시고 선택하세요. 프로그래밍은 특정한 정답이 있는 것이 아니라 문제를 해결하기 위해 가장 적합한 도구와 방법을 선택하는 과정입니다.
코살구 1주차 1940번 문제 조건과 프라이빗 테스트 불일치 문의
0
15
2
문제를 고민하는 시간 관련
0
24
2
코딩살구클럽
0
33
2
코딩살구클럽 문의
0
32
2
코딩살구클럽 승인
0
34
2
DP 경우의 수 설명이 이해가 되지 않습니다.
0
33
2
3-F 채점 관련 질문
0
30
1
BFS, DFS 활용이 되는 상황에서의 방향성
0
33
2
코딩살구클럽 승인
0
44
2
코딩살구클럽승인
0
39
3
코딩살구클럽 승인
0
51
2
3-D 관련 질문
0
35
2
코살구 회원가입 문의
0
45
2
코살구 로그인 문제
0
65
2
3-A 문제 풀이 관련 질문
0
56
3
2-O 질문 있습니다
0
38
2
2-T 문제에 관한 질문
0
40
2
코딩 살구 클럽 접속 및 사용방법 문의
0
63
2
안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~
0
67
2
코딩살구클럽 로그인문제
0
85
3
코딩 살구 클럽 로그인 문제
0
85
2
2-J 채점관련 질문
0
67
3
코딩 살구 클럽 Python 지원 가능 여부
0
77
1
살구클럽 아이디 없음 문제
0
76
1