주어진 튜플의 집합의 크기가 작은것부터 차례대로 집합의 원소를 배치하면 올바른 튜플이 나온다는 아이디어로 문제를 풀었다.
예를 들어 {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}} 배열이 있다면
먼자 가장 작은 {2} 집합의 숫자인 2를 집어넣는다.
그 다음 집합인 {2, 1}에서 이미 넣은 2를 빼고 1을 넣는다.
그 다음 집합인 {2, 1, 3}에서 이미 넣은 2, 1을 빼고 3을 넣는다.
그 다음 집합인 {2, 1, 3, 4}에서 이미 넣은 2, 1, 3을 빼고 4를 넣으면
올바른 튜플인 (2, 1, 3, 4)이 나온다.
전체 코드는 다음과 같다.
import java.util.*;
class Solution {
public int[] solution(String s) {
int[] answer;
int count = 0;
s = s.substring(2, s.length()-2);
s = s.replace("{", "");
String[] list = s.split("},");
answer = new int[list.length];
Arrays.sort(list, new Comparator<String>() {
@Override
public int compare(String s1, String s2){
return countChar(s1) - countChar(s2);
}
});
String first = list[0];
answer[count] = Integer.parseInt(first);
count++;
for(int i = 1; i < list.length; i++){
String[] tmp = list[i].split(",");
for(int j = 0; j < count; j++){
String deleteNum = Integer.toString(answer[j]);
for(int k = 0; k < tmp.length; k++){
if(tmp[k].equals(deleteNum)){
tmp[k] = "0";
}
}
}
int left = 0;
for(int j = 0; j < tmp.length; j++){
if(!tmp[j].equals("0")){
left = j;
break;
}
}
answer[count] = Integer.parseInt(tmp[left]);
count++;
}
return answer;
}
public int countChar(String s){
int a = s.length();
s = s.replace(",", "");
int b = s.length();
return a - b;
}
}먼저 주어진 문자열 s의 양 끝의 {{와 }}를 지우고
{를 전부 없애고,
},로 s를 나누어 list 문자열 배열에 저장하였다.
이것으로 집합을 나누며 숫자와 , 로만 이루어지도록 만들었다.
그러면서 정답 배열을 크기를 list배열의 크기로 만들며,
정답 배열의 현재 크기를 나타내는 count 변수를 선언하였다.
int[] answer;
int count = 0;
s = s.substring(2, s.length()-2);
s = s.replace("{", "");
String[] list = s.split("},");
answer = new int[list.length];list 문자열 배열을 집합의 원소 갯수의 오름차순으로 정렬한다.
이를 위해 문자열 안의 , 갯수로 원소 갯수를 파악했다.
Arrays.sort(list, new Comparator<String>() {
@Override
public int compare(String s1, String s2){
return countChar(s1) - countChar(s2);
}
});
...
public int countChar(String s){
int a = s.length();
s = s.replace(",", "");
int b = s.length();
return a - b;
}배열의 크기로 list 배열을 정렬하였으므로
원소가 하나밖에 없는 첫 번째 배열을 가져와 그 수를 정답 배열에 넣었다.
정답 배열에 숫자가 하나 들어갔으므로 count를 1 증가시킨다.
String first = list[0];
answer[count] = Integer.parseInt(first);
count++;나머지 배열들도 확인한다.
지금부턴 집합에 2개 이상의 수가 들어있으므로 tmp 배열에 , 기준으로 잘라 넣었다.
정답 배열에 저장된 숫자들을 하나씩 꺼내 tmp 배열에 그 숫자와 같은 숫자가 있는지 확인하고, 있다면 그 숫자를 0으로 만든다.
그 후 다시 tmp 배열을 탐색하며 0이 아닌 숫자가 있는 위치를 찾은 후, 그 위치의 숫자를 정답 배열에 넣는다.
정답 배열에 숫자가 하나 들어갔으므로 count를 1 증가시킨다.
for(int i = 1; i < list.length; i++){
String[] tmp = list[i].split(",");
for(int j = 0; j < count; j++){
String deleteNum = Integer.toString(answer[j]);
for(int k = 0; k < tmp.length; k++){
if(tmp[k].equals(deleteNum)){
tmp[k] = "0";
}
}
}
int left = 0;
for(int j = 0; j < tmp.length; j++){
if(!tmp[j].equals("0")){
left = j;
break;
}
}
answer[count] = Integer.parseInt(tmp[left]);
count++;
}
return answer;
}문제를 풀긴 했지만 3중 반복문을 사용해 시간이 오래 걸린다.
다른 사람들의 풀이를 찾아보며 더 효율적인 방법을 찾아 볼 필요가 있다고 느꼈다.
