[백준/JAVA] 9081번: 단어 맞추기

📖 문제

9081번: 단어 맞추기

 

 

💡  풀이 방식

• 구현

1. 단어 맨 뒤에서부터 확인하며 처음으로 감소하는 부분의 인덱스를 찾는다. (idx1)

2. 다시 맨 뒤에서부터 확인하며 감소하는 부분보다 큰 부분의 인덱스를 찾는다. (idx2)

3. idx1과 idx2에 있는 두 값을 swap한다.

4. 단어의 idx1 위치부터 끝까지 단어를 오름차순 정렬한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int T;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        while(T --> 0) {
            findNextWord(br.readLine());
        }
        
        System.out.println(sb.toString());
    }
    
    private static void findNextWord(String str) {
        int len = str.length();
        char[] ch = str.toCharArray();
        
        int idx1 = -1; // 처음으로 감소하는 원소 위치
        int idx2 = 0; // 1에서 찾은 원소보다 처음으로 큰 원소 위치
        
        // 1) 맨 뒤에서부터 확인하며 처음으로 감소하는 부분 찾기
        for(int i = len - 1 ; i > 0 ; i--) {
            if(ch[i - 1] < ch[i]) {
                idx1 = i - 1;
                break;
            }
        }
        
        if(idx1 == -1) {
            sb.append(str).append("\n");
            return;
        }
       
        // 2) 다시 맨 뒤에서부터 확인하며 감소하는 부분보다 큰 부분 찾기
        for(int i = len - 1 ; i >= 0 ; i--) {
            if(ch[idx1] < ch[i]) {
                idx2 = i;
                break;
            }
        }
        
        // 3) idx1과 idx2에 있는 두 원소 swap하기
        char tmp = ch[idx1];
        ch[idx1] = ch[idx2];
        ch[idx2] = tmp;
        
        Arrays.sort(ch, idx1 + 1, len); // 4) idx1의 위치 뒷 부분 오름차순 정렬
        
        for(char c : ch)
            sb.append(c);
        sb.append("\n");
    }
}
 

 

 

➕ 다른 풀이 방식

그리디...

백준 9081 자바 - 단어 맞추기 (BOJ 9081 JAVA)

---

💦 어려웠던 점

- 조합으로 모든 단어 다 구하고 정렬하고 나서 다음에 있는 값 구하는 식으로 풀었었는데 단어 길이가 아무래도 99까지 되다보니 당연히 시간 초과가 뜰 수밖에 없었다..ㅋㅋㅠ 그리고 다른 분들 풀이 참고..

 

 

🧐 새로 알게 된 내용

이런 아이디어.. 어떻게 생각해시는거지?ㅠ

문자열 문제도 주기적으로 풀어줘야겠다ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V	240302

---

(참고)

✔ 풀이 참고

백준 9081번 단어 맞추기 [JAVA]

백준 9081번(자바)