PS(알고리즘) 문제풀이/해시,집합(Map,Set)7 [백준] 1764 : 듣보잡 (C++) 문제 문제 분석 - 중복과 관련된 것은 set/map 해시 알고리즘을 사용하면 유용하다. - 듣도이면서 보도인 사람인 듣보잡의 수를 구해야 하므로 듣도에서 set에 insert을 하고, 보도에서 set에 들어있는지 (듣도인 사람인지) 체크해서 주어진대로 출력하면 풀 수 있는 문제이다. - 듣보잡인 사람의 이름을 사전순으로 나열해야 하므로 vector(가변 배열)을 하나 더 만들어 듣보잡인 사람을 담고, 정렬을 하면 된다. 정답 코드 - 특히 set/map 자료구조에서 해당 key 값이 있는지 판단을 하기 위해서는 s.find()가 s.end()와 같은지 판단하면 된다. s.end()까지 갔다는 것은 해당 key 값이 없다는 것이기 때문에 s.end()이 되는 것이다. // 풀이 시간 : 11분 52초 /.. 2024. 2. 13. [백준] 13414 수강신청 (C++) 문제 문제 분석 - 수강신청 정보를 담기 위해 map 자료구조를 사용한다. - 이때, key의 순서대로 정렬할 필요가 없으므로 unordered_map을 사용한다. - 이미 수강신청을 한 번 누른 적이 있는 경우 나중에 눌렀던 순서로 체크를 해야 한다. - 처음 수강신청 버튼을 누른 경우 unordered_map에 값을 추가한다. - 수강신청 순서대로(코드에서 pair의 second 값) 정렬하고, 정렬된 수강신청 순서에서 상위 K개의 학번만 수강신청한다. - 위 조건을 구현 시 담는 것은 map으로 담아 중복을 제거하여 담고, 정렬할 때는 vector로 옮겨서 정렬해야 한다. [주의사항] 제출 결과 출력 초과가 나오는 경우, 다음과 같은 예외처리를 빼먹은 것이다. "한 사람이 여러 번 수강신청했다가 취.. 2024. 2. 8. [백준 19583번] 싸이버개강총회 (C++) 문제 문제 분석 - 라이브 스트리밍이 열리고부터 개강총회 시작 전까지 채팅을 친 사람을 1) 이라고 하고, 개강총회가 끝나고부터 라이브 스트리밍이 끝날 때까지 채팅을 친 사람을 2) 이라고 하면, 1)과 2)를 모두 만족하는 사람의 수를 출력하는 문제이다. - 문자열 끼리는 대소비교가 가능하다. 예를 들어 00:30은 01:25 보다 작다. 이를 이용하면 이 문제를 해결할 수 있다. - 1) 에서는 채팅을 친 시간 = E 이면서 동시에 채팅을 친 시간 > S >> E >> Q; while (1) { string input_time, name; cin >> input_time >> name; if (cin.eof() == true) break; // 입력을 받을 때까지 입력받기 // 입장 로직 if (in.. 2024. 2. 7. [백준] 16165번 걸그룹 마스터 준석이 <C++> 문제 문제 분석 unordered_map(해시)을 통해 key와 value 값을 양방향으로 검사하는 테크닉을 익히는 문제이다. key 값을 통해 value 값을 찾는 것은 find 함수로 쉽다. value 값을 통해 key 값을 찾으려면 iterator을 순회하면서 찾아야 한다. 대신 시간 제한이 빡빡한 경우 배열에 key 값을 저장해두고 배열의 인덱스로 접근하는 방법도 있지만 이 문제의 경우 N과 M의 범위가 100으로 작고 시간 제한도 2초이므로 iterator로 순회해도 된다. 정답 코드 문제 요구사항을 그대로 구현하면 된다. #include #include #include #include using namespace std; unordered_map um; // (멤버 이름, 팀 이름) int m.. 2024. 2. 3. 이전 1 2 다음
