백준 - 이름 궁합

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/15312

 

[문제 설명]

이름 알파벳으로 궁합 맞추기

[접근 방법]

처음엔 Deque를 이용해서 풀었는데, 삭제 연산 때문에 시간이 오래 걸렸다.

두번째엔 그냥 배열을 이용하여 풀었다. 풀어보니 굳이 시간이 오래 걸리는 자료구조를 사용할 필요 없어 보였다.

배열은 인덱스로 메모리에 직접 접근하므로, 시간 복잡도도 빨라졌다.

전체 시간복잡도는 O(N!)이 아닐까 싶다. (연산하는 원소가 N,N-1,N-2, ... ,5,4,3,2,1순으로 하강하니까)

[내 답안 수정하기]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    static int[] numOfStrokesArray = new int[]{3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String aName = br.readLine();
        String bName = br.readLine();
        int[] arrayOfStrkoes = new int[aName.length()+bName.length()];
        // 일자로 이름 번갈아가면서 세우기
        for (int i = 0; i < arrayOfStrkoes.length-1; i=i+2) {
            arrayOfStrkoes[i] = numOfStrokesArray[aName.charAt(i/2)-65];
            arrayOfStrkoes[i+1] = numOfStrokesArray[bName.charAt(i/2)-65];
        }
        
        int size = arrayOfStrkoes.length;
        while (size > 2) {
            for (int i = 0; i < size-1; i++) {
                arrayOfStrkoes[i] = (arrayOfStrkoes[i]+arrayOfStrkoes[i+1])%10;
            }
            arrayOfStrkoes[--size] = 0;
        }

        System.out.println(String.valueOf(arrayOfStrkoes[0])+String.valueOf(arrayOfStrkoes[1]));
    }
}