[Day15]JAVA 카드 문자열(13417번)

https://www.acmicpc.net/problem/13417

 

 

 

백준 카드문자열 문제를 풀기위해서는 Greedy(탐욕법) 을 활용해서 풀 수 있다. 

즉, 최적의 규칙을 찾는 것이다 

 

문제의 규칙 은

첫번째 카드 외 나머지 카드를 왼쪽 과 오른쪽으로 붙여서 알파벳 순으로 가장 빠른 문자열을 출력하는 것이다. 

 

 M K U 세장의 카드가 있을때 

첫번째 카드 M 은 기본으로 한장 내놓고 

두번째 카드 K  는 M과 비교하여 어느 알파벳이 더 빠른지 비교한다 ->  K가 M보다 더 먼저 있으니 가장 왼쪽편에 놓는다. 

세번째 카드 U 는 현재 완성된 단어 KM 중  맨 앞글자인 K 과 비교하여 어느 알파벳이 더 빠른지 확인한다. -> K가 U보다 더 먼저 있으니 U는 가장 오른쪽에 놓는다. 

 

규칙은 문자열의 첫번째 있는 문자와 비교를 하며 더 빠르면 왼쪽으로 , 느리면 오른쪽으로 붙이는 것이다. (첫번째 문자는 예외) 

 

문자를 비교하기 위해서는 문자를 위한 변수형 char 을 사용합니다. 

char은 문자를 담기 위해 만들어진 변수형이지만 그 실체는 정수형 변수입니다. 
char c = 'a'
위에 식과 같이 char 변수에 저장되는 'a' 와 같은 문자도 실제는 숫자로 변형하여 저장되는 것입니다. 
그래서 char 변수는 문자의 크기를 비교할 수 있는 것입니다. 

String 타입의 데이터를 한글자씩 char 타입으로 변환할 수 있다. 
string.charAt(index)

 

 

*최종코드

import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException
{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    StringBuilder newWord = new StringBuilder();    
    StringBuilder cards = new StringBuilder();  

    //테스트 케이스
    int t = Integer.parseInt(br.readLine()); 

    StringBuilder[] answer =  new StringBuilder[t];

    for(int i=0;i<t;i++)
    {
        cards = new StringBuilder();
        newWord = new StringBuilder();    

        //문자열 수(카드 수)
        int l = Integer.parseInt(br.readLine()); 

        st = new StringTokenizer(br.readLine(), " ");
        for(int j=0;j<l;j++)
        {               
            //뽑은 카드들
            cards.append(st.nextToken());  
        } 

        for(int k=0;k<l;k++)
        {   
            char card = cards.charAt(k);

            if(k==0)
                newWord.append(String.valueOf(card));
            else
            {
                char word = newWord.charAt(0);    

                //2.알파벳 순으로 제일 왼쪽 글자보다 크면 오른쪽으로 붙이기  
                if(card > word)
                {   
                    newWord.append(String.valueOf(card));
                }  
                //3. 알파벳 순으로 제일 왼쪽 글자보다 작으면 왼쪽으로 붙이기
                else 
                {
                    newWord.insert(0,card);
                }
            }
        }    

        answer[i] = newWord;           
    }

    for(StringBuilder sb : answer)
    {
        System.out.println(sb);
    }
}   
}