[JAVA] 프로그래머스 | 181913 문자열 여러 번 뒤집기

 

 

📝 TIL

- [프로그래머스] 181913 문자열 여러 번 뒤집기

 

제한사항

my_string은 영소문자로만 이루어져 있습니다.

1 ≤ my_string의 길이 ≤ 1,000

queries의 원소는 [s, e]의 형태로 0 ≤ s ≤ e < my_string의 길이를 만족합니다.

1 ≤ queries의 길이 ≤ 1,000

 

 

입출력 예

입출력 예#1

my_string	queries	result
"rermgorpsam"	[[2,3], [0,7], [5,9], [6,10]]	"programmers"

 

---

🦔 설계 및 시도

 

처음에 투포인터를 사용해야 되는 거 아닌가 생각했다가

문법의 미숙함으로 구현이 어려울 거 같아서 인덱스로 문제를 해결했다

 

이렇게 구간을 나눠서

 

1. 0~queries[i][0]

2. queries[i][0]~queries[i][1]

3. queries[i][1]~length

 

세 구간으로 나눠 2번 구간을 뒤집는 for문을 사용, 이중 for문으로 문제를 해결했다

for문을 하나를 

 

 

 

[내가 푼 풀이]

시간복잡도 : O(n*m) / 쿼리 m

class Solution {
    public String solution(String my_string, int[][] queries) {
        String answer = my_string;
        
        for(int i=0; i<queries.length; i++){
            StringBuilder sb = new StringBuilder();
            for(int j=0; j<queries[i][0]; j++){
                sb.append(answer.charAt(j));
            }
            
            for(int j=queries[i][1]; j>=queries[i][0]; j--){
                sb.append(answer.charAt(j));
            }
            
            for(int j=queries[i][1]+1; j<my_string.length(); j++){
                sb.append(answer.charAt(j));
            }
            answer = sb.toString();
        }
        return answer;
    }
}

 

 

좀 더 풀이를 개선하기 위해 투 포인터 방식으로도 찾아봤다.

 

 

🔥 풀이에 사용된 개념

Two Pointer(투 포인터)

양 끝에서 가운데로 접근

 

toCharArray()

문자열을 문자 배열로 변환

 

StringBuilder

StringBuilder sb = new StringBuilder();

가변적인 String으로 문자열이 많이 변하는 문제에서는 StringBuilder가 효율적

- 문자열 여러번 덧붙이기

- 문자열 중간 삽입 삭제

 

---

 

💡 풀이 소스 코드

 

StringBuilder를 사용해도 되지만, 위 풀이처럼 사용하면,

매 쿼리마다 문자열 전체를 매번 새로 만들어야 해서 쿼리가 많아지면 느려짐

 

따라서 문자열을 char[] 로 문자 배열로 바구고

쿼리마다 해당 부분만 in-place로 swap 한다!

 

 

시간복잡도 : O(n+m)

공간복잡도 : O(n)

 

class Solution {
    public String solution(String my_string, int[][] queries) {
        char[] arr = my_string.toCharArray();
        
        for(int[] q : queries) {
            int start = q[0];
            int end = q[1];
            
            while(start<end) {
                char tmp = arr[start];
                arr[start] = arr[end];
                arr[end] = tmp;
                
                start++;
                end--;
            }
        }
        
        return new String(arr);
    }
}

 

---

🚀 새로 배운 내용

- StringBuilder는 문자열 조합/ 생성이 반복될 때 좋지만, 매번 만들기엔 시간 손해가 있다

- char[]로 직접 수정하는 방식과 투 포인터 방식도 항상 고려하

 

 

---

😺  느낀점

- 적합한 방법이 생각나지 않으면 느린 방법이라도 해결해보려고 노력하자

 

 

*소스 코드는 다음 깃허브에 올라옵니다 - https://github.com/s0ooo0k/Algorithm_Study

GitHub - s0ooo0k/Algorithm_Study: Algorithm Study 문제 및 풀이