PS(알고리즘) 문제풀이/해시,집합(Map,Set)7 [백준 11652번 C++] 카드 (Map 활용) 문제 문제 분석 이 문제를 해결하기 위해 가장 먼저 배열로 담아서 인덱스로 접근하는 방법을 생각할 수 있다. 하지만 이 문제에서 배열로 담아서 인덱스로 접근하는 방법을 구현할 경우 -2^62~2^62의 값을 담을 수 있는 공간을 미리(선언부터) 할당해야 한다. 누가봐도 메모리 초과가 나올게 뻔하다. map과 set은 insert 연산을 통해서 데이터를 삽입할 때 공간을 할당하므로 N이 최악의 경우 100000 이어도 메모리 초과가 나지 않는다. 정답 코드 - map의 value 값을 정렬하기 위해서 map의 값을 vector로 옮겨 정렬하였다. // 1안 )배열 인덱스를 활용 -> 배열은 먼저 메모리에 할당을 해놔야 하기 때문에 수의 범위가 -2^62~2^62인 숫자들을 담을 공간을 마련하려면 메모리 초.. 2024. 1. 31. [백준 9375번 C++] 패션왕 신해빈 (해시, Map/Set) 문제 문제 분석 문제를 잘 읽는 것이 중요하다. 먼저 의상마다 한 가지의 종류씩을 골라서 입을 수 있다. 문제에서 나온 예제 입력을 바탕으로 설명하자면, headgear는 {hat, turban}을 고를 수 있고 아무것도 선택하지 않을 수 있다. 총 경우의 수는 3가지이다. eyewear은 {sunglasses}을 고를 수 있고 아무것도 선택하지 않을 수 있다. 총 경우의 수는 2가지이다. 즉, 해빈이가 입을 수 있는 모든 의상의 경우의 수는 3*2인 6가지이다. 하지만 문제 조건에서 아무 것도 입지 않는 경우는 제외하기로 했다. headgear와 eyewear 에서 아무것도 선택하지 않는 경우 1가지를 뺀 총 5가지가 정답이다. 이러한 아이디어를 바탕으로 구현하면 된다. 정답 코드 - unordered.. 2024. 1. 31. [백준 17219번 C++] 비밀번호 찾기 (Map/해시) 문제 문제 분석 사이트와 비밀번호를 입력받고 저장해 두었다가 사이트가 주어졌을 때 그 비밀번호를 출력하는 문제이다. - map/unordered_map 에 대한 개념을 알고 있는지를 물어보는 문제이다. - map을 활용하여 비밀번호를 찾는 방법은 여러 가지가 있지만 특히 iterator을 순회하면서 찾고자 하는 값이 map의 second와 일치하는지 일일이 찾아보는 방법과 map의 find 함수를 이용하는 방법이 있는데, map의 find 함수를 이용하여 찾는 것이 빠르다. 정답 코드 이러한 방법대로 구현한 코드이다. - 이때 map의 find 함수는 iterator 형태로 반환한다는 점을 기억해야 한다. - key에 따라 정렬을 해야 하는 것이 중요한 것은 아니므로 unordered_map을 사용한다... 2024. 1. 30. 이전 1 2 다음
