Algorithm(코딩테스트)/해시,집합(Map,Set)8 [JAVA] 🌟프로그래머스 - 달리기 경주 교훈점해시 테이블의 필요성을 알 수 있는 문제 (탐색하는데 n의 개수가 클 때) 배열로 순회하여 풀이 추월한 선수의 index 값을 알아내서 그 앞에 있는 선수와 swap 하면 간단하게 해결할 수 있다.즉, callings 배열을 순회하면서 동시에 players 배열들을 순회해야 한다.그러나, 제한 사항이 callings 배열의 길이가 최악의 경우 100만, players의 배열의 길이가 최악의 경우 5만이다.따라서 최악의 경우 500억의 연산이 일어나므로 시간 초과가 난다. -> 순회를 할 때 시간을 줄여야 한다.Hash Table 사용배열은 어떤 원소를 찾기 위해 순회할 경우 시간 복잡도가 O(n)이다.Hash Table은 어떤 원소를 찾으려면 O(1)으로 해결이 가능하다.(이름, 순위) 를 담는 .. 2025. 3. 21. [백준] 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. 이전 1 2 다음
