알고리즘 문제풀이 입문: 코딩테스트 대비/섹션 4. HashMap, TreeSet (해쉬, 정렬지원 Set)6 K번째 큰 수 문제 이해 카드들이 N장 나열되면, 이 중 3장을 뽑아 더한 값이 K번째로 큰 값을 출력하는 문제이다. 만약 K번째 수가 존재하지 않으면 -1을 출력하면 된다. 문제 해결 합을 큰 순서대로 나열하려면 만약 10 9 8 7 6 .. 이런 카드가 있다면 10 9 8 7 6 .. 10 9 8 7 6 .. 10 9 8 7 6 .. 10 9 8 7 6 .. 즉 일단 N장의 카드를 큰 순서대로 나열하고 3중 for문을 돌면서 합을 저장하고 원하는 k번째 set에 있는 합을 출력하는 방식대로 방법을 생각하며 시작했다. 우선 스캐너 객체를 생성하고 N, K를 입력받은 후 cards를 저장할 Integer 배열도 선언해주었다. N만큼 for문을 돌며 카드들의 값들을 입력 받아준다. Scanner in = new Scan.. 2024. 4. 5. 모든 아나그램 찾기 문제 이해 아나그램은 순서 상관없이 구성이 같으면 아나그램이라고 한다. 이 문제는 모든 아나그램을 찾는 문제로 문자열 S가 입력되고 특정 문자열 T가 입력되면, 문자열 S 안에 T와 아나그램이 되는 부분들을 찾고 그 개수를 출력하는 문제이다. 문제 해결 먼저 스캐너 객체를 생성해준 후 전체 문자열 fullStr와 아나그램인지 비교할 문자열 partStr 객체를 입력받아준다. Scanner in = new Scanner(System.in); String fullStr = in.nextLine(); String partStr = in.nextLine(); 입력받은 문자열에서 각각의 문자(알파벳)이 키가 되고, 그 키가 등장한 횟수가 값이 되어야 하므로 HashMap을 형으로 만들어준다. partStr을 문자.. 2024. 4. 5. 매출액의 종류 문제 이해 매출액이 입력되고 K가 입력되면 연속 K개의 구간을 각각 구한 후 그 안에 매출액 종류의 개수를 각각 출력하는 문제이다. 문제 해결 처음에는 K개를 포함할 수 있는 만큼 for문을 돌며 map안에 K개를 담아준 후 map의 size를 출력해주는 간단한 코드로 작성했다. 하지만 Timeout Error가 발생했다. 이는 중첩된 루프로 인해 매번 K개의 새로운 해시맵이 만들어지므로 시간 복잡도가 커지는 이유 때문이다. Timeout Error 뜬 코드 import java.util.HashMap; import java.util.Scanner; public class P03_매출액의종류 { public static void main(String[] args) { Scanner in = new Sca.. 2024. 4. 4. 아나그램(해쉬) 문제 이해 순서 상관없이 들어있는 알파벳이 같으면 YES, 다르면 NO를 출력하는 문제이다. 문제 해결 알파벳의 나열들을 스캐너 객체를 사용해 각각 str1과 str2로 받아주었다. Scanner in = new Scanner(System.in); String str1 = in.nextLine(); String str2 = in.nextLine(); 이전 문제와 마찬가지로 str1을 String 형태로 입력받았으므로 toCharArray() 과정이 필요하다. char 데이터 타입 key로 하나씩 받아 key가 존재하면 key의 값을, 없으면 0을 return 하고 그 값에서 1을 더해 map1에 넣어준다. 즉 해당 알파벳(key)이 들어올 때마다 그 개수(value)가 증가되는 코드이다 마찬가지로 str.. 2024. 4. 2. 학급 회장 (해쉬) 해쉬 개념 자체를 까먹어서 처음에는 배열을 사용해 각 후보의 표 수를 직접 계산하는 방법으로 풀었다가 유튜브와 인프런 강의로 해쉬 기본 개념에 대해 다시 공부한 후 강사님이 푼 방식과 유사하게 풀었다. 문제 이해 각 후보들의 기호가 나열되어있고, 이 중 가장 많은 투표를 받은 기호를 출력하면 되는 문제이다. 문제 해결 스캐너 객체로 학생수 N과 투표 votes를 입력받아줬다. 최종적으로 출력될 학급 회장 classPresident를 char 데이터형태로 만들어주었다. Scanner in = new Scanner(System.in); int N = in.nextInt(); in.nextLine(); String votes = in.nextLine(); char classPresident = ' '; 후보들.. 2024. 4. 2. Hash 개념 Hash 란 Key : Value 의 형태를 가진 자료구조 전화번호부와 같다고 생각하면 쉬움. 찾고자 하는 이름 = Key 전화번호 = Value Hash는 모든 데이터타입으로 접근 가능하다. HashMap map = new HashMap(); map.put('A', 3); => map의 A번째 인덱스에 3이라고 입력하는 것과 같은 동작이라고 생각하면 됨. map.get("A") => key의 value 읽어오기 (A라는 key가 존재한다는 가정하에 동작. 없으면 에러) map.getOrDefault("A",false) => A라는 Key가 있다면 A의 Value를 반환, 없다면 false를 반환 어떤 문제에서 Hash를 써야할까?? => String을 기반으로 정보를 기록하고 관리해야될 때! (단순 배.. 2024. 4. 2. 이전 1 다음 반응형
