튜플 - 프로그래머스 (Java, level 2)

 

처음 풀이

 

"{{1,2,3},{2,1},{1,2,4,3},{2}}" 에서 각 { } 묶음을 요소로 하는 String[]을 split(regex) 사용해서 만든다. 

(첫번째 요소 : "1,2,3" 두번째 요소 : "2,1" 세번째 요소 : "1,2,4,3")

 

split()에 파라미터로 들어갈 정규 표현식은 "{{"   "},{"   "}}" 을 포함하면 된다.

 

이를 일반화하면, 

 

1. { or } 둘 중에 하나

2. , 가 들어가거나 안들어가거나

3. { or } 둘 중에 하나

 

이 1, 2, 3이 하나의 그룹이면 된다.

 

"( [ { } ] , ? [ { } ] )"

이를 정규표현식으로 나타내면 다음으로 나타낼 수 있다. (문자 사이사이 띄어쓰기는 무시)

 

주어진 문자열을 보면 항상 시작이 {{ 이므로 split()으로 나눠보면 정규표현식에 걸리기 때문에 

String[]의 첫번째 요소는 항상 빈 문자열이 오게 된다.

이를 제거하기 위해 앞 두 문자열을 자르고 split()을 호출한다. (s.substring(2))

 

String[] strSplit = s.substring(2).split("([{}],?[{}])");

 

"1,2" 문자열을 다시 , 로 split하여 배열의 각 문자열을 다시 배열로 바꿔준다.

 

String[][] finalSplit = new String[strSplit.length][];

for(int i=0; i<strSplit.length; i++) {
    finalSplit[i] = strSplit[i].split(",");
}//for end

 

문제에서 구해야하는 튜플의 원소의 순서는 해당 원소가 많이 나오는 순서이므로,

String[][]의 원소들을 각각 탐색하면서 각 원소숫자 (여기서는 String으로 처리) 를 key, 해당 원소가 나오는 횟수(map.getOrDefault() 사용)를 value로 하여 map에 값을 저장한다.

 

Map<String, Integer> map = new HashMap<>();

for(int i=0; i<finalSplit.length; i++) {
    for (String str : finalSplit[i]) {
    	//현재 map에 str을 key로 하는 value값이 있다면 가져오고,
        //없다면 디폴드 값(0)을 가져와 1을 더하면 해당 원소가 나온 횟수가 된다.
        map.put(str, map.getOrDefault(str, 0)+1);
    }
}//for end

 

map을 value에 따라 내림차순 정렬을 한다.

Collections.sort()를 활용하기 위해 Map의 Entry를 원소로 하는 List를 만든다.

Comparator 클래스의 익명 객체를 sort()의 파라미터로 넘겨준다.

 

List<Entry<String, Integer>> entries = new LinkedList<>(map.entrySet());

Collections.sort(entries, new Comparator<Entry<String, Integer>>() {
    @Override
    public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
   	//내림차순 정렬
        return o2.getValue()-o1.getValue();
    }
});

 

value값에 따라 오름차순 정렬된 list의 각 요소(Entry)에서 key값을 순서대로 리턴할 정답 배열의 요소로 삽입한다.

 

int[] answer = new int[entries.size()];

for(int i=0; i<answer.length; i++) {
    answer[i] = Integer.parseInt(entries.get(i).getKey());
}
 return answer;

 

 

 

개선된 풀이 1

 

어차피 나오는 원소의 갯수만 새면 되기 때문에,

split() 한 번으로 String[]의 각 요소를 바로 원소 단위까지로 하게끔 정규 표현식을 수정한다.

 

처음 풀이의 정규표현식으로 "1,2,3" "2,1" ...으로 문자열이 나눠졌으니 "," 까지 OR 조건으로 포함하면 "1" "2" "3" "2" "1" ...로 문자열을 나눌 수 있다.

", | ( [ { } ] , ? [ { } ] )"

앞에 , | 을 추가했다. 이렇게 하면 split() 한 번으로 각 원소를 요소로 하는 String[]을 만들 수 있다.

 

String[] splitStrArr = s.substring(2).split(",|([{}],?[{}])");

 

 

 

개선된 풀이 2

 

위 풀이에서 사용한 정규 표현식도 사실 만들기 쉽지 않아서 간단한 방법이 있을까 고민했다.

 

중괄호(}를 아예 처음부터 제거하고 가는 풀이를 봤다.

어차피 어차피 답을 구하기 위해서 필요한 것은 숫자 문자열이기 때문에 중괄호를 replaceAll()을 이용해 빈 문자열로 치환한다.

 

String newStr = s.replaceAll("[{}]", "");

 

"{{1,2,3},{2,1},{1,2,4,3},{2}}"   -> "1,2,3,2,1,1,2,4,3,2"

 

문자열이 위처럼 간단해 졌으니 복잡한 정규 표현식 없이 , 하나로 문자열을 나눌 수 있다.

 

String[] splitStrArr = newStr.split(",");

 

위 풀이와 똑같이 Map에 <원소, 원소가 나온 횟수> 값을 넣는다.

 

여기서 원소의 개수가 총 4개라면,

튜플의 맨 앞에 올 원소는 나온 횟수가 4번 -> 정답 배열 0번째 index

두번째 원소는 3번 -> 정답 배열 1번째 index

세번째 원소는 2번 -> 정답 배열 2번째 index

네번째 원소는 1번  -> 정답 배열 3번째 index

 

이 같은 규칙을 활용하여 Map의 value값을 기준으로 내림차순 정렬을 직접하지 않고 value값으로 정답 배열의 index를 구해 대입한다.

 

int size = map.size();
int[] answer = new int[size];

for (String key : map.keySet()) {
    answer[size-map.get(key)] = Integer.parseInt(key);
}

 

 

중간 과정이 많이 줄어들어 유의미하게 시간이 줄어든 것을 볼 수 있다.