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을 사용하는 방식이 더 나을 수 있습니다.
최종적으로는 시간 복잡도, 공간 복잡도, 코드 가독성 등을 종합적으로 비교해보시고 선택하세요. 프로그래밍은 특정한 정답이 있는 것이 아니라 문제를 해결하기 위해 가장 적합한 도구와 방법을 선택하는 과정입니다.
코딩살구클럽 입장이 안됩니다
0
33
2
4-F 경우의 수 질문입니다.
0
27
2
코딩살구클럽 가입이 안됩니다.
0
56
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
45
1
교안 158페이지 문의드립니다
0
38
2
코딩살구클럽 관련 건의사항
0
102
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
40
1
진행 방법 질문드립니다!
0
74
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
61
2
2주차 개념#12 트리 순회
0
32
2
백준사이트가 종료된다고 합니다.
0
307
2
백준 서비스 종료
9
925
1
sk 하이닉스 코테 대비
0
380
2
3-G 최댓값 질문
0
52
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
84
2
3-I 코드 질문드립니다.
0
63
2
3-N 질문 있습니다.
0
68
2
학습방법
0
104
2
4-H 질문 있습니다 (코드 리뷰)
0
67
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
178
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
70
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
65
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
52
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
70
2