한 번만 등장한 문자 - Java [프로그래머스 입문]

 

❤️ Problem

• 문제
  문자열 s가 매개변수로 주어집니다. s에서 한 번만 등장하는 문자를 사전 순으로 정렬한 문자열을 return 하도록 solution 함수를 완성해보세요. 한 번만 등장하는 문자가 없을 경우 빈 문자열을 return 합니다.

 

• 제한 사항
  • 0 < s의 길이 < 1,000
  • s는 소문자로만 이루어져 있습니다.

 

• 입출력 예 & 설명

no	s	result
1	"abcabcadc"	"d"
2	"abdc"	"abcd"
3	"hello"	"eho"

1. "abcabcadc"에서 하나만 등장하는 문자는 "d"입니다.
2. "abdc"에서 모든 문자가 한 번씩 등장하므로 사전 순으로 정렬한 "abcd"를 return 합니다.
3. "hello"에서 한 번씩 등장한 문자는 "heo"이고 이를 사전 순으로 정렬한 "eho"를 return 합니다.

 

 

---

 

💛 Solution

풀이

import java.util.ArrayList;
import java.util.Collections;
class Solution {
    public String solution(String s) {
        StringBuffer sb = new StringBuffer();
        String[] trans = s.split("");
        ArrayList<String> arr = new ArrayList<>();
        for (int i=0; i<trans.length; i++) {
            if(!arr.contains(trans[i])) {
                arr.add(trans[i]);
            }
        }
        Collections.sort(arr);
        for(int i=0; i<arr.size(); i++) {
            String tmp = arr.get(i);
            if(s.indexOf(tmp) == s.lastIndexOf(tmp)) {
                sb.append(tmp);
            }
        }
        return sb.toString();
    }
}

 

처리속도를 더 빠르게 할 수는 없을까?

 

 

---

 

💜 Comment

"한 번만 등장한다"라는 개념이 생각보다 코드 구현되는 게 어려웠던 문제. 나는 이 개념을 "여러 번 나타나는 문자열은 배제한다"라고 이해했다. 그렇다면 여러 번 나타나는 것은 어떻게 구현할 수 있을까?

코드를 짜다보면 생각보다 내가 사용하는 인간적인(?) 처리방식으로는 구현이 힘들 때가 많았다. 인간의 입장에서 "여러 번 등장하는 것"을 구분한다 치면 중복되는 문자열의 개수를 세면 그만인데, 이걸 프로그래밍하려니 뾰족한 수가 떠오르질 않았다😥

한참을 고민하다가 문득 든 생각이 "문자열에서 동일한 문자열이 여러 번 등장한다면, 첫 인덱스 번호와 마지막 인덱스 번호가 일치하지 않을 것 같다"는 것이었다.

1. 맨 처음 검사할 문자열을 배열로 쪼개둔 뒤, 검사 기준이 될 ArrayList에 중복없이 쪼개놓은 문자열 값을 넣는다.
2. ArrayList에 있는 문자열을 오름차순으로 정렬한다.
3. 검사할 문자열에서 ArrayList의 각 문자열이 등장하는 첫 인덱스 번호와 마지막 인덱스 번호를 대조하여 일치하는 경우에만 해당 ArrayList의 문자열 값을 StringBuffer에 삽입한다.

처리 속도는 생각하는 것만큼 빠르진 못했지만, 다른 답안하고 비교했을 때는 빠른 편에 속하므로 일단은 만족하기로 했다. 추후에 공부하면서 보완할 수 있는 부분은 보완하자!

오늘은 ArrayList의 정렬 메서드에 대해서 정리해보고자 한다.

 

---

🤍 Concept

 

ArrayList

• Collection Framework 중 하나 (java.util.ArrayList)
• List 인터페이스를 상속 받은 클래스 중 하나
• 동적 배열 → 크기가 고정되지 않음
• 배열에서 조작이 필요한 경우 유용
• 원시형 사용 불가

 

ArrayList 관련 메서드

• ArrayList 값 추가
  1) arrayList.add(VALUE);
  2) arrayList.add(INDEX, VALUE);
• ArrayList 값 수정 == arrayList.set(INDEX, VALUE);
• ArrayList 값 제거
  1) arrayList.remove(VALUE);
  2) arrayList.remove(INDEX);
• ArrayList 초기화 == arrayList.clear();
• ArrayList 값 출력 == arrayList.get(INDEX);
  → Iterator와 ListIterator를 사용하여 출력 가능

public static void main(String[] args) {
  ArrayList<String> numbers 
      = new ArrayList<>(Arrays.asList("one", "two", "three"));

      // 1. for-each + arrayList.get();
      for (String num : numbers) {
          System.out.print(num + " / ");
      }

      // 2. for + arrayList.get();
      for (int i = 0; i < numbers.size(); ++i) {
          System.out.print(numbers.get(i) + " / ");
      }

      // 3. Iterator
      Iterator<String> iterator = numbers.iterator();
      while (iterator.hasNext()) {
          System.out.print(iterator.next() + " / ");
      }

      // 4. ListIterator
      ListIterator<String> listIterator 
          = numbers.listIterator(numbers.size());
      while (listIterator.hasPrevious()) {
          System.out.print(listIterator.previous() + " / ");
      }  
}

 

• ArrayList가 비어있는지 체크 == arrayList.empty();
• ArrayList 특정 값이 있는지 체크
  1) arrayList.contains(VALUE); → True/False
  2) arrayList.indexOf(VALUE); → INDEX/-1
  3) arrayList.lasIndexOF(VALUE); → INDEX/-1

 

---

 

 

ArrayList 정렬 메서드

• Collections.sort();
  • 오름차순: 대문자 → 소문자 순으로 정렬된다
  • import java.util.Collections; 필요

public static void main(String[] args) {
        // ArrayList
        ArrayList<String> arr 
        	= new ArrayList<>(Arrays.asList("z", "A", "G", "d", "e"));
 
        // 오름차순 정렬
        Collections.sort(arr);
        System.out.println("오름차순 : " + arr); // [A, G, a, e, z]
 
        // 내림차순 정렬
        Collections.sort(arr, Collections.reverseOrder());
        System.out.println("내림차순 : " + arr); // [z, e, a, G, A]
 
        // 대소문자 구분하지 않는 오름차순
        Collections.sort(arr, String.CASE_INSENSITIVE_ORDER);
        System.out.println("대소문자 구분없이 오름차순 : " + arr); // [a, A, e, G, z]
 
        // 대소문자 구분하지 않는 내림차순
        Collections.sort(arr, Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));
        System.out.println("대소문자 구분없이 내림차순 : " + arr); // [z, G, e, a, A]
}

 

• List.sort();
  • 조건: Java 8 이상
  • sort()의 파라미터로 Comparator가 필요
    (import java.util.Comparator;)

public static void main(String[] args) {
        // ArrayList
        ArrayList<String> arr 
        	= new ArrayList<>(Arrays.asList("z", "A", "G", "d", "e"));
 
        // 오름차순 정렬
        arr.sort(Comparator.naturalOrder());
        System.out.println("오름차순 : " + arr); // [A, G, a, e, z]
 
        // 내림차순 정렬
        arr.sort(Comparator.reverseOrder());
        System.out.println("내림차순 : " + arr); // [z, e, a, G, A]
 
        // 대소문자 구분하지 않는 오름차순
        arr.sort(String.CASE_INSENSITIVE_ORDER);
        System.out.println("대소문자 구분없이 오름차순 : " + arr); // [a, A, e, G, z]
 
        // 대소문자 구분하지 않는 내림차순
        arr.sort(Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));
        System.out.println("대소문자 구분없이 내림차순 : " + arr); // [z, G, e, a, A]
}

 

---

 

Collections.sort() vs Arrays.sort() 차이점

• Arrays.sort()는 Dual-Pivot Quicksort를 사용
  (배열에서 주로 사용)
• Collections.sort()는 merge sort와 insert sort를 합친 timsort를 사용
• Quicksort는 배열에서 좋은 성능을 보이지만 stable하지 않음
• 따라서 stable이 필요한 Object에는 Collections.sort()를 많이 사용
• Arrays.sort는 인자의 타입이
  1) Primitive Type인 경우 DualPivotQuicksort.sort() 사용
  2) Object Type인 경우에는 TimSort.sort()가 사용

 

 

🔍 참고한 사이트
https://ttl-blog.tistory.com/148
https://brandpark.github.io/java/2021/01/05/arrays_sort1.html

[JAVA] List 정렬하기 (ArrayList, LinkedList 등)

[ JAVA ] Arrays.sort()의 내부 동작(1) - 자바니또의 Tech선물

 

 

 

🔍 <참고> 사용자가 직접 Comparable, Comparator 구현
https://ttl-blog.tistory.com/148
https://hianna.tistory.com/569

[JAVA] List 정렬하기 (ArrayList, LinkedList 등)

[Java] ArrayList 정렬하기 (오름차순, 내림차순, 사용자 정의)

 

 

 

🔍 <참고> Comparable과 Comparator 차이점
https://st-lab.tistory.com/243

자바 [JAVA] - Comparable 과 Comparator의 이해