[Study] 11월 13일 Algorithm Study

목표

---

• 팀원분들과 함께 매주 월, 화, 목, 금 2시에 알고리즘 스터디를 진행하기로 하였다. 오늘은 처음 알고리즘 스터디를 진행한 날인데 느낀점이 있어 스터디 회고록을 작성한다. 오늘 작성한 내용을 잊지 않고 다음부터는 꼭 고려해서 알고리즘을 짜는것이 목표이다.

 

Programmers Lv. 1 대충 만든 자판

---

https://school.programmers.co.kr/learn/courses/30/lessons/160586

프로그래머스

 

풀이 개요

• 해당 문제는 자판의 정보를 담고 있는 keymap배열과 만들어야하는 텍스트 정보를 담고 있는 targets변수를 이용해 target을 만들기 위한 최소 자판 입력 횟수를 구하는 문제이다.
• 문제를 보자마자 알파벳 정보를 가지는 크기 26의 배열을 만들어 풀어야겠다고 생각했고, 배열 안에는 전체 자판에서 특정 알파벳을 입력하기 위한 최소 자판 입력 횟수를 기록하기로 했다. 해당 문제는 아래 알고리즘이 정석이라고 생각했고, 문제 또한 어렵지 않게 풀 수 있었다. 

 

발견한 문제

• 팀원 중 한 분은 Map을 이용해서 문제를 해결하셨다. key값에 알파벳을 넣고 value에 최소 비용을 삽입해서 알고리즘을 작성하셨다. 처음 봤을때 "아, Map을 이용해서도 풀 수 있구나"라고 생각했지만, 얼마 가지 않았다.
• 다른 한 분이 시간 복잡도에 대해 말씀해주셨는데 배열을 이용하면 O(1)의 시간복잡도를 가지는 반면, Map은 key값을 탐색하기 위해 O(logn)의 시간복잡도를 가진다는 말씀을 듣고 소름이 돋았다.

 

배운점

• 앞으로는 무작정 "이런 자료구조가 적합하겠다." 라고해서 사용하는 것이 아닌 효율적인 측면에서 자료구조를 비교해서 "해당 알고리즘을 구현하기 위해서는 이런 자료구조를 사용할 수 있고 그 중, 이 자료구조가 가장 좋은 효율을 낼 수 있으니 이걸 사용하자." 라는 생각을 가지고 알고리즘 문제를 풀어야겠다.

 

작성 코드

import java.util.Arrays;

class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        int[] dp = new int[26]; //0: A, 25: Z
        Arrays.fill(dp, Integer.MAX_VALUE);
        
        for(int i=0; i<keymap.length; i++) {
            String key = keymap[i];
            
            for(int j=0; j<key.length(); j++) {
                int keyIdx = key.charAt(j) - 'A';
                if(dp[keyIdx] > j+1) dp[keyIdx] = j+1;
            }
        }
        
        int[] answer = new int[targets.length];
        for(int i=0; i<targets.length; i++) {
            String target = targets[i];    
            
            for(int j=0; j<target.length(); j++) {
                int t = target.charAt(j) - 'A';
                if(dp[t] == Integer.MAX_VALUE) {
                    answer[i] = -1;
                    break;
                }
                answer[i] += dp[t];
            }
        }
        
        return answer;
    }
}



 

Programmers Lv. 1 둘 만의 암호

---

https://school.programmers.co.kr/learn/courses/30/lessons/160586

프로그래머스

 

풀이 개요

• 해당 문제는 문자열 s의 전체 문자를 index만큼 뒤에 있는 문자들로 바꾸는 문제인데, 특정 문자를 건너뛰기 위한 skip배열이 추가적으로 주어진 문제이다. 문제를 읽고 s만큼 반복문을 돌리고 그 안에서 각 문자의 값을 index만큼 늘리고 skip배열을 돌면서 정답을 만들어가야겠다고 생각했다.

 

발견한 문제

• 하지만, 문제를 풀면서 이런식으로 모든 자료구조를 반복하며 문제를 푸는것이 찝찝했고, 결국 코드 또한 복잡해지면서 테스트케이스에 한 번에 통과하지 못해 디버그를 하는데 꽤 시간을 잡아먹었다.
• 팀원들의 의견을 듣고자 팀원분들께 리뷰를 부탁드렸고 앞 문제에서 시간복잡도를 말씀해주신 팀원분이 또 다시 솔루션을 주셨다. "문제를 해결하는 흐름은 크게 다르지 않지만, 저는 이렇게 풀었습니다." 라고 말씀하시며 작성한 코드를 보여주셨는데 코드를 보니 망치로 얻어맞은 느낌이 들었다.
• 팀원분은 앞 문제처럼 알파벳 정보를 가지는 크기 26의 boolean[]배열을 만들어서 skip해야하는 알파벳의 정보를 저장해둔 것이다. 그리고 함수를 하나 만들어서 알파벳을 넣으면 true/false를 반환하게 하였는데 반복도 줄고 코드도 훨씬 깔끔해보였다.

 

배운점

• 앞 문제를 잘 풀어놓고, 같은 성격의 문제를 비효율적인 힘들게 풀었다는 생각을 했다. 앞으로 알파벳에 관련된 문제를 만나면 배열의 index로 알파벳에 접근하는 방법을 우선적으로 생각해봐야겠다.
• 또한, 복잡한 코드는 문제 풀이를 힘들게 한다는 다시 한 번 것을 깨달았다. 중복되는 부분이 아니더라도 가독성을 떨어뜨릴 수 있는 코드는 함수로 따로 빼서 코드를 작성하는 습관을 들여야겠다.

 

작성 코드

class Solution {
    public String solution(String s, String skip, int index) {
        String answer = "";
        
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);            
            
            int count = index;
            while(count > 0) {
                char nc = (char) (c+1);
                if(nc > 'z') nc = 'a';
                
                boolean canSkip = false;
                for(int j=0; j<skip.length(); j++) {
                    if(nc == skip.charAt(j)) {
                        canSkip = true;
                        break;
                    }
                }
                
                if(!canSkip) count--;    
                c = nc;
            }
            
            answer += c;
        }
        
        return answer;
    }
}

 

수정 코드

class Solution {
    public String solution(String s, String skip, int index) {
        String answer = "";
        
        boolean[] dp = new boolean[26];
        for(int i=0; i<skip.length(); i++) {
            dp[skip.charAt(i) - 'a'] = true;
        }
        
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);            
            
            int count = index;
            while(count > 0) {
                char nc = (char) (c+1);
                if(nc > 'z') nc = 'a';
                
                if(!dp[nc - 'a']) count--;
                c = nc;
            }
            answer += c;
        }
        
        return answer;
    }
}