[Leetcode] 151. Reverse Words in a String - JS

https://leetcode.com/problems/reverse-words-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- 문자열 s를 주면 단어를 역순으로 하여 반환하라.
- s는 적어도 하나의 공백으로 구분되어 있다.
- s는 앞쪽, 혹은 뒤쪽에 공백과 문자 사이의 다수의 공백이 존재할 수 있다.
- 반환되는 문자열은 문자 사이의 공백은 1개만으로 구분되어야 하며 다른 공백은 포함하면 안된다.

제한조건
--------------------
- 1 <= s.length <= 10^4
- s는 대소문자 영어와 숫자, 공백으로 구성되어이 있다.
- s에는 적어도 1개의 단어가 있다.

 

2. 접근 방법

접근방법
--------------------
1. 앞뒤 공백을 제거한다. trim
2. 뒤쪽에서 순회하면서
문자열이면 subStr에 추가한다.
공백이면 공백 flag를 수정하고 subStr을 역순으로하여 res에 추가한다.
문자열이 다시 등장할 때, 공백 flag가 true면 res에 공백을 추가한다.

 

 

3. 코드

var reverseWords = function(s) {
    s = s.trim();
    let res = '';
    let subStr = ''
    let isSpace = false;
    for (let i = s.length - 1; i >= 0; i--) {
        let letter = s[i];
        if (letter !== ' ') {
            if (isSpace) {
                res += ' '
            }
            subStr += letter
            isSpace = false;
        } else {
            isSpace = true;
            res += [...subStr].reverse().join('');
            subStr = ''
        }
    }
    res += [...subStr].reverse().join('');
    return res;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

제자리에서 결과값으로 변환하는 방법으로 공간복잡도를 O(1)으로 풀어보기에 도전했다. 뭔가 flag 방식을 자주 사용하는데 이 방식으로 하면 코드가 복잡해보인다. 컴퓨터적 사고로 푼다기 보단 인간적 사고로 푸는 방법에 가깝다.

flag를 사용하지 않고 푸는 방법을 고민해봐야겠다.

 

 

5.  flag 없이 풀이 (정규표현식)

flag를 사용한 이유는 단어 사이의 여러 공백이 있기 때문이다.

단어 사이의 여러 공백이 등장하면 공백일 때 결과값에 더해주는 로직에 조건이 추가되어야 하므로 복잡해진다.

 

즉, 주요 로직을 진행하기 전에 여러 공백을 제거하는 방법을 찾아보았다.

 

여러 공백을 제거하는 간단한 방법으로는 정규표현식을 사용하는 것이다.

 

\ +\

위 정규표현식에서 ' ' 공백 뒤에 '+'가 붙게되면 앞의 표현식이 1회 이상 반복되는 것을 의미한다.

이를 활용하여 1개 이상의 모든 공백을 1개의 공백으로 치환한다.

 

var reverseWords = function(s) {
    s = s.trim();
    s = s.replace(/ +/g, ' ')
    let res = ''
    let word = ''
    for (let i = s.length - 1; i >= 0; i--) {
        let chr = s[i];
        if (chr !== ' ') {
            word += chr;
        } else {
            res += reversed(word) + ' ';
            word = ''
        }
    }
    res += reversed(word)
    return res
};

function reversed(word) {
    return [...word].reverse().join('')
}

 

추가로 공백이 아닐 때 저장해둔 단어를 역순으로 바꾸는 과정이 복잡해보여 함수로 빼내었다.