[2019 카카오 개발자 겨울 인턴쉽] 튜플 for JAVA (2)

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

코딩테스트 연습 - 튜플

[문제 설명]

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

• (a1, a2, a3, ..., an)

튜플은 다음과 같은 성질을 가지고 있습니다.

1. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
2. 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
3. 튜플의 원소 개수는 유한합니다.

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

• {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

와 같이 표현할 수 있습니다. 이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
• {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

• s의 길이는 5 이상 1,000,000 이하입니다.
• s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.
• 숫자가 0으로 시작하는 경우는 없습니다.
• s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
• s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
• return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

 

[풀이]

주어진 조건에 따라 순서대로 해결하면 되는 문제이므로 내가 생각하고 푼 방식을 순서대로 작성하겠다

 

그전에, 내가 처음 문제를 보고 이해가 안 됐던 부분이 있었는데

위와 같이 위의 튜플은 {2, 1, 3}이고 밑에 튜플은 {1, 2, 3}인데 어떻게 같은 {2, 1, 3, 4}가 나오지? 였다

 

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

• {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

이 부분을 다시 읽어보니 이해가 되었다. {a1, a2, a3}든지 {a2, a1, a3}든지 같은 튜플의 부분 집합이다!. 

 

 

테스트 케이스 중 "{{2},{2,1},{2,1,3},{2,1,3,4}}" 에 해당하는 문자열 케이스가 있다. 나는 이 케이스를 아래와 같은 방식으로 풀었다.

 

 1. 요소를 뽑기 위해 앞뒤로 붙어있는 "{"와 "}"를 제거한다. (2번 반복)

• 2},{2,1},{2,1,3},{2,1,3,4

2. 중간에 껴있는 "}, {"를 기준으로 split 해준다. (split 함수는 문자열 배열을 반환한다)

• {2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}    <- 문자열 배열임

3. 위 문자열 배열을 리스트에 넣고 길이 순으로 정렬해준다.(테스트 케이스는 이미 정렬된 상태)

• {2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}

4. 중복을 제거하는 Set 자료구조를 사용하여 길이가 짧은 요소부터 하나씩 넣어준다.(순서를 보장하기 위해 LinkedHashSet을 사용함)

• 2, 1, 3, 4

 

위와 같은 풀이 방식으로 문제를 풀었다. 문제풀이를 기반으로 코드를 작성한 것이기 때문에 바로 이해가 안 되는 부분이 있을 수 있지만 조금만 보면 이해할 수 있다고 생각한다.

 

 

**참고로 자바에서 }, { 같은 특수문자는 앞에 역 슬래쉬 2개를 붙여서 표현해줘야 한다. ex. \\{

 

[코드]

/**
 * level 2 / 2019 카카오 개발자 겨울 인턴십
 * 튜플 
 * https://programmers.co.kr/learn/courses/30/lessons/64065
 */
public int[] solution(String s) {
	s = removeFirstAndLastBracket(s);		//앞뒤 괄호 제거
	s = removeFirstAndLastBracket(s);
    
	String[] elements = s.split("\\},\\{");
	List<String[]> numbers = new ArrayList<>();
	
	
	for(int i = 0; i < elements.length; i++) {
		String[] element = elements[i].split(",");
		numbers.add(element);
	}
	
	numbers = numbers.stream()		//문자열 배열을 길이순 정렬
				.sorted(new Comparator<String[]>() {
					@Override
					public int compare(String[] o1, String[] o2) {
						if(o1.length < o2.length) {
							return -1;
						}else if(o1.length > o2.length) {
							return 1;
						}else {
							return 0; 
						}
					}
				})
				.collect(Collectors.toList());
	
	LinkedHashSet<String> set = new LinkedHashSet<>();
	
	for(int i = 0; i < numbers.size(); i++) {
		String[] temp = numbers.get(i);
		for(String t : temp) {
			if(!set.contains(t)) {		//set에 없는 요소만 add
				set.add(t);
			}
		}
	}
	
	return set.stream().mapToInt(Integer::parseInt).toArray();		//요소를 정수로 변환 후 정수형 배열로 바꿔주기
}

public String removeFirstAndLastBracket(String s) {		///앞뒤 괄호 제거 메서드
	s = s.substring(1);
	s = s.substring(0, s.length() - 1);
	return s;
}

테스트케이스 통과