[BOJ]11656번: 접미사배열(java)

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

11656번: 접미사 배열

 

통과된 코드

 

import java.io.*;
import java.util.Arrays;
 
public class Main {
    public static void main(String[] args) {
 
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringBuilder sb = new StringBuilder();
 
            String strCmd = br.readLine();
            int iCmdLength = strCmd.length();
            String[] arrSubString = new String[iCmdLength];
            
            for (int i = 0; i < iCmdLength; i++) {
                arrSubString[i] = strCmd.substring(i);
            }
            
            Arrays.sort(arrSubString);
            
            for (int i = 0; i < iCmdLength; i++) {
                sb.append(arrSubString[i] + "\n");
            }
            
            bw.write(sb.toString());
            bw.flush();
 
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 

 

 

런타임에러 난 코드

import java.io.*;
import java.util.Stack;
 
public class Main {
    public static Stack<String> stack = null;
    public static Stack<String> subStack = null;
 
    public static void main(String[] args) {
 
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringBuilder sb = new StringBuilder();
 
            String strCmd = br.readLine();
 
            stack = new Stack<String>();
            subStack = new Stack<String>();
 
            int iCmdLength = strCmd.length();
            for (int i = 0; i < iCmdLength; i++) {
                String strPart = strCmd.substring(i);
 
                if (i == 0) {
                    stack.push(strPart);
                    continue;
                }
 
                sortChar(strPart, 0);
            }
 
            while (!stack.isEmpty()) {
                subStack.push(stack.pop());
            }
 
            while (!subStack.isEmpty()) {
                sb.append(subStack.pop() + "\n");
 
            }
            bw.write(sb.toString());
            bw.flush();
 
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
 
    public static int sortChar(String strPart, int i) {
 
        if (i >= stack.peek().length()) {
            stack.push(strPart);
 
            return 0;
 
        } else if (i >= strPart.length()) {
            subStack.push(stack.pop());
            stack.push(strPart);
 
            while (!subStack.isEmpty()) {
                stack.push(subStack.pop());
            }
 
            return 0;
        }
 
        if (stack.peek().charAt(i) < strPart.charAt(i)) {
            stack.push(strPart);
 
        } else if ((stack.peek().charAt(i) == strPart.charAt(i))) {
 
            int length = (stack.peek().length() < strPart.length() ? stack.peek().length() : strPart.length());
 
            if (i + 1 >= length) {
                return 0;
            }
 
            sortChar(strPart, i + 1);
 
        } else if (stack.peek().charAt(i) > strPart.charAt(i)) {
 
            boolean flag = false;
            
            while (!stack.isEmpty()) { 
                int length = strPart.length();
                for (int k = 0; k <= length; k++) {
 
                    if (stack.peek().charAt(k) > strPart.charAt(k)) {
                        subStack.push(stack.pop());
                        break;
                        
                    } else if (stack.peek().charAt(k) == strPart.charAt(k)) {
                        continue;
                    } else if (stack.peek().charAt(k) < strPart.charAt(k)) {
                        stack.push(strPart);
                        flag = true;
                        break;
                    }
                }
                
                if (flag) {
                    break;
                }
            }
 
            if (!flag) {
                stack.push(strPart);
            }
            
            
            while (!subStack.isEmpty()) {
                stack.push(subStack.pop());
            }
        }
 
        return 0;
    }
}

 

 

 

 

 

문자의 모든 접미사를 사전순으로 배열하는 문제

답안지를 보니 자바에서 기본 제공해주는 sort() 배열 정렬 함수가 있는줄 몰랐지 ^^

스택 2개를 이용해서 앞에서부터 글자 하나씩 비교했다...후...

 

아직 완전히 이해하지 못한 재귀함수와 덧대기식 코딩을 하다보니

원하는 값이 나오긴 했지만 코드에서 냄새가 난다...

다시 예쁘게 정리해볼것 !!

 

Tip

오름차순 정렬 - Arrays.sort()

내림차순 정렬 - Collections.reverseOrder()