[백준] 9081 - 단어 맞추기

[문제링크]

9081번: 단어 맞추기

 

0. C++ 등 일부 언어에서 내장 라이브러리로 제공하는 next permutation 문제

  - 알파벳 순서대로 만들어진 조합의 다음 모습 구하기

 

1. next permutation을 구하는 방법은?

• 뒤에서부터 탐색해, 증가하지 않는 첫 부분의 위치를 구한다
  • 126543 을 예시로 하면, 3-4-5-6-2-1 이므로 2가 구하려는 위치이다
• 다시 뒤에서부터 탐색해, 2보다 큰 수들 중 처음 나오는 수의 위치를 구한다
  • 3-4-5-6-2-1 순서이므로 3이 2보다 큰 수이면서 가장 처음 나오는 수이다
• 1/2에서 구한 두 위치의 수를 바꾼다
  • 126543은 2/3이 바뀌며 136542가 된다
• 1번에서 구한 위치 뒤쪽의 수들을 정렬한다
  • 2번째 수였으므로 3~끝까지 정렬한다
  • 136542에서 132456이 된다

2. 실제 풀이 방법

• 앞부분 - 뒷부분 2개의 stringbuilder를 둔다
• 뒤에서부터 탐색해, 증가하지 않는 첫 위치(이하 A위치)를 구하며 큐에 넣는다
• 해당 위치 앞은 변하지 않을 것이니, 앞부분 builder에 넣는다
• 큐에 들어가 있는 부분은 오름차순으로 진행하며 차례대로 넣는 뒷부분이니, 그대로 꺼내도 정렬되어 있다
• 큐에서 하나씩 꺼내면서 뒷부분 builder에 넣되, A위치 수보다 커질때 한번 따로 처리해야한다
• 커지는 순간 큐에서 꺼낸 수는 앞부분 builder에, A위치의 수는 뒷부분 builder에 넣는다 (swap의 역할)
• 큐의 나머지는 다 뒷부분에 넣는다

 

• 최종적으로 합치면 종료

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = pint(br.readLine());
		for (int test = 1; test <= tc; test++) {
			StringBuilder sb = new StringBuilder();
			StringBuilder sb_back = new StringBuilder();
			char[] str = br.readLine().toCharArray();
			
			Queue<Character> qu = new LinkedList<>();
			int len = str.length-1;
			while(len>0 && str[len-1] >= str[len]) {
				qu.add(str[len]);
				len--;
			}
			if(len==0) {
				//다음 단어가 없다
				System.out.println(str);
			}
			else {
				qu.add(str[len]);
				len--;
				
				//정상인 앞부분 넣기
				for (int i = 0; i < len; i++) {
					sb.append(str[i]);
				}
                
				//바뀔 위치 탐색
				char temp=' ';
				while(qu.peek() <= str[len]) {
					temp=qu.poll();
					sb_back.append(temp);
				}
                
				//바꾼다
				sb.append(qu.poll());
				sb_back.append(str[len]);
                
				//나머지 넣기
				while(!qu.isEmpty()) {
					sb_back.append(qu.poll());
				}

				System.out.print(sb);
				System.out.println(sb_back);
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면