[201027] 튜플 - 2019 카카오 개발자 겨울 인턴십(level2)

0. 문제 유형 : Set, Map 등 적절한 자료구조 활용하기

1. 문제 이해

programmers.co.kr/learn/courses/30/lessons/64065

코딩테스트 연습 - 튜플

(1) n-튜플(n-tuple) : n개의 요소를 가진 튜플

(a1, a2, a3, ..., an)

- 중복 원소 가능 (BUT 문제에서는 중복되는 원소가 없는 튜플 형태로 고려)

- 원소에 정해진 순서가 있다.

- 튜플의 원소 개수는 유한하다.

 

(2) n-튜플의 표현 방식

(a1, a2, a3, a4) = {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}} (단, 원소의 순서는 바뀔 수 있음)

 

- 규칙 : 첫 번째 원소부터 하나씩 추가하는 방식 → 먼저 등장할수록 전체 참여횟수는 높아진다.

 

(3) answer(output) : (2)의 형태로 튜플이 주어졌을 때 (a1, a2, a3, ...) 형태의 튜플로 변경

 

 

2. 전략

(1) String s를 이차원배열 형태로 변환

- "{{2},{2,1},{2,1,3},{2,1,3,4}}" String으로 주어져 각 원소의 분리가 필요

- s.substring(2, s.length()-2).replace("},{", " ").split(" ") : {2}, {2,1}, {2,1,3}, {2,1,3,4} String이 각각 원소인 String 배열

- tSet : 각 원소를 다시 ","으로 split하여 tSet 2차원 배열에 넣음

 

(2) HashMap 이용

- tSet[maxIndex] : tSet 중 개수가 size인 배열 = 배치시킬 모든 원소가 들어있는 배열

- key : tSet[maxIndex]의 각 요소 - value : 해당 요소가 등장하는 횟수

- 횟수의 내림차순으로 tSet[maxIndex]를 재정렬하고 int형으로 변환해 answer 배열로!!

 

 

3. 참고사항

(1) HashMap의 정렬

: value에 따라 내림차순으로 keySet을 정렬해야 한다.

① keySet을 ArrayList 형태로 변환 : set은 순서가 없는 컬렉션이므로 정렬이 불가능하기 때문에

② Collections.sort와 compareTo를 이용해 정렬

ArrayList<String> keyList = new ArrayList<>(map.keySet());
Collections.sort(keyList, (o1, o2) -> map.get(o2).compareTo(map.get(o1)));

 

(2) 훨씬 간결한 풀이 : "Set의 중복 불가능"을 이용

① String 배열로 변환 : replaceAll, trim, split를 이용하여 ["a1", "a1,a2", "a1,a2,a3", ...] 형태로 변환

② String 배열의 길이를 기준으로 오름차순 정렬

Arrays.sort(arr, (a,b) -> {return a.length()-b.length()});

③ 차례로 Set 컬렉션에 add하고, add가 정상적으로 이루어지면 answer에 추가

- 중복 없이 add가 되면 set.add(스트링)은 true를 return 한다!

 

 

4. 코드

import java.util.*;
class Solution {
    public int[] solution(String s) {
        int[] answer = {};
        //String배열로 변환 & hashmap에 원소 저장
        String[] arr = s.replaceAll("[{]", " ").replaceAll("[}]", " ").trim().split(" , ");
        System.out.println(s.replaceAll("[{]", " ").replaceAll("[}]", " "));
        for(int i= 0; i < arr.length; i++){
            System.out.println(arr[i]);
        }
        String[] s2 = s.substring(2, s.length()-2).replace("},{", " ").split(" ");
        String[][] tSet = new String[s2.length][];
        HashMap<String, Integer> map = new HashMap<>();
        int size = s2.length; int maxIndex = 0;
        for(int i = 0; i < size; i++){
            tSet[i] = s2[i].split(",");
            if(tSet[i].length == size){
                maxIndex = i;
                for(int j = 0; j < size; j++){
                    map.put(tSet[i][j], 0);
                }
            }
        }
        //해당 숫자 map value ++
        for(int i = 0; i < size; i++){
            for(int j = 0; j < tSet[i].length; j++){
                int value = map.get(tSet[i][j]);
                map.replace(tSet[i][j], value+1);
            }
        }
        //map value 기준 내림차순 배열
        ArrayList<String> keyList = new ArrayList<>(map.keySet());
        Collections.sort(keyList, (o1, o2) -> map.get(o2).compareTo(map.get(o1)));
        answer = new int[size];
        for(int i = 0; i < size; i++){
            answer[i] = Integer.parseInt(keyList.get(i));
        }
        // Arrays.sort(tSet[maxIndex], new Comparator<String>(){
        //     public int compare(String a, String b){
        //         return (map.get(b)).compareTo(map.get(a));
        //     }
        // });
        // answer = new int[size];
        // for(int i =0; i < size; i++){
        //     answer[i] = Integer.parseInt(tSet[maxIndex][i]);
        // }
        return answer;
    }
}