본문 바로가기

Algorithm/프로그래머스

프로그래머스 level1 문제 : 문자열 내 마음대로 정렬하기(java)

반응형

이번 문제는 어려?웠네요.....


문제 설명 : 


문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car]이고 n이 1이면 각 단어의 인덱스 1의 문자 u, e, a로 strings를 정렬합니다.


제한 조건 : 

1. strings는 길이 1 이상, 50이하인 배열입니다.
2. strings의 원소는 소문자 알파벳으로 이루어져 있습니다.
3. strings의 원소는 길이 1 이상, 100이하인 문자열입니다.
4. 모든 strings의 원소의 길이는 n보다 큽니다.
5. 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.



이렇게 문제가 출제 됐습니다.


저는 아래와 같이 풀었고, 예제는 통과했지만 코드채점은 통과 못했네요...


String[] answer = new String[strings.length];
char[] chars = new char[strings.length];

for(int i=0; i<strings.length; i++) {
chars[i] = strings[i].charAt(n);
}

Arrays.sort(chars);

for(int i=0; i<strings.length; i++) {
for(int j=0; j<strings.length; j++) {
if(chars[i] == strings[j].charAt(n)
&& !strings[j].equals(answer[j])) {
answer[i] = strings[j];
break;
}
}
}

if(chars[0] == chars[1] )
Arrays.sort(answer, String.CASE_INSENSITIVE_ORDER);

return answer;



이 방식에서 잘못된 부분은 다양한 테스트를 하지 못한 점과 char[] << 이놈이 생각보다 시간을 잡아먹는거 같네요..


결국 list로 변경, substring을 이용하는 것을 참고했습니다.


String[] answer={""};
ArrayList<String> list = new ArrayList<>();
for(int i=0; i<strings.length; i++)
list.add(strings[i].charAt(n)+strings[i]);

Collections.sort(list);

answer = new String[list.size()];
for(int i=0; i<list.size(); i++)
answer[i] = list.get(i).substring(1, list.get(i).length());



이렇게 풀이 했구요, 이 기회에 substring 과 다른 분이 풀이한 버블정렬도 공부를 해봐야 할것 같네요..

public String[] solution(String[] strings, int n) {
// strings range - 1 ~ 50
// strings element - 1 ~ 100

// == 버블정렬 ==
int range = strings.length - 1;
for(int i=0; i<range; i++) {
for(int j=0; j<(range)-i; j++) {
if(compareString(strings[j], strings[j+1], n, n)) {
swapString(strings, j, j+1);
}
}
}

return strings;
}
public boolean compareString(String a, String b, int n, int now) {
if(a.charAt(now) > b.charAt(now))
return true;
else if(a.charAt(now) == b.charAt(now)) {
int next = n == now ? 0 : ++now;
if(n == next) next++;
return compareString(a, b, n, next);
} else {
return false;
}
}
public void swapString(String[] strings, int a, int b) {
String temp = strings[a];
strings[a] = strings[b];
strings[b] = temp;
}

버블정렬은 1.~2ms정도 나오고 위에 arraylist로 풀이한 것은 20~30ms정도 나옵니다.


생각보다 차이를 보이네요...


오늘 공부를 통해 많이 배워갔으면 합니다.

반응형