942. DI String Match

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

문제 출처

[문제 설명]

n+1 크기의 배열이 있을 때, 배열의 각각의 요소는 0부터 n까지 유일하게 있습니다.

예 ) 크기 5(n+1)인 배열 -> 0,1,2,3,4, or 2,3,1,4,0 or 3,4,2,1,0 등등

문자열 s를 줬을 때 s에 i번째 문자가 I면 배열에 (i+1)번째가 i번째보다 큽니다.

D면 배열에 i번째가 i+1번째보다 큽니다.

가능한 녀석을 리턴하세요.

[처음 생각한 접근 방법]

I면 뒤에 요소의 값은 앞에 요소 +1

D면 뒤에 요소의 값은 앞에 요소 -1

이런 식으로 할려고했는데 안됐다. 그래서 생각을 바꿔봤다.

어차피 0~최대값까지는 무조건 나오니까 문자에서 I가 나오면 그 자리의 수는 최소, D가 나오면 그 자리의 수는 최대가 되게 한다.

IDID이면

첫번째가 I이므로 첫번째 값은 최소 0이 된다. 0은 이제 나왔으므로 모든 배열의 요소는 유일해야 하니 +1을 해준다.(두번째 최소값)

두번째가 D이므로 두번째 값은 최대인 3이 된다. 3은 이제 나왔으므로 모든 배열의 요소는 유일해야 하니 -1을 해준다.(두번째 최대값)

세번째 I -> 1

네번째 D -> 2

IDID -> 0312

class Solution {
    public int[] diStringMatch(String s) {
        int[] answer = new int[s.length()+1];
        int min = 0;
        int max = answer.length - 1;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'I') answer[i] = min++;
            else answer[i] = max--;
        }

        if (s.charAt(s.length()-1) == 'I') answer[answer.length-1] = max;
        else answer[answer.length-1] = min;

        return answer;
    }
}

시간복잡도는 for문 하나가 s.length()만큼 돌기 때문에 O(n)

공간복잡도는 정답으로 반환할 answer배열이므로 O(n)인듯하다. 틀리면 지적 좀.

 

[리트코드 답안]

   public int[] diStringMatch(String S) {
        int n = S.length(), left = 0, right = n;
        int[] res = new int[n + 1];
        for (int i = 0; i < n; ++i)
            res[i] = S.charAt(i) == 'I' ? left++ : right--;
        res[n] = left;
        return res;
    }

삼항연산자를 사용했다는 점.

그리고 마지막에 최소값(left)과 최대값(right)이 같아지는 것을 이용하여, for문 다음에 나오는 if else문을 제거했다.

알고리즘을 볼 때마다, 삼항 연산자만큼 깔끔한 처리가 없는 거 같다.

 

[내 답안 수정하기]

 

class Solution {
    public int[] diStringMatch(String s) {
        int[] answer = new int[s.length()+1];
        int min = 0;
        int max = answer.length - 1;
        
        for (int i = 0; i < s.length(); i++) {
            answer[i] = s.charAt(i) == 'I' ? min++ : max--;
        }
        
        answer[answer.length-1] = min;
        return answer;
    }
}