[Programmers] PCCP 모의고사 1회 1번 - 외톨이 알파벳 - Java

문제 

프로그래머스

 

풀이

ArrayList 

1. a ~ z에 대한 인덱스를 담을 ArrayList를 만든다.

2. 문자열에 있는 문자를 순회하면서, 각 알파벳에 맞는 인덱스를 넣는다.

3. 2회 이상이 되면서, 인덱스가 차이가 1이상 차이나면 문자를 붙인다.

 

소스코드

import java.util.ArrayList;

class Solution {
    public String solution(String input_string) {
        char[] arr = input_string.toCharArray();
        
        int alphaCnt = 'z' - 'a' + 1;
        
        ArrayList<Integer>[] idxList = new ArrayList[alphaCnt];
        
        for (int i = 0; i < alphaCnt; i++) {
            idxList[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < arr.length; i++) {
            char ch = arr[i];
            
            idxList[ch - 'a'].add(i);
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < alphaCnt; i++) {
            if (idxList[i].size() <= 1) {
                continue;
            }
            
            boolean flag = false;
            
            for (int j = 0; j < idxList[i].size() - 1; j++) {
                if (idxList[i].get(j + 1) - idxList[i].get(j) != 1) {
                    flag = true;
                    break;
                }
            }
            
            if (flag) {
                sb.append((char)('a' + i));
            }
        }
        
        return sb.toString().isEmpty() ? "N" : sb.toString();
    }
}

 

int[]

1. 문자가 등장한 시작 인덱스, 끝 인덱스를 담을 int 배열과 알파벳이 있었는지 여부를 담을 배열을 만든다.

2. 시작과 끝 인덱스를 삽입하고 존재하는지 여부도 체크한다.

3. 등장하지 않았으면서, 시작과 끝 인덱스가 다르면, 2회 이상 등장했다는 경우고, 시작 인덱스와 끝 인덱스 사이에 다른 알파벳이 있으면 조건에 충족하므로, 문자를 붙인다. 

 

소스코드

import java.util.Arrays;

class Solution {
    public String solution(String input_string) {
        char[] arr = input_string.toCharArray();
        
        int alphaCnt = 'z' - 'a' + 1;
        
        int[] firstPos = new int[alphaCnt];
        int[] lastPos = new int[alphaCnt];
        
        boolean[] isExist = new boolean[alphaCnt];
        
        Arrays.fill(firstPos, -1);
        
        for (int i = 0; i < arr.length; i++) {
            int idx = arr[i] - 'a';
            
            if (firstPos[idx] == -1) {
                firstPos[idx] = i;
            }
            
            lastPos[idx] = i;
            isExist[idx] = true;
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < alphaCnt; i++) {
            if (!isExist[i] || firstPos[i] == lastPos[i]) continue;
            
            boolean flag = false;
            
            for (int j = firstPos[i]; j <= lastPos[i]; j++) {
                if (arr[j] - 'a' != i) {
                    flag = true;
                    break;
                }
            }
            
            if (flag) {
                sb.append((char) ('a' + i));
            }
        }
        
        return sb.length() == 0 ? "N" : sb.toString();
    }
}

 

성능

ArrayList 풀이

int[] 풀이

풀이	평균 실행 시간 (ms)	평균 메모리 사용량 (MB)
int[]	0.10	80.3
ArrayList	0.37	82.0

 

평균 실행 시간: 3.7배 빨라짐

평균 메모리 사용량: 1.7MB 줄었음

 

빨라진 이유

ArrayList는 가변 배열이다. 즉 리사이징을 해서 배열이 복사되고 크기를 늘려야하는데, 2600개의 문자의 인덱스를 저장하는데 있어서 int[] 배열로 시작과 끝 인덱스만 저장하는 것보다 시간복잡도적인 면에서 더 빠른 실행 시간을 보여줬기 때문이다.