다 풀기까지 꽤 시간이 소요된 문제. 모든 경우의 수를 구하는 상황이 처음이였고, 순열 알고리즘을 이해하고 활용하는데에 점 애를 먹어서이다.

문제

https://programmers.co.kr/learn/courses/30/lessons/42839

시도한 방법

먼저 1. 모든 경우의 수 만들기 2. 소수 찾기 로 나누어서 각 문제를 해결할 방법을 생각했다. 1은 순열 (nPr) 2는 소수의 정의를 활용했다. ( 처음엔 에라스토테네스의 체를 생각 )

중간에

• 소수판별 조건 (소수판별 대상인 수는 1또는 0이여서는 안됨)
• 중복 제거 => set 자료구조 를 놓쳐 코드를 수정했다. 근데도 전과 동일한 case들을 통과하지 못해서 하나씩 해보기로 결정. 그 과정에서 depth자리 값을 초기화 하지 않았다는 사실을 발견. 결국 DFS에서 재귀호출과정을 분석 => 초기화 코드 추가로 해결하였다.
• 모든 경우의 수 DFS => 자리값 초기화

내 풀이

‚‘‘‘ import java.util.; import java.lang.;

class Solution { public static int count;

public int solution(String numbers) {

    String[] arr = numbers.split("");    
    int n = arr.length; 
    int r = arr.length; // max
    boolean[] visited = new boolean[n];
    String[] output = new String[r];

// String과같은 참조형 변수 초기값이 null Arrays.fill(output,"");

    Set<Integer> set = new HashSet<Integer>();

    //1. 모든 경우의 수를 만든다.
    perm(arr,output,visited, 0, n, r, set);

    Iterator<Integer> it = set.iterator();

    while (it.hasNext()) {
        int num = it.next();
        if(!(num==0||num==1)&& isPrime(num)){
                     count++;
        };
    }

    return count;
}  

static boolean isPrime(int num){

 //(어떤 수 N의 양의 제곱근 이하의 수들로 N을 나눠서 한 번이라도 나누어떨어지면 합성수, 아니면 소수)
 boolean result = true;
 int p = (int)(Math.sqrt(num));
 for(int i=2; i<=p; i++){
      if(num%i==0){
         result = false;
         break;
       }

}

  return result;

}

static void perm(String[] arr, String[] output, boolean[] visited, int depth, int n, int r, Set<Integer> set ) {

// 여기서 검증 작업 // output을 join하여 parseInt 후 if(depth!=0){ int num = Integer.parseInt(String.join("",output));

   //중복되는 수 제거 (011=11) => Set 활용
     set.add(num);

}

if (depth == r) {
    return;
}

for (int i=0; i<n; i++) {
    if (visited[i] != true) {
        visited[i] = true;
        output[depth] = arr[i];
        perm(arr, output, visited, depth + 1, n, r, set);       

//perm 끝내고 여기로 돌아왔을때는 depth를 i번째 숫자(arr[i])로 설정한 모든 숫자를 완성한 상황. //다음 i번째 숫자로 depth번째 수를 새롭게 설정할 것이므로 방금 사용한 i번째 숫자는 안쓴 것으로 설정.
visited[i] = false; // 방금 채운 depth자리값 초기화 output[depth]=""; } } } }‘‘‘

느낀점

사실 DFS 재귀(의 호출과정)를 이해하지 않은 상태에서 문제를 풀다가 막혔던 것이 가장 컸다. 그래서 하나씩 정리하다가 현 상황에서는 설정한 depth자리의 값을 초기화하는 과정이 반드시 필요함을 알게된거고.. 이것때문에 느낀게 많다.

• 역시 단편적으로 이해하고 외우면 응용을 못하게됨 ㅎ. 특정 코드 로직의 어디에 해당하는지 알아야함. 한끗차이로 문제 맞고 틀리고 엄청 갈림.
• 문제 조건도 풀면서 안까먹게 반드시 정리.
• 문제에서 예제로 준 case는 엄청난 힌트임. 각 예제가 어떤 case인지 “추상적 정의” 필요. ( 반드시 출제자는 다른 케이스의 예제를 준다. 같은 케이스의 예제는 never 없다. )
• 그리고.. 복잡한 원리 이해에는 그냥 직접 하나씩 순서대로 써가면서 이해하는게 왕도임. ( 가장 빠른 방법. 회피하면 이렇게 됨.. ) 할때 여러가지 경우 고려하면서.. 예를 들어 여기선 2개 뽑는 경우도 해보고 3개인 경우도 해봐야 코드가 모든 경우에 적용될 수 있는지 (일반화된 코드인지)를 알 수 있음 (이거때문에도 개고생. r을 2로 잡았을때는 초기화를 n==r 일때 하는 걸로 착각함. )

다른 사람 풀이

모든 경우의 수를 만들때 ‘주어진 String을 어떻게 처리했는지’가 좀 다른듯하다. 나머지 핵심적인 부분에서 사용한 개념은 동일한듯. 사실 자료형을 다루는 것이 매번 쉬운일은 아니다. 기초와 센스가 부족하면 오히려 이것을 처리하느라 시간을 보낼수도 있으니..

https://programmers.co.kr/learn/courses/30/lessons/42747

시도한 아이디어 1

정렬한뒤 매 자리에 끼워 넣어서 왼쪽 갯수 가 끼워 넣은 자리 앞 >= 왼쪽갯수 >= 뒷 자리 이면 ...

뭔가 복잡하다. 구현도 어떻게 해야할지 모르겠다. 다른방법을 생각하기로 함.

시도한 아이디어 2

내가 제한할 수 있는 것부터 생각했다. 그것은 논문 갯수.

일단 커봤자 논문 갯수(h)다. 첫번째 경우는 논문 갯수가 5인데 그렇다면 맨끝에 위치해야한다. 하지만 왼쪽의 0보다 5는 크므로 탈락.

4: 6 5 3 1 < (4) 0 => X 3: 6 5 3 >= (3) >= 0 => O

오.. 이걸 발전시키기로 한다.

해결한 방법

위의 아이디어를 추상화시킨다.

           6 5 3 1 0

비교대상: 1 2 3 4 5 length - i - 1 번째 수와 수 length - i 를 비교 ( i =0,1,2... ) 다른 케이스에도 적용해보면... 7 8 0 9 7 3 => 9 8 7 7 3 0 1 2 3 4 5 6

따라서 해결방법을 아래처럼 하기로 했다.

1. 내림차순 정렬한다.
2. for(int i=0; i<array.length;i++){ if(length- i-1 번째 수 >= 수 length - i ){ return (수 length-i) } }

하지만 여기서 굳이 내림차순을 사용해야하나 싶었다. int 배열을 내림차순하려면 Integer로 바꿔야하거나, ArrayList로변경해야하므로 번거롭다.

내림차순 안한경우, 0 3 7 7 8 9 6 5 4 3 2 1 —> 이방향으로 진행하면 된다.

이에 맞게 1을 생략하고 2의 코드를 조금 변경해준다.

내 풀이

‘’’ import java.util.; import java.lang.;

class Solution { public int solution(int[] citations) { int answer = 0;

    //1.  정렬한다.

    Arrays.sort(citations);



    //2. 
for(int i=0; i<citations.length; i++){
    if(citations[i] >= (citations.length - i)) { 
                answer = (citations.length-i);
        break;
       } 

}

    return answer;
}

} ‘’’

느낀점

처음에 모든 인용횟수가 0인 경우를 고려를 안했는데 코드 작성하다가 이 예외경우를 생각하고 다시 코드를 짰다. 이제 예외 케이스를 의식적으로 고려하게 된 것 같다.

또 굳이 내림차순을 해야하나? 로 좀 더 코드양을 줄이고 효율적인 방법을 찾으려고 반문하는 자세.. 칭찬해...

근데 이렇게 아이디어가 중요한 싸움인데 이번 일주일동안 생각한 아이디어를 코딩테스트에서 한시간안에 떠올릴수 있을까..? ㅠ

https://programmers.co.kr/learn/courses/30/lessons/42746

시도한 방법

모든 배열을 돌면서 가장 큰 자리수의 값을 key로 하고, 그 값을 리스트인 value에 add하여 HashMap을 만든다.

value의 리스트들의 값을 모든 경우의 수로 조합하여 가장 큰 값을 만든다. ( 모든 경우의 수 : 시간복잡도 계산해봐야함 )

n * (n-1) * ... * (n - (n-1)) * 1 = n^n n에 numbers의 최대길이인 100000을 입력하니 Infinity가 나옴... ㅋㅋㅋㅋ

key값을 기준으로 내림차순 정렬한다.

만든 큰 값들을 내림차순한 순서대로 읽어서 조합하여 수를 만든다.

compare( o1, o2) 함수에서 o1을 현재값, o2를 비교하는 값으로 간주 양수 반환 : o1값이 크다 == o1을 뒤로 가도록 정렬 = [ o2, o1 ]

다음자리를 계속 비교하는 대신에, 길이가 긴 숫자에 맞춰 짧은 숫자의 자릿수를 맞추고, 그 숫자들을 비교한다. 같은경우, 3 30 330 긴 자리의 숫자와 바로 앞자리 비교 3 36 363

로직이 더러운게.. 뭔가 잘못됐다고 생각함.

해결한 방법

배열 정렬시, 순서 정하는 방법을 아래와 같이 함.

둘이 자리 바꿔서 [6, 10, 2] 6 10 -> 610 > 106 6 2 -> 62 > 26 10 2 -> 102 < 210

6 > 2 > 10

[3, 30, 34, 5, 9] 3 > 30 3 < 34 3 < 5 3 < 9

30 < 34 30 < 5 30 < 9

34 < 5 34 < 9

5 < 9

9 > 5 > 34 > 3 > 30

compare ( a , b ) { if(ab > ba) return -1; ....

기본적으로 자바는 오름차순이기 때문에 큰 수가 앞에 오도록 하기위해서는 -1을 반환.

내 풀이

import java.lang.Integer; import java.util.*;

class Solution { public String solution(int[] numbers_input) { String answer = "";

    Integer[] numbers = Arrays.stream(numbers_input).boxed().toArray( Integer[]::new );

    //numbers : [6,2,10]
    Arrays.sort(numbers, new Switching());
    // "6210"
    //answer = String.join(numbers,"");

    StringBuffer sb = new StringBuffer();

    for(int i=0; i<numbers.length; i++){
        //answer += numbers[i];
        sb.append(numbers[i]);
    }

    answer = sb.toString();

    // 원소 값이 "모두" 0 일때 
    //  [0, 0, 0, 0, 0] => "0"
    //if(Integer.parseInt(answer) == 0) return "0";
    if(answer.toCharArray()[0] == '0' ) return "0";
    return answer;

}

}

class Switching implements Comparator{ @Override public int compare(Integer a, Integer b){ int ab = Integer.parseInt(a+""+b); int ba = Integer.parseInt(b+""+a);

    if(ab > ba) return -1; // 큰수가 앞으로 가야하므로 descending 형태 
    if(ba > ab) return 1;
    return 0;

}

}

후기

• Comparator는 int 과 같은 기본형 대신 Integer을 사용해야 했다. 이때 나는 Arrays.sort를 사용하기 위해 int[] => Integer[] 관련 코드를 썼는데 이는 상당히 복잡하다. 하지만, Collections.sort를 쓴다면 List \ <Integer >에 int[]의 값들을 담아 Collections.sort ( List, Comparator... ) 로 간단히 사용할 수 있다.
• 처음에 0000 인 경우를 고려하지 못했다.
• 0000 인 경우를 잡아내기 위해 Integer.parseInt를 썼는데 0000 인 경우만 빼고는 런타임에러가 났다.

느낀점

예전에 못풀었던 문제인데 정렬을 사용한 아이디어 덕에 풀 수 있었다. 여러 수가 아닌, 정렬 로직에서 ( compare(a, b) ... ) 사용될 단 2개의 수만 고려하면 되는 것이었다.

다른 알고리즘 문제들을 풀면서 재귀가 활용되는 것을 많이 보았다. 또한, 하노이의 탑은 내가 코딩테스트를 처음 준비할때부터 만났던 문제이고 재귀를 모르는 상태에서는 전혀 손대기 어려워서 이번에 재귀 개념을 잡을겸 다른사람의 풀이를 보고 문제를 풀어봤다.

하노이의 탑

문제

https://programmers.co.kr/learn/courses/30/lessons/12946

접근방법

참고한 풀이

https://shoark7.github.io/programming/algorithm/tower-of-hanoi (접근방법이 정말 자세하고 명쾌하다.. 짱이신듯)

풀이

문제 정의 : N개의 원반을 모두 3번으로 옮겨라 (최소횟수)

여기서 최소횟수가 중요한 것이 아니다. 이미 문제에서 최소횟수 구하는 로직은 기술해놨고 우리는 그것을 어떠한 규칙을 가진 함수로 만들어서 코드를 작성하면 된다.

3개의 원반이 주어졌다고 하자. 문제에서 주어진 해결과정을 세 파트로 나눌 수 있다.

1. 1의 3개 원반을 3으로 모두 옮기기 위해서는 먼저 A,B 원반을 2번으로 옮겨야한다. (3을 거쳐서)
2. C 원반을 3번으로 옮긴다.
3. 2에 있는 A,B 원반을 3으로 옮긴다. (1을 거쳐서)

이를 수식으로 나타내보자.

Hanoi ( N=3, from=1, to = 3 ) = Hanoi ( N=2, from=1, to = 2 ) +move ( N=1, from =1, to = 3 ) +Hanoi ( N=2, from=2, to = 3 )

여기서 Hanoi와 move를 구분한 이유는 1,3은 한번에 옮길수 없어 거쳐서 옮기는 것이고 2는 한번에 옮기기 때문이다.

이것을 추상적인 식으로 일반화해보자.

Hanoi ( N, from, to , via ) = Hanoi ( N-1 , from, via ) +move ( N-2, from, to ) +Hanoi ( N-1, via, to )

** N을 갯수로 정의할수도 있지만 N번째 원반이라고 정의할수도 있다. 이를 반영하면... ( N개를 옮기는 것은 결국 제일 밑에 있는 N번째 원반을 옮기는 것 )

( 사실 여기서 N-2가 나온것에 동공지진.. 당황했었는데 위와 같이 정의하면 깔끔해졌다 .. 다른 항(?)이 나오는 것 최소화하는 것이 좋은듯.. )

따라서 다시 정리하면...

Hanoi ( N, from, to , via ) = Hanoi ( N-1 , from, via , to ) +move ( N, from, to ) +Hanoi ( N-1, via, to , from )

이로써 재귀함수를 사용하여 문제를 정의하게 되었다.

마지막으로, 재귀 호출에서 가장 중요한 것은 무한(?)호출을 멈추는 break 조건이다.

만일 Hanoi 함수에서 N번째 원반을 옮기는 것은 move 함수와 같을 것이다.

Hanoi ( N, from, to , via ) = move ( N, from, to ) ( if N==1 )

이로써 문제는 다 풀었다. 끝. 이 아니라.. 제출은 해야하므로..

문제에서 요구하는 결과값 만들기

이제 문제에서 결과값으로 요구하는 것이 무엇인지 살펴보자.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

| n | result | | 2 | [ [1,2], [1,3], [2,3] ] | | 3 | [ [1,3] , [ 1,2],[3,2] ,[1,3] ,[2,1] ,[2,3], [1,3]]|

위와 같이 원반을 옮길때 마다, 어디서(from) 어디로 (to) 옮겼는지를 결과로 제출하면 되는 문제다.

우리는 move 함수를 이용해 요구하는 형식대로 결과를 완성하면 된다!

완성한 move 함수는 어떤 원반이 이동했는지 까지도 정보을 담고 있으므로 문제가 무엇을 요구하든 문제없다.

여기까지는 괜찮았다.. 그런데.. 자바코드를 작성하는데 예상치못하게 애를 먹었다.. (기초 문법 및 개념 부족.. )

코드

import java.util.ArrayList;

class Solution {

    //public int[][] result = new int[][];
    public static ArrayList<int[]> result = new ArrayList<>();
    //public static int i = 0 ; 

    public int[][] solution(int n) {

        hanoi(n,1,3,2);

        int[][] answer = new int[result.size()][2]; //size has private access in ArrayList

        for(int i = 0 ; i < result.size(); i++){
            answer[i] = result.get(i);
        }

        return answer;
    }

    public static void move(int n, int from, int to){
        int[] movement = {from, to};
        //result[i++] = movement;
        result.add(movement);
    }

    public static void hanoi(int n, int from, int to, int via){

        if(n == 1){
            move(n, from, to);
            return;
        } 

        hanoi(n-1, from, via, to);
        move(n, from, to);
        hanoi(n-1, via, to, from);

    }
}

내가 위 코드를 작성하기 까지 직면한 문제들은 아래와 같다.

1) 2차원 배열 개념 다 까먹음 (int[3][2]가 [int[2],int[2],int[2]] 인 것을 몰랐음..)
2) ArrayList 개념 ( size는 속성이 아니라 size() 메서드로 접근해야함 / ArrayList <-> 배열 변환 )
3) 접근제어자 public , static ( 같은 클래스내 메서드 및 변수 참조에 static 빼먹음 )

꾸역꾸역 검색을 통해 완성했지만.. 실제 코딩테스트에서는 이런 지식들을 찾아볼 수 없고 , 이를 떠나 자바 개발자로서 기본 문법은 반드시 숙지해야하므로... 문법 제대로 공부하길.. ( ArrayList랑 배열 변환은 언제까지 검색할건데..? )

마무리하며

• 다른 사람 풀이를 보며 느낀점..

이제껏 문제를 잘못 풀고 있었다는 생각이 든다. 문제가 요구하는 형식을 어떻게 맞출 것인가에 집중했는데 참고한 풀이에서는 문제의 핵심 원리를 파악하고 문제를 풀면 그 안에서 문제가 요구하는 결과값을 충분히 찾아낼 수 있었다.

근데 이 부분은 문제를 좀 더 풀어봐야 알것 같다. 이 문제는 정말 딱 ‘재귀’라는 핵심 개념이 존재하고 답도 반드시 이것을 이용해서 풀어야하기 때문이다.

무슨 방법을 쓰든 문제를 푸는 것 자체가 중요한지, 좋은 알고리즘이 있다면 그것을 적극 이용해서 푸는 것이 중요한지.. ( 뭐지 벌써 답이 나온거같은... ㅋㅋㅋ ) ( 면접 시험가서도 문제 못풀어도 아 이거 oo 개념으로 풀면 될것같습니다. 라고 하는게 어거지로 for문 돌려서 푸는것보다 합격가능성이 높을지도? )

• 코드를 작성하며 느낀점..

알고리즘을 Java 코드로 작성하면서 자바 문법 기초가 부족함을 깨달았다. 다시 책보면서 문법이랑 개념정리 좀 하고 기초를 소홀히 하면 안되겠다.

메서드

• add : 객체를 큐에 저장
• poll : 큐에서 객체를 꺼내 반환
• peek : 삭제 없이 큐의 요소를 읽어 반환. 비어있으면 null을 반환.
• offer
• remove
• element

클래스

큐를 구현한 클래스들이 많다. LinkedList가 대표적이고, 우선순위큐 (PriorityQueue)는 코딩테스트에서 자주 출제되는 것으로 안다.

프린터

문제

https://programmers.co.kr/learn/courses/30/lessons/42587

내 풀이 및 접근방법

코드

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {

        int result = 0;

        //index Queue 생성
        Queue<Integer> indexQueue = new LinkedList<>();
        Queue<Integer> taskQueue = new LinkedList<>();

                                                            //내림차순
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());



        for(int i=0; i < priorities.length; i++){
           int addedNum = (i == location? 1 : 0);
            indexQueue.add(addedNum);
            taskQueue.add(priorities[i]);

            priorityQueue.add(priorities[i]);


        }
        int cnt = 0;
        while(taskQueue.peek() != null){
            int peeked = taskQueue.poll();
            int peekedIndex = indexQueue.poll();
         if( peeked == priorityQueue.peek()){
             cnt++;
             priorityQueue.poll();
             if(peekedIndex == 1){
                 //return cnt;
                 result = cnt;
                 break;
             }
         }else{ // peeked < max 일 경우 (priorityQueue.peek() 은 항상 max 이므로)
            taskQueue.add(peeked);
            indexQueue.add(peekedIndex);
         }   
    }
        // i : 0 
        // t : 1
        // p : 1 
        //cnt : 5

        return result;

    }//method
}//class

접근방법

indexQueue ( location에 해당하는 값인지 참조용 ) taskQueue priorityQueue ( 최대값 참조용 )

이렇게 3개를 두고 품

주어진 로직을 따라가기위해서 priorityQueue를 사용했고 문제의 값을 return하기 위해서 indexQueue를 사용함.

이거 두개에 대한 아이디어를 찾는것이 힘들었고 자료구조가 Queue라는 것을 인식하는 것은 크게 문제가 되지 않았다.

다른사람 풀이

코드

https://programmers.co.kr/learn/courses/30/lessons/42587/solution_groups?language=java

접근방법

내 풀이에서 고민했던 2가지에 대한 접근방법을 달리했다.

indexQueue ( location에 해당하는 값인지 참조용 ) => Class를 이용 priorityQueue ( 최대값 참조용 ) => Arrays.sort( priorities )

새로운 큐를 만들 필요 없이, 각각 클래스를 사용하고 주어진 배열을 활용하면 되는 문제였다.

그밖에 출력 순서를 return 할때 cnt++를 이용한다는 점 등은 동일했다.

프린터

문제

https://programmers.co.kr/learn/courses/30/lessons/42583?language=java

내 풀이 및 접근방법

코드

import java.util.*; 

class Solution {
    public int solution(int bridge_length, int max_weight, int[] truck_weights) {
        int answer = 0;
        Queue<Truck> bridge_queue = new LinkedList<Truck>();
        //현재 다리의 무게 
        // add remove에 따라 
        int bridge_weight = 0;
        int i = 0;
        //누적시간
        int time = 1 ;

        boolean isExceed ;

        while(i < truck_weights.length){ 

            isExceed = false;

            //add 작업
            int truck_weight = truck_weights[i];
            // 넣었을때 초과하지않는경우 add
            if( bridge_weight + truck_weight <= max_weight){
                //맨 마지막 트럭인 경우 
                if(i == (truck_weights.length - 1) ){

                    //마지막 트럭이 다리를 통과하는 시간  
                    int last_truck_pass_time = time + bridge_length;
                    answer = last_truck_pass_time;
                    break;
                }


                isExceed = true;
                bridge_queue.add(new Truck(truck_weight, time));
                i++;
                bridge_weight+=truck_weight;

                //여기서 time은 다음 트럭의 시간임 
                time++;

            } 


                                                //초과하는 경우, 맨 앞에 있는 트럭이 빠지는 시간에 다시 진입 시도                
                time = (isExceed? time : bridge_queue.peek().start_time + bridge_length);

                if(bridge_queue.peek()!=null){
                    if(time ==  (bridge_queue.peek().start_time + bridge_length)) {
                        bridge_weight -=  bridge_queue.peek().weight;
                        bridge_queue.remove();
                    }
                }




        }

        //모든 트럭을 다리에 건너도록 한 이후

        // 현재 다리에 있는 모든 트럭들이 다리를 모두 건널때의 시간 return


        return answer;
    }
}
class Truck{
    int weight;
    int start_time;
    public Truck(int weight, int time){
       this.weight = weight;
        this.start_time = time;
    }
}

접근방법

truck을 돌면서 넣었을때 초과하지않는 경우, bridge queue에 add 초과하는 경우, 맨 앞에 있는 트럭이 빠지는 시간으로 변경 후 다시 add 시도

결과값은 마지막 트럭이 지나는 시간 ( == 마지막 트럭의 대기시간 + bridge의 length )

다른사람 풀이

코드

https://programmers.co.kr/learn/courses/30/lessons/42583/solution_groups?language=java

접근방법

truck_weight도 queue를 사용한다. 트럭의 start_time 대신 move 개념을 사용하였고, moving 메서드를 사용해서 이동하도록 하는 개념이 새로웠다.

로직이 깔끔함.

• 모든 트럭들을 한칸씩 이동시키고
• 빼야할 트럭은 빼고 (remove)
• 더해야할 트럭을 더하는 (add)

나는 더하고 빼는 과정에서 먼저하고 뒤에 하면서 하나씩 싱크가 안맞는 경우가 있었는데, 위 코드의 경우에는 위 과정을 한번의 반복에 시행해 단순하게 구현해서 그러한 문제가 발생하지 않음.

대신 시간 효율성은 내것이 더 좋지 않나 싶다.

내 코드 ) 테스트 9 〉 통과 (1.03ms, 53.3MB) 다른사람 코드 ) 테스트 9 〉 통과 (8.60ms, 52.7MB)

비교하자면 내 코드는 시간에, 다른 사람의 코드는 공간에 집중한 느낌이다.

마무리하며

프린터

이 문제는 오직 ‘자료구조’로서 큐를 사용하고 있을뿐.. 문제 푸는 핵심 아이디어가 큐인건 아님. ( 핵심 아이디어가 문제풀이력의 핵심 ). 다시 풀어볼만한 문제인듯하다.

다리를 지나는 트럭

이 문제 역시 자료구조로서 큐를 사용할뿐이다. 결국 모든 문제에서 가장 중요한 것은,

사용한 언어의 특성 활용 + 문제 해결 아이디어

가 아닐까.. ( 자바에서는 클래스 활용하는 것 등.. )

메서드

자바에서 Stack은 별도 클래스로 제공된다. 관련 메소드는 아래와 같다.

• empty : 스택이 비어있는지 여부를 boolean 으로 반환
• peek : top에 있는 객체를 반환 (꺼내지는 않음)
• pop : top의 객체를 읽고, 스택에서 꺼낸다
• push : 객체를 저장하고 이를 반환
• search : 인자로 전달 받은 객체의 위치를 반환. ( 0이 아닌 1부터 시작. 못찾으면 -1 )

스택의 활용

• 문자열 역순으로 정렬하기
• 괄호 검사하기
• 후위 표기법

괄호 검사하기

• 여러개의 괄호를 동시에 사용할때, 괄호의 종류와 열고 닫는 순서가 맞는다는 뜻
• 검사 방법 : 수식을 하나씩 돌면서 여는 괄호면 push, 닫는 괄호면 pop해서 괄호의 종류를 확인

괄호사용의 틀린예 3가지

• ( A + B ) * C )
• (( A + B ) * C
• { ( A + B } ) * C

열린 괄호 갯수 != 닫힌 갯수 인 경우는 스택에 괄호가 남아 있거나(>), Pop을 해야하는 상황에서 괄호가 없는(<) 경우이다.

스택에서 push, pop만큼이나 중요한 것이 스택이 비어있는지 이므로 코딩할때 신경써야한다.

후위표기법

컴퓨터가 계산할 수 있도록 표기하는 방법이다.

A + ( B * C )

후위표기법으로 표현하면 아래와 같다.

A B C * +

A B C 를 읽고 * 를 만나면 앞의 2 글자인 B C를 연산하고, + 를 만나면 이 계산 값과 앞의 1 글자를 읽어 연산한다.

스택을 활용하면, 피연산자를 만나면 push하고 얀산자를 만나면 앞의 2글자를 pop하여 연산한 뒤 결과를 다시 push하면 된다

문제 풀이

위의 활용에서 접근했던 방식과 다른 방향으로 풀어야하는 문제들이 오히려 많았다.

주식가격

문제

https://programmers.co.kr/learn/courses/30/lessons/42584

내 풀이 및 접근 방법

관점 차이임. 나는 현재 시점에서 미래 시점을 순회하며 작은 수가 있는지 확인. 스택을 사용하면 현재시점에서 과거시점을 순회하며 큰 수가 있는지 확인. 과거시점의 가격 지속시간을 계산함. 과거의 것은 계속 스택으로 쌓으면서 최신 것, 즉 peek 만 확인하면 되고, peek가 현재보다 크면 ( 현재 가격이 떨어진 것이면 ) peek(과거)의 지속시간 기록. 또 peek 뽑아서(pop) ( 더 과거 ) 현재보다 크면 내가 떨어진 시점인 현재와 비교해서 지속시간 기록. 즉, 내가 떨어진 시점인 과거의 시점을 찾아서 지속 시간 기록하기.

여기서 stack을 적용하는 포인트는, 비교해야할(혹은 기록해야할) 과거의 시점을 스택에 쌓고, 가장 최신의 과거 (peek)를 계속 확인하는 것. 기면 pop 아니면 본인을 push한뒤 다음

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];

      for(int i=0; i<prices.length; i++){
    int price = prices[i];
    int j = i+1;
    int cnt = 0 ;
        while(j!= prices.length ){
            cnt++;    
               if(prices[j] >= price){

                j++;

                }else{
                break;
                }



  }
            answer[i]=cnt;

}


        return answer;
    }
}

기능 개발

문제

https://programmers.co.kr/learn/courses/30/lessons/42584

내 접근 방법 및 코드

주식가격 문제의 관점을 적용하고자 했다.

import java.util.*; 

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] answer ;
        int[] time = new int[progresses.length];
        ArrayList<Integer> deploy = new ArrayList<>();
        //time 
        for(int i=0; i<progresses.length; i++){
            int progress = progresses[i];
            int speed = speeds[i];
            time[i] = (100-progress)/speed;
// 빼먹어서 테스트 통과 못했던 부분 
if((100-progress) % speed != 0){
                time[i]++;
            }
        }

        Stack<Integer> stack = new Stack<>();

        int j = 0;

        for(int i=0; i<time.length; i++){
            if(i==0||stack.peek()<time[i]){
                stack.push(time[i]);
                deploy.add(1) ;
            }else{
                int cum = deploy.get(deploy.size()-1);
                deploy.set(deploy.size()-1, cum + 1 );
            }
        }

        answer = new int[deploy.size()]; 

        int size=0;

for(int temp : deploy){

  answer[size++] = temp;

}

        return answer;

    }
}

카카오 문제가 스토리도 있고 재밌는거 같아서 파기 넘치게 도전했다.

문제

https://programmers.co.kr/learn/courses/30/lessons/60060

내 풀이

내가 생각한 풀이

• 정렬한다. (fro로 시작하는 오름차순. 만일 a,b 모두 fro로 시작한다면 문자열 길이순 오름차순 )
• 이분탐색을 이용하여 조건을 만족( fro로 시작 && 문자열 길이 일치 )하는 최초의 문자열 발견하면 문자열 기준으로 뒤와 앞을 돌면서 조건 만족하는 문자열의 시작과 끝 지점 찾기 ( end Index - start Index + 1)개

결과적으로 기본 예제 테스트만 통과하고 낙방.

일단 정확성 테스트는 아래처럼 쉽게 생각해서 플 수 있다.

https://rok93.tistory.com/m/entry/프로그래머스-가사-검색-2020-KAKAO-BLIND-RECRUITMENT-문제-4번

내 목표는 정확성 테스트 통과였는데 너무 어렵게 생각한 것 같다.

그리고 효율성 테스트를 통과하기 위해서는 ‘트라이’라는 자료구조를 써야한다고 한다.

마치며

처음부터 해설을 보고 ‘이분탐색’ 문제로 생각해서 그런지 굉장히 어렵게 생각했다. 실제로 난이도도 높은 문제였고. 이제부터는 레벨 2정도 난이도의 문제를 풀기로 했다. 이번주는 알고리즘 공부를 시작했다는 것에 의의를 두는 것으로 ^^ 다음주는 이변이 없다면 스택 문제를 풀 예정이다.

JUnit을 이용하여 서비스 객체를 테스트할 일이 생겼다. 모든 빈을 등록하도록 스프링 컨테이너를 로드하기위해 아래와 같이 스프링 관련 설정을 읽어오도록 해야한다.

@RunWith(SpringJUnit4ClassRunner.class)
@ContextConfiguration({"classpath:/applicationContext.xml"})
@WebAppConfiguration
public class ServiceTest {

내가 겪었던 어려움은    &nbsp1. classpath가 뭐지?    &nbsp2. 됐고 test 클래스에서 resources 하단의 파일을 어떻게 불러오지? 이 두가지였다.

이 두가지에 대한 해답을 얻기 위해 모은 자료들과 내가 이해한 내용을 공유하려 한다.

classpath란?

먼저, 자바에서 특히 java 이외의 파일들의 경로를 지정할때

classpath:...

라는 표현을 많이 보았을 것이다.

*classpath란 빌드시 컴파일된 class 파일들의 위치 경로이다. *

모든 컴파일된 클래스와 자원들은 classPath 하단에 생성되고 여기서 경로를 찾아야한다.

주의해야할 점은, 절대 이클립스에 보이는 구조가 아니라는 것이다. 예를 들어, '저는 src/main/resources에 있는 txt파일에 접근해서 자바 코드로 수정했는데 이클립스에서 해당문서가 변경이 안되었어요' 라고 물을 수 있다. 답은 '당연하다'. 그건 classPath 내의 txt파일을 변경한 것이므로 이클립스에서는 안보인다. 직접 파일경로를 찾아가서 확인해야 한다. (참고로 이클립스의 경우 또 별도의 classPath를 가지고 있다.)

classpath를 확인하는 방법은 다양하며, 나는 이 방법으로 확인하였다.

프로젝트파일명\target\classes

대부분 찾아보면 위와 같이 설정되어 있을 것이다.

정리하면, classpath는 패키지 계층구조의 '최상위 경로' 인 것이다. (이외에도 jar 파일을 인식하는 경로로 사용되기도 한다.)

예를 들어 output/org/javaguy/coolframework/MyClass.class 를 import org.javaguy.coolframework.MyClass; 라고 불러 올 수 있는 이유는 classpath가 /home/..../output 이라고 설정되어 있기 때문이다.

resources 자원의 경로

그래서 java 패키지 내에서 클래스가 아닌 자원들 ( 컴파일 대상이 아닌 이미지, xml 등 설정문서 )에 접근하기 위해서는 경로를 어떻게 설정해줘야 할까?

먼저, 우리는 .java 파일이 있는 패키지가 아니라 컴파일된 .class 파일들이 있는 경로에서 해당 파일들을 찾아야 한다. ( 당연히 코드가 컴파일 될때 컴파일된 위치에서 타 자원을 찾아야한다. ) 따라서 이클립스에서 패키지 모양을 보지말고 얼른 하단의 src/main/java 폴더로 내려온다.

resources파일을 인식하기 위해서는 ClassPathResource 와 같은 유틸 라이브러리를 많이 사용한다.

ClassPathResource resource = new ClassPathResource("config.xml")

위처럼 자원의 경로를 지정해줘야 하는데, 이때 쓰이는 몇가지 방식이 있다.

• 절대경로, 상대경로 사용 x : "resources/config.xml"
• 접두사 사용
  • "file : src/main/resources/config.xml"
  • "classpath : config.xml"

첫번째와 같이 .나 /를 쓰지않는 경우는 기본적으로 src/main/webapp 하위를 탐색한다.

classpath 는 기본경로가 src/main/java, src/main/resources 이다. 따라서 이 두 경로의 하위를 탐색한다.

file은 기본경로가 현재 프로젝트의 폴더이다.

배포시에는 경로가 달라진다. 자세한 내용은 참고 문서를..

classpath에 대한 정보는 프로젝트 폴더내의 .classpath에서 확인할 수 있다. 이를 보면 classpath에 대한 이해에 도움이 된다.

<?xml version="1.0" encoding="UTF-8"?>
<classpath>
   <classpathentry kind="src" output="target/classes" path="src/main/java">
      <attributes>
         <attribute name="optional" value="true"/>
         <attribute name="maven.pomderived" value="true"/>
      </attributes>
   </classpathentry>
   <classpathentry excluding="**" kind="src" output="target/classes" path="src/main/resources">
      <attributes>
         <attribute name="maven.pomderived" value="true"/>
      </attributes>
   </classpathentry>
   <classpathentry kind="src" output="target/test-classes" path="src/test/java">
      <attributes>
         <attribute name="optional" value="true"/>
         <attribute name="maven.pomderived" value="true"/>
         <attribute name="test" value="true"/>
      </attributes>
   </classpathentry>

classpath는 기본 entry가 src/main/java, src/main/resources로 잡혀있고, 빌드 결과인 output은 target/classes에 저장된다.

test시 resources 자원의 경로

test를 할때는 classpath가 다르게 잡힌다. src/test/java 하위에 테스트 클래스가 위치해야 한다. 위의 xml파일의 마지막을 보면 path가 src/test/java인 별도의 classpath가 있다. 즉, test 클래스에서 "classpath:" 라는 표현을 쓰면 이는 기본적으로 src/test/java의 하위에서 파일을 탐색한다.

하지만 우리가 탐색하고 싶은 resource 파일은 src/main의 하위에 있으므로, "file: "을 사용하는 것이 가장 편리하다. 또는classpath라는 표현을 쓰고 싶다면 src/test하위에 resources 폴더를 생성하여 해당 폴더 하위에 기존의 resource 파일을 위치시켜서 참조할 수 있도록 한다.

결국 file 접두어를 써서 junit 테스트를 성공적으로 진행할 수 있었다.

package com.sph.cms.biz.mail.service;
@RunWith(SpringJUnit4ClassRunner.class)
@ContextConfiguration({"file:src/main/resources/contexts/applicationContext.xml", "file:src/main/resources/contexts/dbDataSourceContext.xml", "file:src/main/resources/contexts/dbMybatisContext.xml"})
@WebAppConfiguration
public class MyBatisTest4 {
   @Autowired
   public MailDao mailDao ;

   @Test
   public void test() {

      try {
         List<String> resultList  = mailDao.getCompanyEmailList();
         System.out.println(resultList);
      } catch (Exception e) {
         e.printStackTrace();
      }
   }


}

src/test/java에서 작성된 클래스는 본인과 패키지 구조가 대응되는 java 패키지 및 클래스를 참조한다. 예를 들어, src/test/java/com.abc.biz에 작성된 클래스는 src/main/java/com.abc.biz에 작성된 config 클래스를

@ContextConfiguration(classes="config.class")

위 처럼 표현하여 불러올 수 있다.

하지만 보통은 자원파일은 별도로 위치하므로 우리가 의도하던 바는 아니니 참고만 하자.

참고 : java — 클래스 패스 란 무엇이며 어떻게 설정합니까?

마무리하며

포스팅하는데에 엄청 오래걸렸다.. 원래 이런건가.. 하지만 정리하다보니 포스팅 직전까지도 불확실했던 부분을 잘 알게되어서 기쁘다. 앞으로 포스팅 속도도 점점 나아지겠지.. ㅜㅜ