99클럽(2기) - 코테스터디 29일차 TIL # Greedy # String

LeetCode - 2864. Maximum Odd Binary Number

You are given a binary string s that contains at least one '1'.

You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number that can be created from this combination.

Return a string representing the maximum odd binary number that can be created from the given combination.

Note that the resulting string can have leading zeros.

---

 

1. 풀이

 주어진 바이너리 s를 재배열하여 홀수인 최대값으로 만드는 문제이다. 바이너리가 홀수이려면 마지막 자리수가 1이어야 한다. 

 

1) s의 모든 char를 리스트에 넣은 후 1을 제거

1은 무조건 정답의 마지막 자리에 들어가야 하므로 1을 제외한 나머지 요소를 재배치하기 위해 s를 구성하는 각각의 문자를 리스트에 넣은 후 1을 제거한다. 

 

2) 리스트를 내림차순으로 정렬한다.

 1 하나를 제외한 요소들로 최대값을 만들어야 하기때문에 내림차순으로 정렬하여 1(들)이 맨 앞으로 오도록 한다. 예를 들어 stringList = [1, 0, 1, 0, 0] 일 때 내림차순 정렬 결과는 [1, 1, 0, 0, 0]이다.

 

3) 리스트의 요소들을 하나의 문자열로 병합

 StringBuilder를 사용해서 리스트의 모든 요소를 하나로 병합한다. String을 '+=' 로 연결하면 연산을 수행할 때마다 String 객체를 새로 생성하므로 내부적인 버퍼를 사용하는 StringBuilder를 통해 append 메소드로 문자열을 병합한다.

 

4) 병합된 문자열에 1을 추가해서 반환

 병합된 문자열에는 1이 빠져있으므로 마지막에 1을 추가해서 반환하면 끝!

 

import java.util.*; 

class Solution {
    public String maximumOddBinaryNumber(String s) {
        // s를 리스트에 넣은 후 마지막 자리에 들어갈 1을 제거한다
        List<String> stringList = new ArrayList<>(Arrays.asList(s.split("")));
        stringList.remove("1");
        
        // 내림차순으로 정렬
        Collections.sort(stringList, Collections.reverseOrder());
		
        // 리스트의 요소들을 하나의 문자열로 병합
        StringBuilder sb = new StringBuilder();
        for (String str: stringList) {
            sb.append(str);
        }
		
        // 마지막에 1을 붙여서 반환
        String result = sb.toString() + "1";
        return result;
    }
}

 

 

2. 새롭게 알게 된 점

• Arrays ↔ ArrayList 변환하는 방법
  • Array → ArrayList
    • Arrays.asList(array 객체)
      • 예시) List<Integer> list = new ArrayList<>(Arrays.toList(array객체));
  • ArrayList → Arrays
    • List.toArray(array 객체)
      • 예시) Integer[] array = list객체.toArray(new Integer[0]); // 생성자로 new Integer[0]를 전달하면 JVM에 의해 자동으로 list의 길이로 최적화된다.

 

• StringBuilder 이외에 String Arrays 또는 String ArrayList를 문자열로 병합하는 방법 (Java 8 이상)
  • String.join()
    • String.join("", list 객체)
    • String.join("", arrays 객체)
  • Collectors.joining()
    • Arrays.stream(array객체).collect(Collectors.joining());
    • list객체.stream().collect(Collectors.joining());

 

• StringBuilder로 문자열을 만든 후에는 꼭 toString 메서드를 호출해서 문자열 데이터로 사용될 수 있도록 해야한다.