#14 알고리즘 연습 - 문자열 마음대로 정렬하기

2019년 2월 12일 화요일

#14 알고리즘 연습 - 문자열 마음대로 정렬하기 - JAVA

문자열 내마음대로 정렬하기

문제 설명

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

제한 조건

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

입출력 예

strings	n	return
[sun, bed, car]	1	[car, bed, sun]
[abce, abcd, cdx]	2	[abcd, abce, cdx]

입출력 예 설명

입출력 예 1
sun, bed, car의 1번째 인덱스 값은 각각 u, e, a 입니다. 이를 기준으로 strings를 정렬하면 [car, bed, sun] 입니다.

입출력 예 2
abce와 abcd, cdx의 2번째 인덱스 값은 c, c, x입니다. 따라서 정렬 후에는 cdx가 가장 뒤에 위치합니다. abce와 abcd는 사전순으로 정렬하면 abcd가 우선하므로, 답은 [abcd, abce, cdx] 입니다.

문제풀이 IDEA

문제에서는 n번째 인덱스를 기준으로 sort를 해줘야 한다. 따라서 기존에 sort를 이용하기 위해서는 n번째를 뽑아와서 sorting을 하면 되는데 이때 주의 해야할것이 문제를 보면

n번째를 비교후 n번째가 같으면 0번째 index부터 비교하여 사전식으로 정렬을 해주게 된다
따라서 정렬의 기준에 따라 n번째 char + 0번째 ~ n-1번째 char 로 이루어진 새로운 문자열을 담고 있는 temp list를 만들어서 sorting해준다

그리고 정렬된 temp 문자열과 map을 대응시키며 answer list에 추가해준다

이때 새로운 문자열을 만들면 기존의 문자열과 대응하여 기존의 문자열을 출력해줘야 하므로 Map의 key에 새로운 문자열 value에 기존의 문자열을 넣어준다

나의 코드 ⭐

import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;

class Solution {
  public String[] solution(String[] strings, int n) {
      String[] answer = new String[strings.length];       //answer의 크기는 입력받은 string의 크기와 같다.
      String[] temp = new String[strings.length];        //정렬에 쓰기위한 temp의 크기도 입력받은 string의 크기와 같다.
      Map<String, String> map = new HashMap<String, String>();   //Map을 사용하여 key와 value를 이용한 대응을 사용한다

      for (int i = 0; i<strings.length;i++){                  
        map.put(strings[i].substring(n,n+1)+ strings[i].substring(0,n)+ strings[i].substring(n+1), strings[i]);

                //코드가 길어 지저분한데 string list의 원소들의 n번째 char를 가져오고 다음 비교대상인 index 0~ n-1까지

                  String을 가져와서 새로운 string을 만들어 map의 key값으로 넣어준다.

                  map의 value값으로는 가공하지 않은 원래 string의 원소들을 넣어주자

                  (물론 이때도 n번째 char + string[i] 를 해주게 되면 같은 비교기준을 가진 정렬이 출력된다)

        temp[i] = strings[i].substring(n,n+1)+ strings[i].substring(0,n)+ strings[i].substring(n+1);

                // map의 key값을 정렬할수 없으므로 정렬을 위한 temp array에도 조작한 string을 넣어주자

       } 
      Arrays.sort(temp);          //temp를 정렬하여 우리가 원하는 순서대로 정렬되도록 한다

      for (int i = 0; i<strings.length;i++){
           answer[i] = map.get(temp[i]);       // 정렬된 temp의 원소들을 순서대로 가져와 해당 key에 대응되는 원래의

                                                  value값들을 answer array에 넣어준다
      } 
      return answer;
  }
}

다른 코드 ⭐

import java.util.*;

class Solution {
    public String[] solution(String[] strings, int n) {
        String[] answer = new String[strings.length];
        ArrayList<String> arr = new ArrayList<>();     //ArrayList를 이용해 동적으로 elements를 추가할수 있게 해줬다.
        for (int i = 0; i < strings.length; i++) {
            arr.add(strings[i].charAt(n) + strings[i]);  //ArrayList에 비교 되상이 되는 n번째 char와 기존의 element를 더한 string을 넣는다 
        }
        Collections.sort(arr);                           //ArrayList를 사용했기때문에 Collections의 sort를 가져와 정렬해줬다.

 for (int i = 0; i < arr.size(); i++) {
            answer[i] = arr.get(i).substring(1);
        }                                       //이부분이 중요한데 answer array에 정렬된 ArrayList의 1번째 index부터 마지막까지의 substring을

        return answer;                            가져온다  이 substring은 본래의 strings의 element와 완전히 일치하게 된다.
    }
}

알고 넘어 갈것

내가 해준 방법은 다소 temp를 1개 더 만들고 Map도 만들어야 하고 절차가 복잡했는데
ArrayList를 안 쓴이유가

n번째 char를 기준으로 비교하고 본래의 string을 가져올수 있을까 라는 생각에서 였다

따라서 이 방법은 substring을 최대치로 활용할수 있는 방법이였다.

뿐만아니라 String내의 char를 가져옴에 있어서도 나는 substring을 사용한 반면
다른 코드에서는 charAt을 사용하여 보다 깔끔하고 보기 좋게 사용해주었다.

대신 import java.util.*는 귀찮아서 그런것 같지만 이러한 import는 좋지 못한 임포트가 될것 같다.

출처: 프로그래머스

벽에그린나의키

2019년 2월 12일 화요일