Maximize The Number 문제의 자바 해결 방법: 효율적인 알고리즘

문제

Problem_Link

문제해결방법

• 목표: 가장 뒤에 있는 1과 가장 앞에 있는 0을 서로 교환한다.
• 조건: 교환 횟수가 주어진 k보다 적어야 한다.
• StringBuilder를 써야 함: 스트링을 교환해야하므로, 가장 효율적인 방법이 StringBuilder.
• 가장 뒤쪽에 있는 1은 반드시 k보다 횟수가 적을때만 필요함
• 반복문이 끝나는 조건은
  1. 교환횟수가 k보다 큼
  2. 주어진 길이만큼 반복을 했을경우.

그러므로, 두개의 포인터가 사용됨.

첫번째 포인터(i)는 반복해서 돌면서 0을 찾고, 두번쨰 포인터(lastOneIndex) 는 가장 뒤에 있는 1을 찾음.

두 포인터가 다 찾았다면 이를 교환하는데, 이 교환횟수가 K릏 넘는다면 반복을 중지함.

시간복잡도: O(n), 공간복잡도: O(n)

class Solution {
    public static String maximumNumber(String S, int K) {
        // 문자열 S를 StringBuilder로 변환하여 수정 작업이 용이하도록 함
        StringBuilder sb = new StringBuilder(S);
        int n = S.length(); // 문자열의 길이
        int lastOneIndex = n - 1; // 가장 뒤쪽에 있는 1의 인덱스를 저장할 변수
        int counter = 0; // 교환한 횟수를 저장할 변수

        // 가장 뒤쪽에 있는 1의 인덱스를 찾음
				// 위의 인덱스는 i보다 커야하고, 교환한 횟수가 K보다 적어야 함.
        for (int i = 0; i < n && counter < K; i++) {
            while (lastOneIndex > i && sb.charAt(lastOneIndex) == '0') {
                lastOneIndex--;
            }

            // 현재 자리가 0이고 가장 뒤쪽에 있는 1이 현재 자리보다 뒤에 있을 경우 교환
            if (sb.charAt(i) == '0' && lastOneIndex > i) {
                sb.setCharAt(i, '1'); // 현재 자리의 0을 1로 변경
                sb.setCharAt(lastOneIndex, '0'); // 가장 뒤쪽에 있는 1의 자리를 0으로 변경
                counter++; // 교환 횟수 증가
            }
        }

        // 변경된 문자열 반환
        return sb.toString();
    }
}