[Algorithm] Programmers_튜플 in Java

하이초·2024년 3월 11일

Java algorithm programmers

Algorithm

목록 보기

85/94

💡 Programmers Level.2 튜플:

주어진 집합 String을 통해 원 튜플 찾기

🌱 코드 in Java

알고리즘: Set

import java.util.*;

class Solution {
    public int[] solution(String s) {
        String[] tuple = s.replaceAll("\\{\\{|\\}\\}", "").split("},\\{"); // 집합별 분리
        Arrays.sort(tuple, (s1, s2) -> s1.length() - s2.length()); // 가장 첫번째부터 정렬
        int len = tuple.length;
        int[] answer = new int[len];
        Set<String> set = new HashSet<>();
        for (int i = 0; i < tuple.length; i++) {
            String[] elem = tuple[i].split(",");
            for (String e : elem) {
                if (set.add(e)) { // 중복되지 않은 요소 찾아내기
                    answer[i] = Integer.parseInt(e); // 새롭게 나온 요소 answer에 추가하기
                    break;                    
                }
            }
        }
        return answer;
    }
}

이번 문제는 3단계로 나눠서 생각했다.

집합 분리
튜플 순서를 알 수 있도록 문장을 길이순으로 정렬하기
정렬된 문자열을 통해 계속 다음 문자열에 새로 등장하는 숫자를 answer에 추가하기

여기서 1,2번은 크게 어렵지 않은 부분이었고, 3번을 어떻게 할까 하다가
'중복되지 않은 새로운 문자'이기 때문에 set 자료구조를 사용했다.

만약 set.add() 함수가 true/false를 반환해주지 않았다면,
LinkedListSet을 사용한 뒤 iterator로 순회하며 순서대로 answer에 넣어줬어야 했을 것이다.
그렇지만 true/false를 반환받기 때문에 햅삐!

다른 풀이를 찾아 본 것 중에는

import java.util.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

class Solution {
    public int[] solution(String s) {

        Map<String, Integer> map = new HashMap<>();
        Pattern pattern = Pattern.compile("[0-9]+");
        Matcher matcher = pattern.matcher(s);
        while (matcher.find()) {
            String n = matcher.group();
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        int size = map.size();
        int[] answer = new int[size];
        for (String key: map.keySet()) {
            answer[size - map.get(key)] = Integer.parseInt(key);
        }
        return answer;
    }
}

import java.util.*;
import java.util.stream.Stream;

class Solution {
    final Map<Integer, Integer> counts = new LinkedHashMap<>();

    public int[] solution(String s) {
        Stream.of(s.replaceAll("[}{]", "").split(",")).mapToInt(Integer::parseInt)
                .forEach(i -> counts.merge(i, 1, Integer::sum));
        return counts.entrySet().stream().sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
                .map(Map.Entry::getKey).mapToInt(x -> x).toArray();
    }
}

이런 풀이들이 있었는데, 내가 3번째 단계에서 전 문장과 비교하여 새롭게 등장한 숫자를 중점으로 뒀다면 이
이 두 풀이는 각 숫자의 등장 횟수를 통해 많이 등장할수록 튜플의 앞 순서라는 아이디어를 통해 접근한 것이다.
첫번째 Pattern Matcher를 사용한 방법은 등장 횟수를 통해 size - count로 index에 접근하기 때문에 정렬도 필요 없다. 정말 짱이다..

아직 Pattern이랑 Matcher의 활용을 잘 해보지 못했는데, 이런 때 배워둬야겠다.
Stream은 말해 뭐해.. 어떻게 저렇게 엮지...