BOJ 1464번 뒤집기3

1464번 뒤집기3

문제 이해하기

• 문자열을 뒤집거나 그대로 두어 사전순으로 가장 앞선 문자열을 찾는다.
• 문자열의 길이 <= 50
• 제한시간 2초

문제 접근 방법

사전 순으로 앞에 있는 단어를 뒷쪽에 두고 마지막에 문자열을 reverse한다.

1. 초기 문자열: a1a2a3 ... ak-1akak+1
2. k번째 문자까지 뒤집은 문자열: akak-1 ... a2a1ak+1
3. k+1번째 문자까지 뒤집은 문자열: ak+1a1a2a3 ... ak-1ak

⇒ 1, 2, 3 과정을 거친 결과 ak+1의 위치만 변경되었다.

---

이 점을 문제에 적용해보자.

문자열 a1a2a3 ... ak-1akak+1에서

• ak가 ak+1보다 앞선다면 ak+1의 위치를 변경
• ak가 ak+1과 앞서지 않는다면 문자열을 유지

---

예시로 이해해보자.

초기문자열 ACAB에서

1. 문자열 AC에서 A와 C 비교 ⇒ 위치 변경 ⇒ CAAB
2. 문자열 CAA에서 A와 A 비교 ⇒ 위치 유지 ⇒ CAAB
3. 문자열 CAAB에서 A와 B 비교 ⇒ 위치 변경 ⇒ BCAA
4. 사전 순으로 앞에 있는 단어를 뒤에 두었으므로 reverse한다.

구현 배경 지식

• 문자열 비교

문제를 해결한 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // 입력 및 전처리
        String str = br.readLine();
        String ans = str.substring(0, 1);

        // 로직
        for (int i = 1; i < str.length(); ++i) {
            if (ans.charAt(i - 1) < str.charAt(i)) {
                ans = str.charAt(i) + ans;
            } else {
                ans = ans + str.charAt(i);
            }
        }

        // 출력
        sb.append(ans);
        sb.reverse();
        sb.append("\n");

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

}