본문 바로가기

알고리즘 풀이/프로그래머스

[프로그래머스] 튜플 / 2019 카카오 개발자 겨울 인턴십 - JAVA

🔗 문제 링크

[프로그래머스] 튜플 / 2019 카카오 개발자 겨울 인턴십

 

코딩테스트 연습 - 튜플

"{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1]

programmers.co.kr

 

📝 풀이 과정

튜플에는 순서가 있지만 집합에는 순서가 없다는 것이 중요하다.

{1}
{1,2}
{1,2,3}

튜플 (1, 2, 3)을 집합으로 만들면 아래와 같이 구성되는데 잘 살펴보면 길이가 하나씩 증가할 때마다 새로운 원소가 들어오게 되는 것을 알 수 있다. 따라서, 집합을 },{로 분할하고 길이에 따라 정렬하면 튜플이 추가되는 순서대로 정렬된다.

 

중복되는 원소가 없기때문에 Set을 활용하였다. 튜플을 순서대로 돌며 set에 없는 원소가 나오면 새로운 원소가 튜플에 추가된 것이기때문에 답에 추가해주었다.

 

💻 코드

import java.util.*;

public class Solution {
    public int[] solution(String s) {
        String[] tuples = Arrays.stream(s.replaceAll("\\{\\{|}}", "").split("},\\{"))
                .sorted(Comparator.comparingInt(String::length)).toArray(size -> new String[size]);

        Set<Integer> set = new HashSet<>();
        List<Integer> ans = new ArrayList<>();
        for (String tuple : tuples) {
            int[] nums = Arrays.stream(tuple.split(",")).mapToInt(Integer::parseInt).toArray();

            for (int num : nums) {
                if (!set.contains(num)) {
                    set.add(num);
                    ans.add(num);
                    break;
                }
            }
        }
        return ans.stream().mapToInt(i -> i).toArray();
    }
}