[Programmers] 2019 카카오 인턴십 2번 - 튜플

[문제 설명]

자료구조 중 하나인 튜플을 집합 기호로 표현한 String이 주어진다. (s)

집합 기호로 구성된 String으로 튜플을 찾아내는 문제

 

[조건]

1 <= s의 길이 <= 1,000,000

1 <= 튜플의 원소 <= 100,000

1 <= 튜플 원소의 개수 <= 500

 

[풀이]

주어진 문자열의 특징을 파악하여, 각 집합의 숫자 원소로 파싱한다.

이후, 집합의 길이에 따라 정렬을 한다.

길이가 짧은 집합에 포함된 원소부터 추가한다.

 

중복 체크를 할 때 나는 배열을 사용하였다.

그러나, 문제의 제한 사항에 원소의 개수나, 원소의 크기가 주어져 있지 않은 경우에는 HashSet과 같은 자료구조를 쓰는게 적절해보인다. 

 

import java.util.Arrays;

public class Programmers_kakao2019_intern_2 {
    public static int[] solution(String s) {
        int[] answer;
        int ansIdx = 0;
        
        String[] splitGroup = new String[500];
        boolean[] isAdded = new boolean[100001]; 
        String[] temp = new String[500];
        
        // s의 앞 : '{{', 뒤 : '}}' 자르기
        s = s.substring(2, s.length() - 2);
        
        // s를 },{ 로 split하기
        splitGroup = s.split("\\},\\{");
        answer = new int[splitGroup.length];
        
        // split된 String을 길이 순으로 정렬
        Arrays.sort(splitGroup, (String a, String b) -> a.length() - b.length());
                
        // 숫자 하나씩 추가하기.
        for (int i = 0; i < splitGroup.length; ++i) {
        	temp = splitGroup[i].split(",");
        	
        	for (int j = 0; j < temp.length; ++j) {
        		int curInt = Integer.valueOf(temp[j]);
        		
        		if (!isAdded[curInt]) {
        			answer[ansIdx++] = curInt;
        			isAdded[curInt] = true;
        			break;
        		}
        	}
        }
        return answer;
    }
	
	public static void main(String[] args) {
		System.out.println(Arrays.toString(solution("{{2,1,3,4},{2},{2,1},{2,1,3}}")));
	}
}

 

 

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

코딩테스트 연습 - 튜플