알고리즘 문제풀이 For Java - 2회차

2021-06-27T00:47:04.059Z

SodiumSulfate

스터디일지 : 2021-06-25 금요일

이번주 주제 : 해시
참석인원 : 동, 연, 새리, 시온, 산희 ,케이(사전 순 6명)
- 알고리즘 마스터 && 교수님 케이께서 누추한 스터디 캐리해주심 ㄷ ㄷ;;
진행시간 : 19시~22시(3시간)
프로그래머스 고득점 키트
- https://programmers.co.kr/learn/challenges?selected_part_id=12081
다른 언어 사용가능한 분들(Cpp, python) 은 다른언어로도 한번씩 더 풀어봄

문제

프로그래머스 플랫폼에서 4문제
해시 관련 문제 풀이함

해시

번호	링크	동	연	새리	시온	산희	케이
1	완주하지 못한 선수	O	O	O	O	O	O
2	전화번호 목록	O	O	O	O	O	O
3	위장	O	O	O	O	X	O
4	베스트앨범	X	O	O	X	O	O

오늘의 알고리즘문제풀이 담당코드 && 발표내용

HASH - 완주하지 못한 선수 by 동

문제

문제 : https://programmers.co.kr/learn/courses/30/lessons/42576
문제 설명
- 문자열 배열이 2개 주어짐
  1. 하나는 참가한 모든 선수의 이름이 (participant)
  2. 다른건 완주한 모든 선수의 이름이(completion)
- 위 두 배열을 비교해 완주하지 못한 선수의 이름을 구하는 문제입니다.
제한
- N제한 : 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- 답은 1개 : completion의 길이는 participant의 길이보다 1 작습니다.
- 중복가능성 : 참가자 중에는 동명이인이 있을 수 있습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

풀이

두가지 풀이법을 생각해볼수 있는데
1. Hash 자료구조의 특성을 이용해서 participant에서 completion 을 하나하나 삭제하기
2. participant , completion 둘다 정렬(사전순) 해서 양측에 존재하면 Pass, 한쪽에만 존재하는 문자열이 정답임
이 문제는 효율성도 점검하는데, 위 두가지 풀이중
- 1번 Hash 자료구조의 특성을 이용하면 전체 연산량은 N번이고,
- 2번 정렬2번+순차탐색 방식으로 풀면 전체 연산량은 N+LogN*2 정도 된다.

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    sort(participant.begin(),participant.end());
    sort(completion.begin(),completion.end());
    int len = participant.size();
    
    
    for(int i=0 ; i<len ; i++) {
        if(participant[i] !=completion[i]) {
            answer = participant[i];
            break;
        }
    }
    
    
    return answer;
}

Python3 코드

#test.py
from operator import *

def solution(participant, completion):
    
    answer = ''
    participant.sort()
    completion.sort()

    
       
    for i in range(len(completion)) :
        if participant[i] != completion[i]:
            answer = participant[i]
            break
    

    if answer == '' :
        answer = participant[-1]
    
    return answer

Java 코드

import java.util.*;

public class first{
	public static void main(String[] args) 
	{
		Solution mysol = new Solution();
		String p1[] = {"leo", "kiki", "eden"};
		String c1[] = {"eden", "kiki"};
		String ret = mysol.solution(p1,c1);
		System.out.println(ret);

	}
}


class Solution {
    public String solution(String[] participant, String[] completion) {
        
    	String answer = "";
    	
    	
    	Arrays.sort(participant);
    	Arrays.sort(completion);
    	
    	for(int i=0 ; i<completion.length ; i++) { 
    		if(!participant[i].equals(completion[i])){
    			return participant[i];
    		}
    	}
    	
    	
        return participant[completion.length];
    }
}

HASH 전화번호 목록 문제 By 연

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42577
어떤 번호가 ,다른번호의 접두어가 되는지( 77 → 7767)
접두어가 존재하면 True, 아니면 False

제한

phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다

풀이

완전탐색 : 유일한 입력인 phone_book의 제한이 백만이므로, 2중포문 n^2로 코딩하면 시간제한에 걸릴수도 있음 → 길이순 정렬이 필요 , 왜냐하면 접두어가 되기 위해서는 항상 짧아야하니까
- phone_book 을 문자열의 길이순으로 정렬하고,
- 짧은거부터 검색을 시작
- 모든 문자열의 앞부분에 검색문자열이 존재하는지를 일일이 검사
- 존재한다면 그대로 리턴하고 끝
- 근데 생각해보니 완탐으로 풀면 N*N/2 인데 그냥 풀렸다.

코드

package progrs;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class Solution42577 {
    public boolean solution(String[] phone_book) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < phone_book.length; i++) {
            map.put(phone_book[i], i);
        }

        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 0; j < phone_book.length; j++) {
                if (map.containsKey(phone_book[i].substring(0, j))) {
                    return false;
                }
            }
        }

        return true;

    }

    public static void main(String[] args) {
        Solution42577 sol = new Solution42577();
        sol.solution(new String[]{"12", "123", "1235", "567", "88", "111111", "0", "000000000000"});
    }
}

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

const int DEBUG = 0;

bool lcomp(string a, string b) {
    int la = a.length();
    int lb = b.length();
    if (la < lb) {
        return true;
    }
    else if (la > lb) {
        return false;
    }
    else if (la == lb) {
        return (a < b);
    }
    else {
        //이런경우는 없다
        return (a < b);
    }
    
}

bool solution(vector<string> phone_book) {
    bool answer = true;

    sort(phone_book.begin(), phone_book.end(), lcomp);
    int n = phone_book.size();
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            int ret = phone_book[j].find(phone_book[i]);
            //if (0<= ret && ret<=n) {
            if (0== ret) {
                return false;
            }
        }
    }

    return answer;
}

해설

단순 구현문제이므로, 위에서 문제분석을 읽고 그대로 코드를 옮기면 된다.
따라서 이 문제에서는 스니핏 해설이 존재하지 않는다.
로컬에서의 테스트를 위해 테스트코드가 추가된 버전을 수록함.

HASH - 위장 by 세리

문제

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42578
스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때
서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성

풀이

두가지 구현 방법
1. map 자료구조 : Key:Value 로 clothes배열에다 집어넣고 KEY별 경우의 수 -1(아무것도 안입는경우)
2. 구현 : 어쨋거나 [의상의 종류]와 [의상종류별 가짓수] 두개만 알면 경우의수 따져셔 풀수 있으니까 일일이 중복검사하고, 가짓수를 세서 해결

코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        HashMap<String, Integer> map = new HashMap<>();
        
        for (String[] cloth : clothes) {
            map.put(cloth[1], map.getOrDefault(cloth[1], 0) + 1);
        }
        
        int result = 1;
        for (String key : map.keySet()) {
            result *= map.get(key) + 1;
        }
        
        return result - 1;
    }
}

Hash 베스트엘범 By 시온

수도코드 스니핏

해설

    map<string, int> gnr_playtimes;
    map<string, map<int, int>> bestof_in_gnr

설명

 

    //장르별로 플레이횟수를 구하기
    int len = genres.size();
    for (int i = 0; i < len; i++) {
        gnr_playtimes[genres[i]] += plays[i];
        //genres[i] string값을 Key로 plays 를 하나씩 추가

        bestof_in_gnr[genres[i]][i] = plays[i];
        //##
        // 이중 map
        //1차 Key: 장르명 중에서 >>> 2차 Key : plays의 인덱스
    }

import java.util.*;

class Solution {
    
    class Song implements Comparable<Song> {
        int id, play;
        String genre;
        
        Song(int id, int play, String genre){
            this.id = id;
            this.play = play;
            this.genre = genre;
        }
        
        @Override
        public int compareTo(Song o){
            if(this.play == o.play){
                return this.id - o.id;
            } else {
                return -(this.play - o.play);
            }
        }
    }
    
    ArrayList<Integer> bestAlbum;
    ArrayList<Song> songList;
    HashMap<String, Integer> genreMap;
    HashMap<String, Integer> albumMap;
    
    public int[] solution(String[] genres, int[] plays) {
        bestAlbum = new ArrayList<>();
        songList = new ArrayList<>();
        genreMap = new HashMap<>();
        albumMap = new HashMap<>();
        
        for(int i = 0 ; i < genres.length ; ++i){
            int id = i;
            int play = plays[i];
            String genre = genres[i];
            
            songList.add(new Song(id, play, genre));
            
            if(genreMap.containsKey(genre)){
                genreMap.put(genre, genreMap.get(genre) + play);
            } else {
                genreMap.put(genre, play);
            }
        }
        
        Collections.sort(songList, new Comparator<Song>(){
           @Override
            public int compare(Song s1, Song s2){
                if(s1.genre.equals(s2.genre)){
                    return s1.compareTo(s2);
                } else {
                    return -(genreMap.get(s1.genre) - genreMap.get(s2.genre));
                }
            }
        });
        
        for(Song song : songList){
            if(!albumMap.containsKey(song.genre)){
                albumMap.put(song.genre, 1);
                bestAlbum.add(song.id);
            } else {
                int genreCnt = albumMap.get(song.genre);
                
                if(genreCnt >= 2) continue;
                else {
                    albumMap.put(song.genre, genreCnt + 1);
                    bestAlbum.add(song.id);
                }
            }
        }
        
        int[] answer = new int[bestAlbum.size()];
        for(int i = 0 ; i < answer.length ; ++i){
            answer[i] = bestAlbum.get(i);
        }
        
        return answer;
    }
}

## Hash 베스트엘범 By 산희

산희가 코드 보내주면 추가예정

답변 0