항해99 11/13(토) 알고리즘

 

항해99 11/8(월) 알고리즘 TIL

에서 해결 못 했었던 21번 문제...

왜 안 되는지 알아냈다!

 

 

코딩테스트 연습 - 이상한 문자 만들기

class Solution {
    public String solution(String s) {
        String answer = "";
        //이게 왜 안 될까.....?        
        String[] strs = s.split(" ");

        for(int i = 0; i < strs.length; i++){
            for(int k = 0; k < strs[i].length(); k++){
                if(k % 2 == 0) {
                    answer += Character.toUpperCase(strs[i].charAt(k));
                }else{
                    answer += Character.toLowerCase(strs[i].charAt(k));
                }
            }
            if(i != strs.length-1){
                answer += " ";
            }
        }

        return answer;
    }
}

왜 안 되냐면...

1. split은 문자열을 해당 string 기준으로 나누어 배열로 저장해주는 함수이다.

2. split 과정에서 기준이 되어주는 단어는 사라진다.

3. 이에 따라 문자열 좌우 끝의 공백이 제거되거나 중간 공백이 기존 공백 개수와 관계없이 하나만 출력되는 것이다!

" hello world! " -> "HeLlO WoRlD!"

"hi   i'm  kim!" -> "Hi I'M KiM!"

대문자 소문자 변환에만 집중하다보니 이 부분을 간과했다. 어처구니 없는 부분이다. 이 문제를 해결하는 방법은 두 가지다.

1. 상단의 통과에 성공한 기본 코드처럼 실행한다.

2. 빈 배열 발견 시, 공백을 추가해준다.

 

방법 1은 이미 했으니, 방법 2로 해보겠다.

 

class Solution {
    public String solution(String s) {
        String answer = "";
        String[] strs = s.split(" ");

        for(int i = 0; i < strs.length; i++){
            // 문자열이 공백일 때 처리
            if(strs[i].length() == 0){
                answer += " ";
            }else{
                for(int k = 0; k < strs[i].length(); k++){
                    if(k % 2 == 0) {
                        answer += Character.toUpperCase(strs[i].charAt(k));
                    }else{
                        answer += Character.toLowerCase(strs[i].charAt(k));
                    }
                }
                if(i != strs.length-1){
                    answer += " ";
                }
            }
        }
        int anc = s.length() -1;
        
        // 끝 문자열이 공백일 때 처리
        while(s.charAt(anc) == ' '){
            answer += " ";
            anc--;
        }

        return answer;
    }
}

돌아가긴 한다. 근데 코드가 더 복잡해지는데다가 기존 코드보다 끔찍할 정도로(10배 정도) 느리다. 이런 방법은 지양하고 겸손하게 직관적인 코드나 짜자.

 

그리고 하는 김에 코드를 조금 더 직관적으로 바꾸고 성능을 개선한 코드도 짜봤다. 이게 지금까지 짜본 것 중 가장 빠르다. 위에 있는 느려터진 코드보다 100배정도 빠르다.

 

import java.util.*;

class Solution {
    public String solution(String s) {
        StringBuilder answer = new StringBuilder();
        char[] chars = s.toCharArray();
        
        // anc가 짝수면 대문자, 홀수면 소문자로 출력해줄 것임.
        int anc = 0;
        for(char c : chars){
            if(c == ' '){
                answer.append(' ');
                // 공백을 만났을 때 초기화를 시켜주면 첫 문자부터 다시 대문자가 됨.
                anc = 0;
                continue;
            }
            
            if(anc % 2 == 0){
                answer.append(Character.toUpperCase(c));
            }else{
                answer.append(Character.toLowerCase(c));
            }
            anc++;   
        }

        return answer.toString();
    }
}

이제야 속이 좀 후련하네 ^-^)b

 

 

항해99 11/12(금) 알고리즘 TIL

여기에 이론만 써놓고 구현은 못 했던 코드들도 한 번 해보려고 한다.

 

 

DFS

올바른 출력 순서

A -> B -> E -> K -> L -> F -> C -> G -> D -> H -> M -> I -> J

public class Main {
    static char[][] tree = new char[][]{
            {'B', 'C', 'D'},
            {'A', 'E', 'F'},
            {'A', 'G'},
            {'A', 'H', 'I', 'J'},
            {'B', 'K', 'L'},
            {'B'},
            {'C'},
            {'D', 'M'},
            {'D'},
            {'D'},
            {'E'},
            {'E'},
            {'H'}
    };
    static boolean visited[] = new boolean[tree.length];

    static void dfs(int nodeIdx){
        // 1. tree[0] 'A' visited 추가 및 탐색       // push
        // 2. tree[0][0] 'B' 추가 및 탐색     // pop, pop 한 데이터로 for문 돌려서 push
        // 3. tree[1][0] 'E' 추가 및 탐색     // 반복
        // 4. tree[4][0] 'K' 추가 및 탐색
        // 5. tree[10][0] 모든 목록이 visited. 부모('K')에게 돌아감
        visited[nodeIdx] = true;

        System.out.print((char)(nodeIdx + 'A') + " -> ");
        for(char node: tree[nodeIdx]){
            if(!visited[node - 'A']){
                dfs(node - 'A');
            }
        }
    }

    public static void main(String[] args){
        dfs(0);
    }
}

출력 결과

A -> B -> E -> K -> L -> F -> C -> G -> D -> H -> M -> I -> J ->

재귀함수를 이용해 구현한 코드이다. 스택을 이용해서 어떻게든 해보고 싶었는데..... 쉽지 않았다.

아마 tree 구조가 실제 클래스로 바뀐다면 for문 내부의 구성이 childs를 순차적으로 불러올 수 있도록 바뀔 것이다. 나머지는 큰 차이가 없을 것 같다.

 

 

BFS

올바른 출력 순서

A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> L -> M

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static char[][] tree = new char[][]{
            {'B', 'C', 'D'},
            {'A', 'E', 'F'},
            {'A', 'G'},
            {'A', 'H', 'I', 'J'},
            {'B', 'K', 'L'},
            {'B'},
            {'C'},
            {'D', 'M'},
            {'D'},
            {'D'},
            {'E'},
            {'E'},
            {'H'}
    };
    static boolean visited[] = new boolean[tree.length];

    static void bfs(int nodeIdx) {
        // 1. tree[0] 'A' visited 추가 및 탐색 // add, poll
        // 2. tree[0][0] 'B' 추가 // add
        // 3. tree[0][1] 'C' 추가 // add
        // 4. tree[0][2] 'D' 추가 // add
        // 5. tree[0][0] 'B' 탐색 // poll

        Queue<Character> q = new LinkedList<>();

        // 1. visited 추가
        q.offer((char) (nodeIdx + 'A'));
        visited[nodeIdx] = true;

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            // 1. 5. 탐색
            int nodeIndex = q.poll() - 'A';
            System.out.print((char) (nodeIndex + 'A') + " -> ");

            //큐에서 꺼낸 노드와 연결된 노드들 체크
            for (char node : tree[nodeIndex]) {
                int visitedIdx = node - 'A';
                // 방문하지 않았으면 방문처리 후 큐에 넣기
                if (!visited[visitedIdx]) {
                    // 2. 3. 4. 추가
                    visited[visitedIdx] = true;
                    q.offer((char) (visitedIdx + 'A'));
                }
            }
        }
    }

    public static void main(String[] args) {
        bfs(0);
    }
}

 

사실.. DFS랑 BFS 코드는 현재 내 손으로 전부 쓴 건 아니고, 이미 작성되어있는 코드들에서 많은 부분을 참고했다. 로직에 대한 이해는 되어 있으니, 반복숙달을 하면서 체화 시키고 응용하는 방법을 알아나가야겠다.