[백준 - 2871번] 아름다운 단어 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, 정렬

입력

첫째 줄에 짝수 N이 주어진다. (2 ≤ N ≤ 100 000)

둘째 줄에 종이에 적혀 있는 글자가 순서대로 주어진다. 글자는 모두 알파벳 소문자이다.

출력

만약, 희원이가 이길 수 있다면 첫째 줄에 "DA"를, 없다면 "NE"를 출력한다. 둘째 줄에는 희원이가 만들 수 있는 가장 아름다운 단어를 출력한다.

풀이

희원이가 상근이를 이길 수 있는지, 만들 수 있는 가장 아름다운 단어는 무엇인지를 출력해야 한다.

이 문제는 골드 2인데 아이디어가 어렵지 않은 것 같다. 체감상

희원이가 사전 순으로 앞에 있는 단어를 만들기 위해서는 당연히 남아 있는 알파벳 중 사전순으로 가장 앞에 있는 알파벳을 골라야 한다.

그러면 그러한 알파벳이 여러 개라면? index가 더 뒤에 있는 알파벳을 골라야 한다.

왜냐하면 상근이는 가장 오른쪽에 있는 알파벳을 고르기 때문에 상근이가 최선의 선택을 할 수 없게끔 하려면 사전순으로 가장 앞에 있으면서, index순으로 가장 오른쪽에 있는 알파벳을 희선이가 선택해야 한다.

즉, 희선이의 최선의 선택은 사전순으로 가장 앞에 있으면서, index순으로 가장 오른쪽에 있는 알파벳이라고 할 수 있다.

그리디 풀이의 시간 복잡도는 O(N * log N)이다. (정렬해서)

소스 코드

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

class Info implements Comparable<Info>{
    int ind, pri;
    Info(int ind, int pri) {
        this.ind = ind;
        this.pri = pri;
    }
    
    @Override
    public int compareTo(Info o) {
        if(this.pri < o.pri) {
            return -1;
        } else if(this.pri > o.pri) {
            return 1;
        } else {
            if(this.ind < o.ind) {
                return 1;
            } else if(this.ind > o.ind) {
                return -1;
            }
        }
        return 0;
    }
}

public class Main {
    static int N;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      String str = br.readLine();
      Info[] sang = new Info[N];
      Info[] hee = new Info[N];
      for(int i=0; i<N; i++) {
          sang[i] = new Info(i, (int) str.charAt(i));
          hee[i] = new Info(i, (int) str.charAt(i));
      }
      Arrays.sort(hee);
      
      boolean[] visited = new boolean[N];
      int heeCursor = 0;
      int sangCursor = N - 1;
      int cout = 0;
      boolean sangTurn = true;
      StringBuilder sangSb = new StringBuilder();
      StringBuilder heeSb = new StringBuilder();
      while(cout != N) {
          if(sangTurn) {
              while(visited[sangCursor]) {
                  sangCursor -= 1;
              }
              visited[sangCursor] = true;
              sangSb.append((char) sang[sangCursor].pri);
          } else {
              while(visited[hee[heeCursor].ind]) {
                  heeCursor += 1;
              }
              visited[hee[heeCursor].ind] = true;
              heeSb.append((char) hee[heeCursor].pri);
          }
          sangTurn = !sangTurn;
          cout += 1;
      }
      int result = heeSb.toString().compareTo(sangSb.toString());
      if(result < 0) {
          System.out.println("DA");
      } else {
          System.out.println("NE");
      }
      System.out.println(heeSb.toString());
  }
}