알고리즘(베스트 앨범, 보행자 천국)

[베스트 앨범]

 

* 조건

1. 각 곡에 대한 장르(genres), 재생 횟수(plays)가 주어진다
2. 배열의 인덱스가 해당 곡의 고유 번호이다
3. 정렬해야할 조건이 3가지이다.
   • 재생된 횟수가 가장 많은 장르 순으로 내림차순 정렬
   • 해당 장르 내에서 각 곡마다 재생된 횟수 기준으로 내림차순 정렬
   • 만약 각 곡의 재생된 횟수가 같다면 고유 번호로 오름차순 정렬
4. 만약 해당 장르의 곡이 1개라면 1개만 출력, 2개 이상이라면 2개만 리턴한다
5. 베스트 앨범에 들어갈 노래의 고유 번호를 출력한다

 

 

* 알고리즘

• HashMap

 

 

* 로직

• 해쉬맵 형태를 HashMap<장르, 리스트> 구조를 만든다 -> A
• 리스트에는 HahsMap<곡의 고유번호, 재생된 횟수> 형태로 보관한다
  ex. classic, [<0, 500>, <2, 150>, <3, 800>]
• 장르별로 재생된 횟수를 HashMap<장르, 재생된 횟수> 형태로 보관한다 -> B
• A의 리스트를 (조건-3)을 고려하여 정렬을 진행한다
• 제일 많이 재생된 장르를 선택하고
  • 해당 장르 내에 존재하는 곡의 고유번호를 담는다
  • (조건-4)를 만족한다
• 선택된 장르는 지워준다

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;

public class Problem_BestAlbum {

    public static void main(String[] args) {
        String[] genres = {
                "classic", "pop", "classic", "classic", "pop"
        };
        int[] plays = {
                500, 600, 150, 800, 2500
        };

        int[] answers = solution(genres, plays);
        for(int ans : answers)
            System.out.print(ans + " ");
    }

    public static int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        ArrayList<Integer> results = new ArrayList<>();     //정답 관리 리스트

        /*
        * 장르    ,   리스트(곡 인덱스와 재생된 횟수를 관리 = 해쉬맵)
        * classic,	[<0, 500>, <2, 150>, <3, 800>]
        * pop,	[<1, 600>, <4, 2500>]
        * */
        HashMap<String, ArrayList<HashMap<Integer, Integer>>> hashMap = new HashMap<>();

        for(int i=0; i<genres.length; ++i){
            boolean find = false;

            //아무것도 없을땐 처음꺼 추가
            if(hashMap.size() == 0){
                ArrayList<HashMap<Integer, Integer>> tmp = new ArrayList<>();
                HashMap<Integer, Integer> hashTmp = new HashMap<>();
                hashTmp.put(i, plays[i]);
                tmp.add(hashTmp);

                hashMap.put(genres[i], tmp);
                continue;
            }

            else if(hashMap.size()>0){
                for(String key : hashMap.keySet()){
                    if(key.equals(genres[i])){
                        //같은 장르를 찾았다면 find = true
                        //찾았다면 -> 기존값에서 추가
                        HashMap<Integer, Integer> hashTmp = new HashMap<>();
                        hashTmp.put(i, plays[i]);
                        hashMap.get(key).add(hashTmp);

                        find = true;
                        break;
                    }
                }
            }

            //같은 장르를 찾지 못했다면 -> 생성
            if(!find) {
                ArrayList<HashMap<Integer, Integer>> tmp = new ArrayList<>();
                HashMap<Integer, Integer> hashTmp = new HashMap<>();
                hashTmp.put(i, plays[i]);
                tmp.add(hashTmp);

                hashMap.put(genres[i], tmp);
            }
        }

        //장르별 재생된 횟수 관리
        HashMap<String, Integer> genrePlayed = new HashMap<>();
        for(String genre : hashMap.keySet()){
            int played = 0;
            ArrayList<HashMap<Integer, Integer>> tmp =  hashMap.get(genre);

            //장르별로 실행된 횟수 더하기
            for(int a=0; a<tmp.size(); ++a){
                for(Integer songIdx : tmp.get(a).keySet()){
                    played += tmp.get(a).get(songIdx);
                }
            }

            //더해진 값을 넣어주기
            genrePlayed.put(genre, played);
        }

        //같은 장르 내에 있는 곡들은 내림차순 정렬
        /*
        * classic,	[<3, 800>, <0, 500>, <2, 150>]
        * pop,	[<4, 2500>, <1, 600>]
        * */
        for(String genre : hashMap.keySet()){
            Collections.sort(hashMap.get(genre), new Comparator<HashMap<Integer, Integer>>() {
                @Override
                public int compare(HashMap<Integer, Integer> o1, HashMap<Integer, Integer> o2) {
                    Integer key1 = 0;
                    Integer key2 = 0;

                    Integer value1 = 0;
                    Integer value2 = 0;

                    for(Integer key : o1.keySet()){
                        key1 = key;
                        value1 = o1.get(key1);
                    }

                    for(Integer key : o2.keySet()){
                        key2 = key;
                        value2 = o2.get(key2);
                    }

                    if(value1 > value2) return -1;
                    else if(value1 == value2){
                        if(key1 > key2) return 1;
                        else return -1;
                    }

                    else return 1;
                }
            });
        }

        while (true){
            if(genrePlayed.size() == 0) break;

            int maxPlayed = Integer.MIN_VALUE;
            String maxPlayedGenre = "";
            for(String genre : genrePlayed.keySet()){
                if(maxPlayed < genrePlayed.get(genre)){
                    maxPlayed = genrePlayed.get(genre);
                    maxPlayedGenre = genre;
                }
            }

            for(int i=0; i<hashMap.get(maxPlayedGenre).size(); ++i){
                if(i >= 2) break;

                //큰 순서로 곡의 인덱스 추가
                for(Integer songIdx : hashMap.get(maxPlayedGenre).get(i).keySet()){
                    results.add(songIdx);
                }
            }

            //답에 넣은 장르는 제거
            genrePlayed.remove(maxPlayedGenre);
        }

        //답 주입해주기
        answer = new int[results.size()];
        for(int i=0; i<answer.length; ++i){
            answer[i] = results.get(i);
        }

        return answer;
    }
}

 

<다시 풀어본 코드>

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;

class SongInfo implements Comparable<SongInfo> {
    public int idx;
    public int played;

    public SongInfo(int idx, int played) {
        this.idx = idx;
        this.played = played;
    }

    @Override
    public int compareTo(SongInfo o) {
        if(this.played < o.played) return 1;
        else if(this.played == o.played){
            if(this.idx > o.idx) return 1;
            else return -1;
        }
        return -1;
    }
}

public class Problem_BestAlbum {

    public static void main(String[] args) {
        String[] genres = {"classic", "pop", "classic", "classic", "pop"};
        int[] plays = {500, 600, 150, 800, 2500};
        int[] answers = solution(genres, plays);
        for(int ans : answers)
            System.out.print(ans + " ");
    }

    public static int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        HashMap<String, ArrayList<SongInfo>> hashMap = new HashMap<>();

        for(int i=0; i<genres.length; ++i){
            String genre = genres[i];
            int played = plays[i];

            if(hashMap.size() == 0){
                ArrayList<SongInfo> tmp = new ArrayList<>();
                tmp.add(new SongInfo(i, played));
                hashMap.put(genre, tmp);
            }

            else {
                //같은 장르 탐색
                boolean find = false;
                for(String key : hashMap.keySet()){
                    if(key.equals(genre)){
                        ArrayList<SongInfo> songInfos = hashMap.get(key);
                        songInfos.add(new SongInfo(i, played));
                        hashMap.put(genre, songInfos);

                        find = true;
                        break;
                    }
                }

                if(!find) {
                    ArrayList<SongInfo> tmp = new ArrayList<>();
                    tmp.add(new SongInfo(i, played));
                    hashMap.put(genre, tmp);
                }
            }
        }

        //장르에 속한 노래의 누적 재생수 정보 담기
        ArrayList<HashMap<String, Integer>> genrePlayed = new ArrayList<>();
        for(String key : hashMap.keySet()){
            ArrayList<SongInfo> songInfos = hashMap.get(key);
            int playCnt = 0;

            for(SongInfo song : songInfos){
                playCnt += song.played;
            }

            HashMap<String, Integer> tmp = new HashMap<>();
            tmp.put(key, playCnt);
            genrePlayed.add(tmp);
        }

        //많이 재생된 장르 순으로 정렬
        Collections.sort(genrePlayed, new Comparator<HashMap<String, Integer>>() {
            @Override
            public int compare(HashMap<String, Integer> o1, HashMap<String, Integer> o2) {
                int v1 = 0, v2 = 0;
                for(String key : o1.keySet()){
                    v1 = o1.get(key);
                }

                for(String key : o2.keySet()){
                    v2 = o2.get(key);
                }
                return v2 - v1;
            }
        });

        //정렬된 장르를 기준으로 2곡씩 선별(1곡 밖에 없다면 1곡만)
        ArrayList<Integer> results = new ArrayList<>();
        for(int i=0; i<genrePlayed.size(); ++i){
            String genre = null;
            for(String tmp : genrePlayed.get(i).keySet())
                genre = tmp;

            //장르 내에서 많이 재생된 노래 순으로 정렬
            ArrayList<SongInfo> songInfos = hashMap.get(genre);
            Collections.sort(songInfos);

            for(int s = 0; s< songInfos.size(); ++s){
                if(s == 2) break;
                results.add(songInfos.get(s).idx);
            }
        }

        answer = new int[results.size()];
        for(int i=0; i<answer.length; ++i){
            answer[i] = results.get(i);
        }

        return answer;
    }
}

 

 

 

[보행자 천국]

 

* 조건

1. 지도에 대한 사이즈 m,n이 주어진다
2. 배열의 값이
   • 0이면 -> 자동차가 자유롭게 지나간다
   • 1이면 -> 지나갈 수 없다
   • 2이면 -> 좌, 우 회전이 불가능하다 = 직진만 가능
3. 출발지(0,0) 부터 목적지(m-1, n-1)까지 가기 위한 경로의 개수를 출력한다

 

 

* 알고리즘

• DP

 

 

* 로직

• 우선 왼쪽 상단에서 오른쪽 하단으로 가려면 2가지 방향성이 존재한다 (왼쪽 -> 오른쪽 A, 위 -> 아래 B)
• 현재 좌표가
  1. 0이라면: 현재 좌표 기준 위에서 아래로 오는 곳의 값 + 현재 좌표 기준 왼쪽에서 오른쪽으로 오는 곳의 값을 A와 B 배열에 넣어준다
  2. 1이라면: 현재 좌표로는 지나갈 수 없기 때문에 0
  3. 2라면: 각각 이전 좌표의 값을 A와 B배열에 넣어준다
• 저번에 풀어봤던 [등굣길] 문제와 유사하다 (참고: https://uyoo-story.tistory.com/41)

 

알고리즘(등굣길, 순위)

 

 

public class Problem_Pedestrian {
    static final int MOD = 20170805;

    public static void main(String[] args) {
        int m = 3;
        int n = 3;
        int[][] city_map = {
                {0, 0, 0}, {0, 0, 0}, {0, 0, 0}
        };

        int answer = solution(m, n, city_map);
        System.out.println(answer);
    }

    public static int solution(int m, int n, int[][] cityMap) {
        int answer = 0;

        /*
            * leftToRight[i][j] = 현재 좌표를 기준으로 왼쪽에서 오른쪽으로 갈 수 있는 경우의 수
            * topToBottom[i][j] = 현재 좌표를 기준으로 위에서 아래로 갈 수 있는 경우의 수

            * 현재 위치가 0 (정상 진행): 2 방향에 대해 모두 갈 수 있기 때문에 둘다 누적
               -> leftToRight[i][j] += leftToRight[i][j-1] + topToBottom[i-1][j] 누적
               -> topToBottom[i][j] += leftToRight[i][j-1] + topToBottom[i-1][j] 누적

            * 현재 위치가 1 (통행 금지): 2 방향에 대해 모두 갈 수 없 때문에 0으로 갱신
               -> leftToRight[i][j] = 0
               -> topToBottom[i][j] = 0

            * 현재 위치가 2 (좌회전 or 우회전 금지): 해당 방향으로 오는 값만 받기
               -> leftToRight[i][j] = leftToRight[i][j-1]
               -> topToBottom[i][j] = topToBottom[i-1][j]
        */

        int[][] leftToRight = new int[m+1][n+1];
        int[][] topToBottom = new int[m+1][n+1];

        //시작점은 모두 갈 수 있음
        leftToRight[1][1] = 1;
        topToBottom[1][1] = 1;

        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                if(cityMap[i-1][j-1] == 0){
                    leftToRight[i][j] += (leftToRight[i][j-1] + topToBottom[i-1][j]) % MOD;
                    topToBottom[i][j] += (leftToRight[i][j-1] + topToBottom[i-1][j]) % MOD;
                }

                else if(cityMap[i-1][j-1] == 1){
                    leftToRight[i][j] = 0;
                    topToBottom[i][j] = 0;
                }

                else {
                    leftToRight[i][j] = leftToRight[i][j-1];
                    topToBottom[i][j] = topToBottom[i-1][j];
                }
            }
        }

        answer = (leftToRight[m][n-1] + topToBottom[m-1][n]) % MOD;
        return answer;
    }
}