[JAVA] 백준 | 17413 단어뒤집기 2

📝 TIL

- [백준] 17413 단어뒤집기 2

 

제한사항

시간제한 1초

메모리 제한 512MB

 

입출력 예

입출력예 #1

# 처리된 내용이 출력!

baekjoon online judge // noojkeab enilno egduj 
<open>tag<close> // <open>gat<close>
<ab cd>ef gh<ij kl> // <ab cd>fe hg<ij kl>
<problem>17413<is hardest>problem ever<end> // <problem>31471<is hardest>melborp reve<end>

 

 

---

🦔 설계 및 시도

문자열이 주어질 때 < > 안(태그)은 그대로 출력,

태그 밖의 단어는 공백 단위로 뒤집어 출력한다.

 

문제를 풀기 위한 구상 ...

 

(1차) 단순하게(사실 이것도 복잡하다고 생각했지만 <, ' '가 들어오면 뒤집어서 출력, >가 들어오면 그대로 출력

을 생각했으나 태그 안의 공백은 무시하고 그대로 출력되어야 한다.

 

(2차) tag=0으로 초기화하여, < 가 들어오면 태그를 1로 바꾸어주고 tag가 1일 때는 공백이 들어와도 그대로 유지

> 가 들어오면 그대로 출력하고 tag는 다시 0으로

를 생각했었는데, 계속 < 여는 괄호가 잘못 출력이 되었다.

 

deque를 사용했는데 deque를 최대한 활용하고 싶어

pollLast, removeFirst를 계속 반복해서 쓰다가 계속 스택을 비우는 과정에서 오류가 발생하여,

2차 과정에서 시간을 엄청 쏟다 다시 처음부터 구상했다.

 

(3차) tag=1, 즉 < 괄호 안일 때는 그냥 바로 stringbuilder에 추가해주고,

닫는 괄호가 나오고, tag가 0이면 deque에 넣다가 출력하는 형태로 작성했다.

 

tag를 체크하는 것을 모드처럼 이해하고, deque를 씀에도

그냥 stack으로 생각하면 조금 더 접근이 쉬웠을 거 같다.

 

요약하자면,

 

 

1. 문자열 처음부터 끝까지 돌면서

2. 태그 시작('<')이 나오면 deque에 쌓인 문자를 뒤집어서 출력하고, tag=1로 전환

3. 태그 끝('>')이 나올 때까지 stringbuilder에 그냥 넣다가, >을 만나면 tag=0

4. tag=0일 때는 deque에 넣고, tag=1일 때는 sb에 넣는다.

5. 공백을 만나면 deque를 뒤집어서 출력하기.

이때 tag를 체크 안해도 되는 이유는 어차피 tag=1일 때는 sb에 바로 넣기 때문에 dq가 비어있다

6. 마지막에 남은 단어 처리하기 위해서 추가로 뒤집어서 출력하기

 

 

 

 

 

💡 풀이 소스 코드

 

시간복잡도 : O(n)

공간복잡도 : O(n)

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine(); 
        System.out.println(solution(str));
    }

    public static String solution(String str) {
        StringBuilder sb = new StringBuilder();
        Deque<Character> dq = new ArrayDeque<>();
        int tag = 0;

        for (int i = 0; i < str.length(); i++) {
            char s = str.charAt(i);
            
            // 괄호 안에서 태그 체크
            if (s == '<') {
                while (!dq.isEmpty())
                    sb.append(dq.pop());
                tag = 1;
                sb.append(s);
            }
            
            else if (s == '>') {
                tag = 0;
                sb.append(s);
            }
            
            // 공백 만나면 뒤집기(< 안일 때는 어차피 dq 비어있음)
            else if (s==' '){
                while(!dq.isEmpty()){
                    sb.append(dq.pop());
                }
                sb.append(s);
            }
            
            // 괄호 안에서는 그냥 바로 append
            else if (tag == 1) {
                sb.append(s);
            }

            else {
                dq.push(s);
            }
        }
        
        while (!dq.isEmpty()) {
            sb.append(dq.pop());
        }
        return sb.toString();
    }
}

 

---

🚀 새로 배운 내용

- Deque를 이용한 스택 구현 방법

- 태그를 이용할 때 boolean을 쓰는 것도 좋은 방법

 

 

---

😺  느낀점

- 구상할 때 손으로 직접 써보면서 풀기

- 조건을 나눠서 푸는 것이 때로는 정답일 수도 있다!

- deque의 특성을 최대한 활용하려고 처음에 풀려고 한게 오히려 더 헷갈렸던 거 같다.

때로는 단순하게 생각하는게 도움이 될 때도 있다!

 

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

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