섹션2. 해싱 & 시간 파싱 알고리즘 - (3)

🎈섹션2. 해싱 & 시간 파싱 알고리즘 - (3)

🟦 2-4. 음수가 있는 부분수열

최초 내 시도 | ⇒ 이중 for()문으로 답은 나왔다. | O(n2) 여서 비효율

• 나는 이중 for문 돌면서 특정 i로 찍은 현재 값에서 j로 0~i-1까지 차례로 돌며 구간합 == m 일때마다 answer++처리 했다.
• 다만, 만약 m값이 nums 값 그 자체일 경우도 고려해야 한다고 생각

package to_0426;
/* 2-4. 음수가 있는 부분수열 문제 풀이 
 * */
import java.util.*;
class Solution1 {

    //솔루션 함수 
    public int solution(int[] nums, int m){
        int answer = 0;
        int[] az = new int[nums.length];
        for(int i=0; i<nums.length; i++) {
            az[i] = nums[i];//여기서 한번만 더해주고
            if(az[i] == m) answer++;
            //특정 i찍고 그 앞을 j로 하나씩 거꾸로 가면서 특정 m되면 break
            for(int j= i-1; j>=0; j--) {
                az[i] += nums[j];
                if(az[i] == m) answer++;
            }
        }        
        return answer;
    }
    //실행 메인 
    public static void main(String[] args){
        Solution1 T = new Solution1();
        System.out.println(T.solution(new int[]{2, 2, 3, -1, -1, -1, 3, 1, 1}, 5));    
        System.out.println(T.solution(new int[]{1, 2, 3, -3, 1, 2, 2, -3}, 5));    
        System.out.println(T.solution(new int[]{1, 2, 3, -3, 1, 2}, 3));    
        System.out.println(T.solution(new int[]{-1, 0, 1}, 0));    
        System.out.println(T.solution(new int[]{-1, -1, -1, 1}, 0));    
    }
}

---

완성 코드 | Hashing 으로 풀면 O(n)으로 돌 수 있다.

• 1) 각 구간별 sum을 계속 구해나가면서
• 2) 현재의 sum종류별 빈도수를 <sum ,빈도수> 형태로 맵에 저장
• 3) 맵에 현재의 sum-m 의 키값이 존재한다면 그 빈도수를 answer++

package to_0426;
/* 2-4. 해싱으로 다시 풀어보기 
 * */
import java.util.*;
public class Solution1_Re {
    public int solution(int[] nums, int m){
        int answer = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        int sum = 0;
        map.put(0, 1);
        //하나씩 뽑아서 
        for(int x : nums) {
            //누적 합 구하되 
            sum+= x; 
            //만약 맵에 현재 sum-m의 값이 존재한다면, 그 값의 빈도수만큼 answer++
            if(map.containsKey(sum-m)) answer += map.get(sum-m);
            //현재의 sum 종류별 빈도수를 다시 맵에 누적 
            map.put(sum,  map.getOrDefault(sum, 0)+1);
        }
        return answer;
    }

    public static void main(String[] args){
        Solution1_Re T = new Solution1_Re();
        System.out.println(T.solution(new int[]{2, 2, 3, -1, -1, -1, 3, 1, 1}, 5));    
        System.out.println(T.solution(new int[]{1, 2, 3, -3, 1, 2, 2, -3}, 5));    
        System.out.println(T.solution(new int[]{1, 2, 3, -3, 1, 2}, 3));    
        System.out.println(T.solution(new int[]{-1, 0, 1}, 0));    
        System.out.println(T.solution(new int[]{-1, -1, -1, 1}, 0));    
    }
}

---

🟦 2-5. 회장 선거

최초 시도 | 맞았음

• 1) 회장선거 k번 이상 뽑힌 애들만 분별해놓음
• 2) 회장선거 나가는 애 뽑은 애 빈도수 구해놓기
• 3) 그 중 max 값 찾아서 max 값 갖는 여러 명은 구해놓음
• 4) 최종 알파벳 앞순 뽑기: ArrayList 에 담아놓고 Collections.sort()로 알파벳 순 정렬 한 뒤, 첫번째 값을 answer 에 담아서 리턴했더니 정답 나옴

package to_0426;
/* 2-5. 회장선거 문제풀이 */
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

class Solution2 {
    public String solution(String[] votes, int k){
        String answer = " ";
        String s = " ";

        HashMap<String, Integer> map = new HashMap<>();
        //1) 회장선거 나가는 애 먼저 구해놓고
        for(String x : votes) {
            String[] tmp = x.split(" ");
            map.put(tmp[1], map.getOrDefault(tmp[1], 0)+1);
        }

        for(String key : map.keySet()) {
            if(map.get(key) >= k) {
                s += key+" ";
            }
        }

        //2) 회장선거 나가는 애를 뽑은 애들 중 가장 많은 선물 받는 애 알파벳 순으로 뽑기
        HashMap<String, Integer> out = new HashMap<>();

        for(String x : votes) {
            String[] tmp = x.split(" ");
            if(s.contains(tmp[1])) {
                out.put(tmp[0], out.getOrDefault(tmp[0], 0)+1);
            }
        }
        int max = Integer.MIN_VALUE;
        for(String key : out.keySet()) {
            if(out.get(key) > max) {
                max= out.get(key);            
            }
        }
        ArrayList<String> arr = new ArrayList<>();
        //3) 많이 선물 받은애 까지는 구했는데.
        for(String key : out.keySet()) {
            if(out.get(key) == max) {
                arr.add(key);
            }
        }
        //4) 알파벳 순으로 String 정렬 후 
        Collections.sort(arr);
        //첫 번쨰 값을 answer 에 담기 
        answer = arr.get(0);

        return answer;
    }

    //실행 메인 
    public static void main(String[] args){
        Solution2 T = new Solution2();
        System.out.println(T.solution(new String[]{"john tom", "daniel luis", "john luis", "luis tom", "daniel tom", "luis john"}, 2));
        System.out.println(T.solution(new String[]{"john tom", "park luis", "john luis", "luis tom", "park tom", "luis john", "luis park", "park john", "john park", "tom john", "tom park", "tom luis"}, 2));
        System.out.println(T.solution(new String[]{"cody tom", "john tom", "cody luis", "daniel luis", "john luis", "luis tom", "daniel tom", "luis john"}, 2));
        System.out.println(T.solution(new String[]{"bob tom", "bob park", "park bob", "luis park", "daniel luis", "luis bob", "park luis", "tom bob", "tom luis", "john park", "park john"}, 3));
    }
}

완성 코드 |

• 1) 투표 정보를 <뽑은 이 : (대상들) > 형태로 담는다.
• 2) 맵1 <후보자, 빈도수>
• 3) 맵1 <투표자, 선물수> = 선발된 후보자 많이 투표한 애들 ++
• 투표정보 순회하면서 뽑는 이 a 기준으로 뽑은 대상 b를 담는다.
• 동시에 후보자 b 기준 카운팅도 한다
• 카운팅된 빈도값이 k보다 크거나 같으면 후보자이다.

package to_0427;
/*2-5. 회장선거 */
import java.util.*;
class Solution1 {

    //솔루션 함수 
    public String solution(String[] votes, int k){
        String answer = " ";
        //투표 정보 <사람 -> (뽑은 애들) > 형태
        HashMap<String, HashSet<String>> voteHash = new HashMap<>();
        //후보자, 빈도수
        HashMap<String, Integer> candidate = new HashMap<>();
        //선물받는 애 = 후보자로 선발된 애들을 가장 많이 뽑은 사람의 빈도수 
        HashMap<String, Integer> present = new HashMap<>();

        for(String x : votes) {
            String a = x.split(" ")[0]; //공백 기준 앞 문자 - 뽑은 이
             String b = x.split(" ")[1]; //공백 기준 뒷 글자 - 대상 
             //담기- 뽑은 사람 기준으로 -> 자리 생성해두고 
             voteHash.putIfAbsent(a, new HashSet<String>());
             voteHash.get(a).add(b); //a 기준으로 대상 b를 담는다
             //후보자 누적 
             candidate.put(b, candidate.getOrDefault(b, 0)+1);
        }

        int max = Integer.MIN_VALUE;
        //각각의 뽑은이 하나씩 뽑아와서 
        for(String a : voteHash.keySet()) {
            int cnt = 0;
            //뽑은이 a가 뽑은 대상 b들을 차례로 들고와서
            for(String b : voteHash.get(a)) {
                //b가 후보자인 경우,  카운팅 
                if(candidate.get(b) >= k) cnt++;
            }
            //선물받는 이 a기준에 받는 cnt담음 
            present.put(a, cnt);
            //기존 max와 cnt비교 후 더 큰값을 max로 세팅
            max = Math.max(max, cnt);
        }

        //알파벳 순 출력
        ArrayList<String> tmp = new ArrayList<>();
        for(String name : present.keySet()) {
            if(present.get(name) == max) tmp.add(name);
        }

        //사전 순으로 비교하여 sort 정렬한다. 
        tmp.sort((a,b) -> a.compareTo(b));
        answer = tmp.get(0);

        return answer;
    }
    //실행 메인 
    public static void main(String[] args){
        Solution1 T = new Solution1();
        System.out.println(T.solution(new String[]{"john tom", "daniel luis", "john luis", "luis tom", "daniel tom", "luis john"}, 2));
        System.out.println(T.solution(new String[]{"john tom", "park luis", "john luis", "luis tom", "park tom", "luis john", "luis park", "park john", "john park", "tom john", "tom park", "tom luis"}, 2));
        System.out.println(T.solution(new String[]{"cody tom", "john tom", "cody luis", "daniel luis", "john luis", "luis tom", "daniel tom", "luis john"}, 2));
        System.out.println(T.solution(new String[]{"bob tom", "bob park", "park bob", "luis park", "daniel luis", "luis bob", "park luis", "tom bob", "tom luis", "john park", "park john"}, 3));
    }
}

---