소스 보러가기
문제 보러가기

사용한 알고리즘 및 자료구조

HashMap,ArrayList

풀이
문제를 보고 HashMap 사용을 떠올랐다. 가장 먼저 생각한 것은 자바의 콜렉션을 최소화 하여 문제를 풀어내는 것 이었다. 그리고 총 4개의 콜렉션을 사용하여 문제를 풀었다.

먼저 파악해야 될 것은 정렬의 우선순위 요소 파악이다.

“장르 우선순위 , 노래 재생 횟수, 고유번호가 낮은 순서” 이렇게 우선순위가 선정되어 정렬이 된다. 파악한 우선순위로 차례차례 문제를 풀면 간단히 해결이 된다.

  1. 각 장르별로 재생된 횟수 구하여 HashMap에 담기

  2. 노래에 대한 구조체를 만들어 ArrayList에 담기

  3. 정렬하기 : Collections.sort() 함수 이용

  4. 정렬된 ArrayList에서 장르별 순서대로 2개씩 노래 새로운 ArrayList에 담기

간단하게 표현하면 이렇게 4단계로 문제가 풀린다. 자세한건 코드를 보면서 파악하기 바란다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
    // before test, have to delete 'static' keywords
    public static int[] solution(String[] genres, int[] plays) {
        HashMap<String, Integer> genresCheck = new HashMap<String, Integer>();
        HashMap<String, Integer> inputCheck = new HashMap<String, Integer>();
        ArrayList<Song> songList = new ArrayList<Song>();
        ArrayList<Integer> outputList = new ArrayList<Integer>();
        //1. genres count
        
        
        
        for(int g_idx = 0; g_idx < genres.length; g_idx++) {
 
            String g_str = genres[g_idx];
            songList.add(new Song(g_str,plays[g_idx],g_idx));
            
            if(genresCheck.containsKey(g_str)) {
                genresCheck.put(g_str, genresCheck.get(g_str)+plays[g_idx]);
            } else {
                
                genresCheck.put(g_str, plays[g_idx]);
            }
            
        }
        //2. sort
        
        Collections.sort(songList, new Comparator<Song>() {
            
            //s1 new
            @Override
            public int compare(Song s1, Song s2) {
                
                if(s1.genresName.equals(s2.genresName)) {
                    
                    if(s1.playCount != s2.playCount) {
                        return - (s1.playCount - s2.playCount);
                    } else {
                        
                        return (s1.songNum - s2.songNum);
                    }
                    
                } else {
                    
                    return -(genresCheck.get(s1.genresName) - genresCheck.get(s2.genresName));
                    
                }
                
            }
            
            
        }); 
        //3.checking
        for(int idx = 0; idx < songList.size(); idx++) {
            
            Song song = songList.get(idx);
            
            if(!inputCheck.containsKey(song.genresName)) {
                inputCheck.put(song.genresName, 1);
                outputList.add(song.songNum);
            } else {
                
                int cnt = inputCheck.get(song.genresName);
                
                if(cnt > 1) {
                    continue;
                } else {
                    inputCheck.put(song.genresName, cnt+1);
                    outputList.add(song.songNum);
 
                }
                
            }
            
        }
        
        int[] answer = new int[outputList.size()];
        
        for(int s_idx = 0; s_idx < answer.length; s_idx++) {
            answer[s_idx] = outputList.get(s_idx);
        }
 
 
        return answer;
    }
 
    static class Song {
        
        String genresName;
        int playCount;
        int songNum;
 
        public Song(String genresName, int playCount, int songNum) {
            
            this.genresName = genresName;
            this.playCount = playCount;
            this.songNum = songNum;
 
        }
 
    }
 
cs

'알고리즘(추가예정) > 기타' 카테고리의 다른 글

[프로그래머스] 인형뽑기  (0) 2020.08.30

블로그를 다시 시작합니다. 

알고리즘은 이전에 풀어놓은것을 사용하지 않고 다시 풀면서 

업로드를 진행할 예정입니다.

연구실에서 경험한 

SDN, NFV, 컨테이너, 쿠버네티스등 다양한 분야에 관련된 글 포스팅을

진행할 예정입니다.

현재 구직중에 있습니다 

링크드인 :  https://www.linkedin.com/in/gilho0608/

 

 

'일상 > 그냥이야기' 카테고리의 다른 글

2021년 취업 성공 후기  (2) 2021.01.17

소스 보러가기
문제 보러가기

사용한 알고리즘 및 자료구조
DFS/BFS, 그래프

풀이

간단한 DFS/BFS 문제이다. 문제를 푸는데 20분도 안 걸렸다. 이번에는 DFS를 이용해서 해당 문제를 풀었다. 이 문제를 읽고 생각을 했던 것은 2차원 배열에서 (n,n) 칸들을 기준으로 좌우 대칭이 된다는 것이다. 또한 각각의 값들이 연결관계를 표현했다. 따라서 처음에 탐색할 때는 1/2만 탐색을 하고 DFS 를 사용할 때는 연결관계를 기준으로 탐색을 하면 된다. 보통의 DFS 문제는 ‘상하좌우’로 움직이면서 문제를 해결했지만, 해당 문제는 배열의 값들이 내포하고 있는 연결관계를 이용해서 DFS 함수를 구현했다.

  1. 초기화
  2. 문제에 해당하는 조건( 배열의 값 : 1 && 아직 탐색하지 않은 칸) 찾기 ,조건을 찾을 때 마다 answer++
  3. 조건 찾고 나서 DFS 함수를 이용해 연결관계를 따라 영역표시하기
  4. 다시 2-3번 반복
  5. Answer 출력

간단한 DFS 문제이다. 실제로 삼성 시험을 봤던 사람들에게는 매우 쉬웠을 거라 생각한다. 다만 이것을 어떻게 해야 더 효율적으로 구현할 수 있을까 고민해보았다. 간단한 문제라 특별하게 적용할 것은 없었으나, 그래도 고민 해보면 좋을 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
    public static int SIZE;
 
    // before test, have to delete 'static' keywords
    public static int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[][] visited = new boolean[n][n];
        SIZE = n;
 
        for (int c_idx = 0; c_idx < n; c_idx++)
            for (int r_idx = c_idx; r_idx < n; r_idx++) {
 
                if ((computers[c_idx][r_idx] == 1) && (visited[c_idx][r_idx] == false)) {
                    visited[c_idx][r_idx] = true;
                    dfs(r_idx, visited, computers);
                    answer++;
 
                }
            }
 
        return answer;
    }
 
    public static void dfs(int idx, boolean[][] visited, int[][] computers) {
 
        for (int col = 0; col < SIZE; col++) {
 
            if ((computers[idx][col] == 1) && (visited[idx][col] == false)) {
 
                visited[idx][col] = true;
 
                dfs(col, visited, computers);
 
            }
 
        }
 
    }
 
 
cs

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 124 나라의 숫자  (0) 2020.08.30
[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13

+ Recent posts

티스토리툴바