[프로그래머스] 2018 하반기 공채 대비 코딩테스트 실전 모의고사 1회

2018 하반기 공채 대비 코딩테스트 실전 모의고사 1회

생각

프로그래머스에서 진행한 2018 하반기 공채 대비 코딩테스트 실전 모의고사 1회를 풀어보았다.

총 3개의 문제가 주어지며, 꼬아져있는 문제는 없었다.

1. 팰린드롬(palindrome) 만들기

앞으로 읽을 때와 뒤로 읽을때가 똑같은 단어를 팰린드롬이라고 한다. 두 자연수 n,m이 주어졌을 때 n이상 m이하의 자연수 중 팰린드롬인 숫자의 개수를 return 하여라.

프로그래머스 스타일을 제대로 안 읽은 것일 수도 있지만 백준이나 SW Expert에서 풀때처럼 제한 사항이 적혀있지는 않았다.

▶ 코드를 제출하면 제약 사항을 테스트는 하지만 기준은 모르겠다(못 본걸수도 있다)

m이 최대 50만 까지이므로 n이 1이라고 치면 총 50만개의 숫자를 살펴보면 되므로 반복문은 숫자를 찾는데 필요한 시간 복잡도는 O(N)일 것이며, 팰린드롬을 체크하는데 필요한 반복분은 십만 단위일 경우 6자리이므로 3번만 살펴보면 된다. 따라서 이부분은 아주 조그마하므로 시간 복잡도는 O(N)이라 할 수 있을 것 같다.

▶ 이런 테스트가 처음이라 먼가가 숨겨져 있을 줄 알고 1의 자리 10의 자리 100의자리를 따져가며 규칙을 찾아보려 했지만 잘 보이지 않아서 제한 사항을 알 수는 없었지만 위와 같이 50만이 최대이므로 모든 수를 살펴보면서 풀이를 하였다.

2. 조선소에서 최소한으로 배상비용을 낼 수 있도록 하여라!

일할 수 있는 시간 N과 일이 담긴 works 배열을 준다. 이때, 1시간마다 한 가지 일을 -1씩 처리할 수 있으며 N시간 동안 진행한다. N 시간동안 작업을 진행후 남아있는 일들을 제곱하여 더하였을 때, 최소값을 출력해라.

"모든 문제는 문제를 잘 읽어야 답을 도출 할 수 있다" 라는 사실을 알려주는 문제라 생각한다. 이번 모의고사중 가장 까다로웠던 문제가 아니였나 싶다.

▶ "문제 속에 답이있다" 예제로 주어진 케이스를 보면 작업량이 제일 많을 때를 -1 시키고있다. 어떻게보면 숫자가 클 수록 제곱을 하였을 때, 많이 커지기 때문에 당연히 제일 큰 숫자를 -1 해주는게 맞겠지만 예제가 없었다면 쉽게 떠올랐을까 라는 생각이 든다.

▶ 이제 문제는 다음이다. 배열에서 항상 제일 큰 숫자를 찾아서 -1을 시켜줘야 한다. 처음 시도는 Arrays.sort() 메소드를 통해서 works 배열을 계속 정렬해주어 맨 뒤의 Index의 값을 -1 해주었다.

▶ N이 최대 1,000,000이고 배열의 크기가 최대 1000이므로 위와 같은 시도는 비효율 적일 것이고, 제출했을 때도 효율성 테스트는 0점을 일반 케이스도 몇 개는 실패를 얻었다.

▶ 항상 최대값을 찾아서 -1을 해주고 다시 최대값을 찾는게 관건이므로 PriorityQueue를 사용해서 내림차순 Comparator를 통해 내림차순 정렬하였다.

▶ PriorityQueue는 이진 트리 구조를 가지고 있고, 내림차순 정렬을 통해 최대값이 항상 queue의 꼭 대기에 있으므로 배열 전체를 정리하는 것보다 빠른 결과를 얻을 수 있다.

▶ 이제 문제를 다 풀었다고 생각했었지만(효율성 통과) 일반 케이스에서 2개가 실패를 하였다. 곰곰히 생각해보니 N이 클경우 배열의 값들이 0을 넘어 음의 값으로 갈 수도 있었다. 결과는 제곱을 해서 제출하므로 음의 값을 가질 경우 잘 못된 결과 값을 갖게된다. 따라서 -1을 해주었을 때 0이하가 되면 해당 값을 제거하였다.

*이미 테스트 끝내기를 눌러서 시도해 볼 수는 없지만 맨 처음 한 번만 정렬하고 그 max값을 저장해두고 그 값과 비교해가며 찾는것도 나쁘진 않을 것 같다.*

3. 버스정류장 돌기!

N개의 버스정류장이 주어졌을 때, 각각의 정류장에서 출발해서 각각의 정류장으로 갈 수 있으면 1 그렇지 않으면 0을 가지고 있는 N*N 배열을 return 하여라.

"백준에서 본듯한 문제인데?"라고 생각했었는데 끝나고 예전 글을 보니 이 문제 였다. [백준] 11403번 경로 찾기 

문제의 설명을 위의 링크에서 볼 수 있다. 여기서는 피드백만 해보아야겠다.

▶ 이번에 작성한 코드와 비교를 해보니 더 간단해졌나!? 생각이 들었지만 백준은 입력을 받아 출력도 해야했고, 프로그래머스에서는 입력 값을 매개변수를 통해 주고, 출력값도 return으로 배열을 넘겨주면 되니 더 간단해 보였던것 같다.

▶ 확실히 많이 풀어본 사람이 비슷한 문제(이 경우는 똑같은 문제)를 접하였을 때 빨리 풀 수 있는것 같다 실제 시험을 볼 때까지 많이 풀어봐야 겠다.

코드

1)

class Solution {
    public int solution(int n, int m) {
        int answer = 0;
        int len = 0;
        boolean flag = true;
        for(int i=n;i<=m;i++) {
            String t = i+"";
            len = t.length();
            flag = true;
            for(int j=0;j<len;j++) {
                if(t.charAt(j)!=t.charAt(len-j-1)) {
                    flag = false;
                    break;
                }
            }
            if(flag) answer++;
        }
        return answer;
    }
}

2)

import java.util.Comparator;
import java.util.PriorityQueue;
 
class Solution {    
    public int solution(int no, int[] works) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1<o2?1:o1==o2?0:-1;
            }
        });
        int len = works.length;
        for(int i=0;i<len;i++)
            queue.add(works[i]);
        int result = 0;
        for(int i=0;i<no;i++) {
            if(queue.isEmpty()) break;
            int t = queue.poll()-1;
            if(t<=0) {
                len--;
                continue;
            }
            queue.add(t);
        }
        
        for(int i=0;i<len;i++) {
            int t = queue.poll();
            result += Math.pow(t, 2);
        }
 
        return result;
    }
}

3)

class Solution{
    int[][] solution(int n, int[][] signs){
        int[][] answer = new int[n][n];
        
        for(int i=0;i<n;i++)
            solve(n,i,i,signs,answer);
        return answer;
    }
    
    // 경로만 찾으면 되므로 dfs를 이용.
    private void solve(int n,int first,int next,int[][] signs,int[][] answer) {
        for(int i=0;i<n;i++) {
            if(signs[next][i]==0) continue;
            if(answer[first][i]!=0) continue;
            answer[first][i] = 1;
            solve(n,first,i,signs,answer);
        }        
    }
}