[Study] 프로그래머스 lv.1 문자열 내 마음대로 정렬하기 ( 69% )

https://school.programmers.co.kr/learn/courses/30/lessons/12915

풀이 로직

1. Map으로 문자열, n번째 문자의 쌍을 만든다
2. value 값으로 오름차순 정렬, value가 같으면 key 값으로 오름차순 정렬한다.
3. key 값을 배열로 만들어 리턴한다.

실패한 코드

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public String[] solution(String[] strings, int n) {
        ArrayList<Character> charList = new ArrayList<Character>(); // char add를 위해 List 사용

        // String의 n번째 문자열을 List에 삽입
        for (String st : strings) {
            charList.add(st.charAt(n));
        }

        // List > Array 후 정렬
        char[] charArray = new char[charList.size()];
        charList.toArray(charArray);
        Arrays.sort(charArray);

        // 정렬된 charArray 기준으로 String 정렬하기
        String[] answer = new String[charList.size()];

        for (String st : strings){
            answer[charArray.indexOf(st.charAt(n))] = st;
        }

        return answer;
    }
}

1. ArrayList는 Character (래퍼 클래스)로 선언되어 있어서 언박싱을 해야 한다는 번거로움이 있다.
2. 선언하는 변수가 너무 많은 것 같다… 다른 방법을 써 보자

내가 작성한 코드

import java.util.*;

class Solution {
    public String[] solution(String[] strings, int n) {
        // Map으로 문자열, n번째 문자의 쌍을 만든다
        Map<String, Character> map = new HashMap<>();
        
        for(String st : strings){
            map.put(st, st.charAt(n));
        }

        List<String> keySet = new ArrayList<>(map.keySet());
        
        /*
        A.compareTo(B) : A < B 일 때 음수, A = B 일 때 0, A > B 일 때 양수 return
        문자열의 경우 A가 사전적으로 더 앞에 있는 값일 경우 음수 리턴
        */
        
        // value 값으로 오름차순 정렬, value가 같으면 key 값으로 오름차순 정렬
        
        keySet.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) { // o1은 앞의 String, o2는 뒤의 String
                if(map.get(o1).compareTo(map.get(o2)) == 0){ // char 값이 동일할 경우 
                    return o1.compareTo(o2); // key값끼리 비교하여 return
                }else{ // 아닐 경우
                    return map.get(o1).compareTo(map.get(o2));
                }
            }
        });        
        
        // key 값을 배열로 만들어 리턴
        String[] answer = keySet.toArray(new String[map.size()]);
        
        return answer;
    }
}

실행 시간

0.48ms ~ 0.89ms

테스트 1 〉	통과 (0.56ms, 72.6MB)
테스트 2 〉	통과 (0.83ms, 74.5MB)
테스트 3 〉	통과 (0.75ms, 74.5MB)
테스트 4 〉	통과 (0.67ms, 76.4MB)
테스트 5 〉	통과 (0.55ms, 76.7MB)
테스트 6 〉	통과 (0.79ms, 72MB)
테스트 7 〉	통과 (0.75ms, 79.6MB)
테스트 8 〉	통과 (0.67ms, 75.6MB)
테스트 9 〉	통과 (0.48ms, 78MB)
테스트 10 〉	통과 (0.89ms, 76.5MB)
테스트 11 〉	통과 (0.48ms, 76.9MB)
테스트 12 〉	통과 (0.72ms, 78.4MB)

새로 배운 문법

        // value 값으로 오름차순 정렬, value가 같으면 key 값으로 오름차순 정렬
        
        keySet.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) { // o1은 앞의 String, o2는 뒤의 String
                if(map.get(o1).compareTo(map.get(o2)) == 0){ // char 값이 동일할 경우 
                    return o1.compareTo(o2); // key값끼리 비교하여 return
                }else{ // 아닐 경우
                    return map.get(o1).compareTo(map.get(o2));
                }
            }
        });      

sort()

참조

void sort(Comparator<? super E> c);

• Comparator는 두 객체를 비교하기 위한 인터페이스입니다.
• <? super E>는 Comparator의 형식 매개변수입니다. E는 리스트의 요소 타입을 나타냅니다.

즉, sort() 메서드는 Comparator를 인자로 받아 리스트의 요소들을 정렬하는데 사용됩니다. 이때, Comparator 인터페이스를 구현하는 익명 클래스를 생성하여 sort() 메서드에 전달하는 것이 가능합니다.

Comparator

상세 내용 블로그 (설명 잘 되어 있으니 꼭 읽어 보는 것을 추천!)

Comparator은 인터페이스로, 내부에 있는 함수를 메소드를 구현해서 사용해야 한다.

여기서 사용한 메소드는 compare(T o1, T o2) 이다.

이때 선행 원소 (앞서 들어온 값) = o1 후행 원소 (뒤에 들어온 값) = o2

앞서 말한대로 interface 이기 때문에 특정 class 에서 상속 받아 사용할 수도 있다.

import java.util.Comparator;	// import 필요
class Student implements Comparator<Student> {
 
	int age;			// 나이
	int classNumber;	// 학급
	
	Student(int age, int classNumber) {
		this.age = age;
		this.classNumber = classNumber;
	}
	
	@Override
	public int compare(Student o1, Student o2) {
 
		/*
		 * 만약 o1의 classNumber가 o2의 classNumber보다 크다면 양수가 반환 될 것이고,
		 * 같다면 0을, 작다면 음수를 반환할 것이다.
		 */
		return o1.classNumber - o2.classNumber;
	}
}

이렇게 작성하면 main에서 compare 함수를 호출하여 객체를 비교할 수 있다.

Student a = new Student(17,2);
Student b = new Student(18,1);
Student c = new Student(15,3);

int isBig = c.compare(a,b); // a 객체와는 상관 없이 b / c 객체를 비교한다.

익명 클래스

참조

이름이 없는 클래스로, 클래스를 정의하면서 동시에 객체를 생성한다.

이전 강의에서 우리가 return new postService.getPosts(); 했던 것처럼!

new 키워드를 사용하여 익명 클래스를 만들고, 인터페이스나 추상 클래스를 구현하거나 확장할 수 있다.

A.compareTo(B)

참조 1 / 참조 2

return 값	음수	0	양수
문자열	A가 사전적으로 앞에 위치	A = B	A가 사전적으로 뒤에 위치
숫자 문자열	A < B	A = B	A > B

비교 대상 문자열의 각 문자 들을 첫 번째 자리부터 비교하다가, 가장 먼저 만나는 서로 다른 문자들의 ASCII 값 차이를 반환 후 더 이상 비교하지 않는다.

다른 사람의 풀이 - ArrayList를 통한 정렬

import java.util.*;

class Solution {
    public String[] solution(String[] strings, int n) {
        String[] answer = {};

			// n번째 문자를 맨 앞에 붙인 문자열을 만들어 List로 만든다
        ArrayList<String> arr = new ArrayList<>();
        for (int i = 0; i < strings.length; i++) {
            arr.add("" + strings[i].charAt(n) + strings[i]);
        }

			// 정렬
        Collections.sort(arr);
        
			// 원래의 문자열만 떼어내서 답을 return 
				answer = new String[arr.size()];
        for (int i = 0; i < arr.size(); i++) {
            answer[i] = arr.get(i).substring(1, arr.get(i).length());
        }
        return answer;
    }
}

다른 사람의 풀이 - compare 함수를 통한 정렬

import java.util.*;

class Solution {
  public String[] solution(String[] strings, int n) {
      Arrays.sort(strings, new Comparator<String>(){
          @Override
          public int compare(String s1, String s2){
              if(s1.charAt(n) > s2.charAt(n)) return 1;
              else if(s1.charAt(n) == s2.charAt(n)) return s1.compareTo(s2);
              else if(s1.charAt(n) < s2.charAt(n)) return -1;
              else return 0;
          }
      });
      return strings;
  }
}

compare 함수를 오버라이드 하여 n번째 문자로 재정의 하는 방식을 사용했다.