리트코드 - 151. Reverse Words in a String

리트코드 - 151. Reverse Words in a String

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

 

문제 설명

입력 문자열 s가 주어질 때, 단어의 순서를 역순으로 바꿔라.
단어는 비공백 문자열 시퀀스로 정의된다. s의 단어들은 최소한 하나의 공백으로 구분된다.
공백 하나로 연결된 역순으로 나열된 단어를 문자열로 리턴하라.
s는 앞이나 뒤에 공백이나 두 단어 사이에 공백이 여러 개 포함될 수 있다는 점에 주의하라. 반환된 문자열에 단어를 구분하는 공백은 하나만 있어야 하고, 추가 공백이 있어서는 안 된다.

 

의사코드

words = s.split(" ") result = ""; 반복문 시작 (words 배열 거꾸로 하나씩)     if (word[i].equals(""))         result.append(word).append(" "); 반복문 종료 result.toString().trim() 리턴

 

풀이코드

class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder result = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            if (words[i].equals("")) {
                continue;
            }
            result.append(words[i]).append(" ");
        }
        return result.toString().trim();
    }
}

 

코드설명

단어가 주어지면 띄어쓰기를 제거 후 ,다시 마지막 단어에서 처음 단어까지 띄어쓰기를 하나만 포함해 출력하는 문제이다.

먼저 String에서 제공하는 split을 사용하면 단어 단위로 배열에 저장할 수 있다.

 

문제는 공백이 여러개가 붙어있는 경우 공백도 배열에 저장이 된다는 점이다.

따라서 이 공백일 때를 제외하기 위해 if문에서 공백일 경우는 건너뛰어주면 된다.

 

이외의 경우는 result에 추가해주고, 스페이스도 추가해준다.

이렇게 하면 모든 단어가 result에 연결되는데 마지막 배열에 띄어쓰기가 포함된다.

따라서 result.toString() 한 값에 trim()을 해주면 된다.

 

if문을 사용하고 싶지 않으면 s.split(); 부분에 "\\s+" 정규식을 전달해주면 조금 더간단한 코드가 된다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

문제를 풀면서 이게 왜 medium 난이도인지 모르겠다고 느꼈다.

코테를 보며 java에서 제공하는 기본 메소드들은 활용하는 것이 맞지만 순수하게 사용하는 법도 알아두면 좋아야 한다고 생각한다.

그런 점에 아래 다른사람의 코드를 보고 왜 medium 난이도 인지 알게되었다.

 

public class Solution {
    public String reverseWords(String s) {   
        int currentIndex = s.length() - 1;
        StringBuilder reversedWords = new StringBuilder();

        while (currentIndex >= 0) {
            int wordLength = 0;

            while (currentIndex >= 0 && s.charAt(currentIndex) != ' ') {
                wordLength++;
                currentIndex--;
            }

            if (wordLength > 0) {
                int wordStartIndex = currentIndex + 1;
                int wordEndIndex = currentIndex + wordLength;
                reversedWords.append(s, wordStartIndex, wordEndIndex + 1);
                reversedWords.append(' ');
            } else {
                currentIndex--; 
            }
        }
        
        return reversedWords.toString().trim();
    }
}

 

이 풀이에서는 String 배열을 사용하고 있지 않다. toCharArray를 통한 배열도 사용하고 있지 않다.

while문이 중첩되어 있긴 하지만 O(n) 시간만큼만 사용하고 있다.

 

내 풀이는 5ms인데 이 풀이는 3ms 로 런타임이 줄었다.

두번째 while문에서 charAt이 currentIndex에 종속적이란 것만 빼면 괜찮은 코드 같다.

 

정리

배열에 공백과 단어가 주어질 때 역순으로 단어를 출력하는 방법