[SWEA] 올해의 조련사

[5672] 올해의 조련사

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRgX36gSIDFAUo

• 앵무새들의 첫 글자가 순서대로 주어진다.
• 새로운 줄 세우기 방법으로 다시 앵무새들을 줄 세웠을 때 얻을 수 있는 가장 빠른 문자열을 알아내자.
• 새로운 줄 세우기 방법은 다음과 같다.
• 기존의 줄을 세운 다음 가장 앞 or 뒤에 있는 앵무새를 새로운 줄의 마지막에 새우는 것을 반복하는 방식

 

 

Solution

• 기존의 줄에서 앞 문자와 뒤 문자의 사전 순서를 비교하여 새로운 줄의 끝에 순서대로 넣는다.
• 사전식 순서가 같은 경우 while() 문을 반복하여 다음에 나오는 문자가 더 작은 앵무새의 이름을 넣는다. 

 

 

소스코드

 

import java.io.IOException;
import java.util.Scanner;
 
public class Solution {
    static int n, front, back;
    static char[] line;
    static StringBuilder sb;
 
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
 
        int tc = sc.nextInt();
        int tnum = 0;
 
        while (tc-- > 0) {
            n = sc.nextInt();
            line = new char[n];
            sb = new StringBuilder();
 
            front = 0;
            back = n - 1;
 
            for (int i = 0; i < n; i++) {
                char c = sc.next().charAt(0);
                line[i] = c;
            }
 
            for (int i = 0; i < n; i++) {
                if (line[front] < line[back]) {
                    sb.append(line[front]);
                    front += 1;
                    continue;
                } else if (line[front] > line[back]) {
                    sb.append(line[back]);
                    back -= 1;
                    continue;
                } else if (line[front] == line[back]) {
                    int tempF = front + 1;
                    int tempB = back - 1;
                    while (true) {
                        if (tempB - tempF > 0) {
 
                            if (line[tempF] < line[tempB]) {
                                sb.append(line[front]);
                                front += 1;
                                break;
                            } else if (line[tempF] > line[tempB]) {
                                sb.append(line[back]);
                                back -= 1;
                                break;
                            } else if (line[tempF] == line[tempB]) {
                                tempF++;
                                tempB--;
                            }
                        } else {
                            sb.append(line[front]);
                            front += 1;
                            break;
                        }
 
                    }
                }
            }
            tnum++;
            System.out.println("#" + tnum + " " + sb.toString());
        }
    }
 
    public static int stoi(String s) {
        return Integer.parseInt(s);
    }
}