99클럽 코테 스터디 15일차 TIL

백준 - 13417번

풀이

N개의 문자 중, 가장 왼쪽 문자를 기준으로 다음에 오는 문자들과 비교한다.

사전 순으로 빠른 문자는 가장 왼쪽(First)에 배치하고, 반대라면 가장 오른쪽(Last)에 배치한다. 

 

문제를 읽고 예제 출력을 봤을 때 조금 의아했다.

분명 사전 순서로 배치되었을 텐데 어떻게 ASDFG, AAABCBC가 나오는 걸까.

 

A S D F G 의 알파벳 카드가 주어졌을 때, A를 먼저 뽑고 다음으로 S, D... 순서로 뽑게 될 것이다.

현재 소지 중인 가장 왼쪽에 있는 카드와 다음으로 뽑은 카드를 비교한다.

D 카드를 뽑았을 때, 사전 순서대로라면 A 카드 오른쪽에 배치해야하지만 이미 S 카드가 배치된 상태이다. 

여기서 그리디 알고리즘을 다시 살펴보면

• 모든 경우에 최적해를 보장하지 않는다.
• 한번 결정한 것은 번복하지 못한다.

주어진 카드에서 ADFGS 순서로 배치하는 것이 가장 최적이겠지만 S 카드를 먼저 배치한 상황이다.

이미 배치된 카드는 다른 자리로 옮길 수 없다.

 

구현 1 - 실패

import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int N = sc.nextInt();

            String[] alphabets = new String[N];
            for (int j = 0; j < N; j++) {
                alphabets[j] = sc.next();
            }
            
            // 수정 필요 start
            String first = alphabets[0];
            String result = first;
            for (int j = 1; j < alphabets.length; j++) {
                String tmp = alphabets[j];

                if (first.hashCode() > tmp.hashCode()) {
                    result = tmp.concat(result);
                } else {
                    result = result.concat(tmp);
                }
            }
            // end

            sb.append(result).append("\n");
        }

        System.out.println(sb);
        sc.close();
    }
}

문제를 잘못이해하고 작성했던 코드다. 문자 비교를 가장 처음에 뽑았던 카드로만 해야 하는 것으로 이해했다. 

hashcode가 사용되는 조건문도 수정이 필요하다.

만약 같은 문자를 비교하게되면 왼쪽이 아닌 오른쪽으로 이동하게 된다.

• 문자 비교 후 새로 초기화될 때마다 문자열의 첫 번째 문자와 다음 문자를 비교해야 한다.
• hashcode 비교시 같은 문자가 오는 경우 왼쪽으로 이동하게 해야 한다. 

구현 2

String result = alphabets[0];
for (int j = 1; j < alphabets.length; j++) {
    char tmp = alphabets[j].charAt(0);

    // 반복문을 돌때마다 생성되는 결과 문자열의 첫 번째 문자와 비교
    if (result.charAt(0) >= tmp) { // first
        result = alphabets[j].concat(result);
    } else { // last
        result = result.concat(alphabets[j]);
    }
}

수정하고 통과되었지만 메모리와 시간이 많이 소모된다.

코드를 보면 concat()으로 문자를 반복해서 초기화하고 있다. 이런 방식은 메모리에 많은 부담을 준다.

그리고 입출력은 Scanner를 사용하고 있는데, Scanner의 경우 편리한 데이터 형식 변환을 제공하지만 그로 인해 추가적인 처리 과정이 필요하여 BufferedReader보다 비교적 느리다.

 

입출력은 BufferedReader를 사용하고,

문자열을 새롭게 초기화하는 방식 대신, 자료구조를 사용하여 구현해보려 한다.

문자 비교 후, 문자열의 앞/뒤에 배치해야 하기 때문에 양쪽 끝에서 삽입이 가능한 Deque를 선택했다.

구현 3

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());

            StringTokenizer st = new StringTokenizer(br.readLine());
            String[] alphabets = new String[N];
            for (int j = 0; j < N; j++) {
                alphabets[j] = st.nextToken();
            }

            Deque<String> deque = new ArrayDeque<>();
            deque.addFirst(alphabets[0]);

            for (int j = 1; j < alphabets.length; j++) {
                char tmp = alphabets[j].charAt(0);

                if (deque.getFirst().charAt(0) >= tmp) { // first
                    deque.addFirst(alphabets[j]);
                } else { // last
                    deque.addLast(alphabets[j]);
                }
            }

            while (!deque.isEmpty()) {
                sb.append(deque.remove());
            }
            sb.append("\n");
        }

        System.out.println(sb);
        br.close();
    }
}

---

백준 13417번 카드 문자열

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