튜플

nelljun_kim·2022년 3월 22일
0

코딩테스트

목록 보기
4/8

처음 풀이

"{{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);
}
profile
세상을 다양하게 하는 개발자

0개의 댓글