[LeetCode] 151. Reverse Words in a String

문제 출처: https://leetcode.com/problems/reverse-words-in-a-string/

Reverse Words in a String - LeetCode

---

문제

입력 문자열 s가 주어지면, 단어의 순서를 반대로 정렬하라.

 

단어란, 공백 없는 문자의 시퀀스로 정의한다. s 내의 단어는 최소 한 개의 공백으로 구분되어 있다.

 

단어들의 순서를 뒤집어 단일 공백으로 연결한 문자열을 반환하라.

 

주의: 문자열 s는 공백으로 시작하거나 끝날 수 있으며, 두 단어 사이에 다중 공백이 존재할 수 있다. 반환된 문자열은 단어들이 단일 공백으로 구분되어 있어야 한다. 어떠한 추가적인 공백을 넣지 마시오.

예제

Input: s = "the sky is blue"
Output: "blue is sky the"

Input: s = "  Bob    Loves  Alice   "
Output: "Alice Loves Bob"

---

풀이

언어에서 문자열에 대해서 제공하는 내장 함수를 사용하지 않는 방법으로 문제를 해결하려고 하였습니다.

 

1차적으로 주어진 s 에 대해서 단어들을 분리하는 과정이 필요합니다. 문제에서 언급되었듯이 각 단어는 한 개 이상의 공백 문자로 구분되기 때문에 이를 통해서 각 단어를 분리할 수 있습니다. 이 과정에서 추출되는 각 단어들은 스택 자료구조에 저장합니다.

function splitWords(s) {
    const words = [];
    
    let word = '';
    for (let i = 0; i < s.length; i++) {
    	if (s[i] === ' ') {
            if (word) {
            	words.push(word);
            	word = '';
            }
            continue;
        }
        word += s[i];
    }
    if (word) { words.push(word); }
    
    return words;
}

방식은 간단합니다. 반복문을 통해 s의 각 문자에 접근합니다. 접근한 문자가 공백이 아니라면, 단어를 만들어 갑니다. 만약 공백이라면, 이전까지 만들어 놓은 단어를 저장하고 새로운 단어를 만들기 위해 초기화를 진행합니다. 이때 공백이 연속해서 나올 수 있기 때문에 만들어 놓은 단어를 체크하는 과정이 필요합니다.

 

위와 같은 방식으로 문자열 s로부터 각 단어를 추출했다면, 남은 과정은 스택에서 각 단어들을 빼내어 하나의 공백으로 엮는 일입니다. 스택 자료구조의 특징으로 인해 마지막에 삽입된 단어부터 순차적으로 추출될 것입니다.

var reverseWords = function(s) {
    let answer = '';
    
    const words = splitWords(s);
    while (words.length) {
    	answer += words.pop() + (words.length ? ' ' : '');
    }
    
    return answer;
}

 

Github: 151.js

GitHub - opwe37/Algorithm-Study