[boj] 17413. 단어 뒤집기 2

[boj] 17413. 단어 뒤집기 2

• 문제 링크 : https://www.acmicpc.net/problem/17413
• 사용 언어 : Node.js

17413번: 단어 뒤집기 2

문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.

먼저, 문자열 S는 아래와 같은 규칙을 지킨다.

1. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('<', '>')로만 이루어져 있다.
2. 문자열의 시작과 끝은 공백이 아니다.
3. '<'와 '>'가 문자열에 있는 경우 번갈아가면서 등장하며, '<'이 먼저 등장한다. 또, 두 문자의 개수는 같다.

태그는 '<'로 시작해서 '>'로 끝나는 길이가 3 이상인 부분 문자열이고, '<'와 '>' 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.

---

 

1. 문제 분석

주어진 문자열에 대하여 태그 안에 위치하는 단어는 변화 없이, 태그 바깥에 위치하는 단어는 뒤집어 출력하는 문제입니다.
역순으로 출력 => LIFO (Last In First Out) 스택 자료구조를 활용하면 되겠습니다.
단어가 종료되는 공백, '<', 문장의 끝을 유의해서 스택 내부의 문자를 역순으로 출력해주도록 합니다.

 

---

 

2. 솔루션

const fs = require('fs')
const testString = fs.readFileSync(process.platform ===
                                   'linux' ? '/dev/stdin' : 'input.txt')
                     .toString().trim()
const sArr = [...testString]
const stack = []
// 현재 문자가 Tag 내부의 문자인지 표현하는 Flag
let isTag = false
let answer = ''
for (let i = 0; i < sArr.length; i++) {
    const char = sArr[i]
    // Tag의 시작
    if (char === '<') {
        isTag = true
        // Tag 시작 시 Stack 내의 문자열 출력
        while(stack.length !== 0) {
            answer += stack.pop()
        }
        answer += char
        // Tag의 종료
    } else if (char === '>') {
        isTag = false
        answer += char
    } else {
        // 현재 Tag 내부 이면 일반 출력
        if (isTag) {
            answer += char
        } else {
            // 공백을 만나면 단어의 끝이므로 Stack 내부에 있는 문자열 출력
            if (char === ' ') {
                while (stack.length !== 0) {
                    answer += stack.pop()
                }
                answer += char
            } else {
                // Tag 바깥이므로 역순 출력 위해 Stack에 저장
                stack.push(char)
            }
        }

    }
}

// 테스트 케이스 풀이 제출 이전 Stack 내 남아있는 문자열 출력
while(stack.length !== 0) {
    answer += stack.pop()
}


console.log(answer)

 

---

마치며

문자열 뒤집기 문제의 경우 대부분이 스택 자료형을 사용하는 문제이기에 기억해 두도록 합시다.