문제
문제 분석
처음엔 이해하기 어려워서 부분집합인줄 알았다. 하지만 자세히 읽어보니 부분집합보단 순서가 존재하고 원소가 중복 될수 있다. 즉 (1,2,3) =/= (2,3,1)이고 튜플{{2},{1,2,3},{3,2}}의 집합은 {2,3,1}이다.
풀이
단계별로 풀기
주어진 자료형과 연산과정이 복잡하여 여러 단계로 나누어 생각해보자
1.문자열을 배열로
2.원소들의 순서 정하기
3.원소들의 순서대로 정렬
문자열을 배열로
매개변수 String s는 문자열이다. 문자열안에 대괄호({,})로 묶여 있으므로 대괄호와 콤마를 기준으로 2차원 배열을 구분한다. 그다음 대괄호들을 제거함으로써 내부 1차원 배열로 숫자들을 담아낸다.
String[] arr = s.split("},"); //문자열 내에 배열 구분 String temp=""; String[] temps; int[][] answers = new int[arr.length][]; //문자열을 치환한 배열 저장(가변) //배열로 치환 for(int i=0;i<arr.length;i++) { temp = arr[i].replaceAll("[{|}]",""); //대괄호 제거 temps = temp.split(","); //콤마 제거 answers[i] = new int[temps.length]; //2차원 가변 배열 for(int j=0;j<temps.length;j++) { answers[i][j] = Integer.parseInt(temps[j]); //인트로 변환후 저장 } }
원소들의 순서 정하기
튜플로 주어질땐 순서가 중요하지 않으나 원소들의 집합을 구할땐 순서가 지켜져야 한다. {A,B}만 튜플로 주어지면 A와 B중 어느 원소가 먼저인지 알순 없으나 {{A,B},{A}}의 경우 A가 먼저, {{A,B},{B}}의 경우 B가 먼저 옴을 알수 있다.
{{A,B,C},{A,C},{A}}, {{A,B,C},{A,C},{C}}는 가능하지만 {{A,B,C},{A,C},{B}}는 불가능하다.
더 적은 수의 원소의 부분집합에도 포함될수록 순서가 앞선다는것을 주의 해야 한다.
더 적은 수의 원소를 가진 튜플에도 포함된다는 것은 더 많은 튜플에 포함된다는 말과 동일하다. 즉 순서가 앞 = 더 적은 수의 원소의 튜플에 포함 = 더 많은 수의 튜플에 포함 = 더 많이 언급됨 순서가 앞설수록 문자열에서 더 많이 언급되므로, 언급된 횟수를 세고 내림차순으로 정렬하면 순서대로 정렬할수 있다.
import java.util.*; HashMap<Integer,Integer> hash = new HashMap<>(); //나온 횟수 저장 for(int i=0;i<answers.length;i++) { for(int j=0;j<answers[i].length;j++) { int count = hash.getOrDefault(answers[i][j],0); //이미 있는 값 or 0 hash.put(answers[i][j],count+1); // + 1 하여 추가 } }
해시맵(원소,나온횟수)을 이용하여 원소들이 얼만큼 나왔는지 기록한다.
처음 나온 원소이면 1, 이미 있던 원소이면 +1하여 원소들의 우선순위를 구할 수 있다.
원소들의 순서대로 정렬
해시맵에는 (원소,나온횟수) Key,Value 쌍으로 저장되어 있다. 나온횟수(Value)를 기준으로 정렬하는 방법은 여러가지가 있다.
Comparator 인터페이스를 활용하여 정렬 하였다.
//내림차순 정렬
List<Integer> KeySetList = new ArrayList<>(hash.keySet());
Collections.sort(KeySetList, new Comparator<Integer>() { //Comparator 인터페이스
public int compare(Integer o1, Integer o2) {
return hash.get(o2).compareTo(hash.get(o1)); //내림차순
}
});
//배열 저장
int[] answer = new int[KeySetList.size()]; //배열 크기
for(int i=0;i<KeySetList.size();i++) {
answer[i] = KeySetList.get(i); //요소 저장
}해시맵에 저장된 원소(Key)들을 List에 저장 하고 List에 저장된 원소(Key)들을 나온횟수(Value)를 기준으로 Comparator인터페이스를 재정의하여 정렬할 수 있다.
코드
import java.util.*;
class Solution {
public int[] solution(String s) {
String[] arr = s.split("},"); //문자열 내에 배열 구분
String temp="";
String[] temps;
int[][] answers = new int[arr.length][]; //문자열을 치환한 배열 저장(가변)
HashMap<Integer,Integer> hash = new HashMap<>(); //나온 횟수 저장
//배열로 치환
for(int i=0;i<arr.length;i++) {
temp = arr[i].replaceAll("[{|}]",""); //대괄호 제거
temps = temp.split(","); //콤마 제거
answers[i] = new int[temps.length]; //2차원 가변 배열
for(int j=0;j<temps.length;j++) {
answers[i][j] = Integer.parseInt(temps[j]); //인트로 변환후 저장
}
}
//해시맵에 나온 횟수 저장
for(int i=0;i<answers.length;i++) {
for(int j=0;j<answers[i].length;j++) {
int count = hash.getOrDefault(answers[i][j],0); //이미 있는 값 or 0
hash.put(answers[i][j],count+1); // + 1 하여 추가
}
}
//내림차순 정렬
List<Integer> KeySetList = new ArrayList<>(hash.keySet());
Collections.sort(KeySetList, new Comparator<Integer>() { //Comparator 인터페이스
public int compare(Integer o1, Integer o2) {
return hash.get(o2).compareTo(hash.get(o1)); //내림차순
}
});
//배열 저장
int[] answer = new int[KeySetList.size()]; //배열 크기
for(int i=0;i<KeySetList.size();i++) {
answer[i] = KeySetList.get(i); //요소 저장
}
return answer;
}
}GitHub
