[2018 KAKAO] 셔틀버스

제출일 : 2020-08-29

문제 풀이 시간 : 2H 30M

---

link : https://programmers.co.kr/learn/courses/30/lessons/17678

문제 설명

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

입력 형식

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

• 0 ＜ n ≦ 10
• 0 ＜ t ≦ 60
• 0 ＜ m ≦ 45
• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
• 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

출력 형식

콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

입출력 예제

문제 풀이 접근

문제를 풀며 꽤나 시간이 많이 걸렸습니다.

처음에 작성한 코드는 주어진 테스트 케이스는 맞지만 체점결과 1개의 케이스가 실패하여 처음부터 코드를 작성하였습니다.

도착시간을 우선순위 큐에 담고 버스가 도착하는 시간에 탑승하는 인원을 확인하고 현재 도착한 셔틀버스를 타기 위한 가장 늦은 시간을 구하는 방식으로 문제를 접근하여 풀었습니다. 22번 테스트케이스가 어떠한 것인지 자꾸 실패하였고 예외를 계속 코딩하다보니 코드가 너무 지저분해지기만 해 코드를 버리고 새로 작성하였습니다.

저는 우선순위큐를 사용했지만 다른 사람들의 풀이를 보니 대부분 String배열을 정렬하여 문제를 해결한것을 보고 나는 왜 이렇게 간단하게 생각하지 못했나 하는 생각을 했습니다.

아래의 코드는 모든 시간에 셔틀버스를 탄 사람들을 각각 다 저장하고 뒤에서부터 탐색하여 빈자리가 있다면 셔틀버스가 오는 시간이 가장 늦은 시간이 되고 빈자리가 없다면 앞사람보다 1분 빨리 도착하는 경우를 구했습니다.

코드

언어 : JAVA

package Programmers.kakao;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class kakao2018_4_셔틀버스 {
    public static void main(String[] args) {
        System.out.println(solution(1, 1, 5, new String[] { "08:00", "08:01", "08:02", "08:03" }));
        System.out.println(solution(2, 10, 2, new String[] { "09:10", "09:09", "08:00" }));
        System.out.println(solution(2, 1, 2, new String[] { "09:00", "09:00", "09:00", "09:00" }));
        System.out.println(solution(1, 1, 5, new String[] { "00:01", "00:01", "00:01", "00:01", "00:01" }));
        System.out.println(solution(1, 1, 1, new String[] { "23:59" }));
        System.out.println(solution(10, 60, 5, new String[] { "23:59", "23:59", "23:59", "23:59", "23:59", "23:59",    "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59" }));
    }

    public static String solution(int n, int t, int m, String[] timetable) {

        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0])
                    return o1[1] - o2[1];
                return o1[0] - o2[0];
            }
        });
        for (int i = 0; i < timetable.length; i++) {
            StringTokenizer st = new StringTokenizer(timetable[i], ":");
            pq.add(new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) });
        }

        int H = 9, M = 0;
        int[][][] bus = new int[n][m][2];
        int[][] time = new int[n][2];
        for (int k = 0; k < n; k++) {
            time[k][0] = H;
            time[k][1] = M;
            int cnt = 0;
            for (int i = 0; i < m; i++) {
                bus[k][i][0] = -1;
            }
            while (cnt < m && !pq.isEmpty()) {
                int[] now = pq.peek();
                if (now[0] < H || (now[0] == H && now[1] <= M)) {
                    bus[k][cnt] = pq.poll();
                    cnt++;
                } else
                    break;
            }
            // 시간 증가
            H = (M + t >= 60) ? H + 1 : H;
            M = (M + t >= 60) ? M + t - 60 : M + t;
        }

        for (int k = n - 1; k >= 0; k--) {
            for (int i = m - 1; i >= 0; i--) {
                if (bus[k][i][0] == -1)
                    return String.format("%02d:%02d", time[k][0], time[k][1]);

                if (i > 0 && bus[k][i - 1][0] == bus[k][i][0] && bus[k][i - 1][1] == bus[k][i][1])
                    continue;

                if (bus[k][i][1] - 1 < 0)
                    return String.format("%02d:%02d", bus[k][i][0] - 1, 59);
                else
                    return String.format("%02d:%02d", bus[k][i][0], bus[k][i][1] - 1);

            }
        }
        return "";
    }
}

[2018 KAKAO] 캐시

제출일 : 2020-08-28

문제 풀이 시간 : 15M

---

link : https://programmers.co.kr/learn/courses/30/lessons/17680

문제 설명

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력 형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력 형식

• 입력된 도시이름 배열을 순서대로 처리할 때, 총 실행시간을 출력한다.

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

입출력 예제

문제 풀이 접근

우선 LRU에 대한 개념이 있어야 문제를 해결할 수 있습니다.

여기서 간단하게 설명하자면 LRU는 페이지 교체 알고리즘으로 가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘입니다.

저는 이를 큐를 사용하여 구현하였습니다.

최근에 사용되어 값이 큐에 저장되어 있는지 contain()을 이용하여 확인하였고 remove()를 이용하여 값을 제거하고 add()를 사용하여 큐에 가장 마지막 위치에 해당 값을 위치하도록 하였습니다.

이렇게 한다면 큐의 첫번째 값은 가장 오랫동안 사용하지 않은 값이 있게 되며 값이 존재하지 않을때 값을 추가하고 캐시의 크기보다 큐의 크기가 클경우 맨앞의 값을 꺼내왔습니다.

문제를 보면 대소문자를 구분하지 않는다고 명시되어 있습니다. 따라서 모든 도시의 이름을 소문자로 치환하여 문제를 해결하였습니다.

코드

언어 : JAVA

package Programmers.kakao;

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

public class kakao2018_3_캐시 {
    public static void main(String[] args) {
        System.out.println(solution(3, new String[] { "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo",
                "Seoul", "NewYork", "LA" }));
        System.out.println(solution(3,
                new String[] { "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul" }));
        System.out.println(solution(2, new String[] { "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco",
                "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome" }));
        System.out.println(solution(5, new String[] { "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco",
                "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome" }));
        System.out.println(solution(2, new String[] { "Jeju", "Pangyo", "NewYork", "newyork" }));
        System.out.println(solution(0, new String[] { "Jeju", "Pangyo", "Seoul", "NewYork", "LA" }));
    }

    public static int solution(int cacheSize, String[] cities) {
        int answer = 0;
        Queue<String> q = new LinkedList<>();

        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toLowerCase();
        }
        for (int i = 0; i < cities.length; i++) {
            if (q.contains(cities[i])) {
                q.remove(cities[i]);
                q.add(cities[i]);
                answer++;
            } else {
                q.add(cities[i]);
                if (q.size() > cacheSize) {
                    q.poll();
                }
                answer += 5;
            }
        }
        return answer;
    }
}

[2018 KAKAO] 다트게임

제출일 : 2020-08-28

문제 풀이 시간 : 30M

---

link : https://programmers.co.kr/learn/courses/30/lessons/17682

문제 설명

카카오톡에 뜬 네 번째 별! 심심할 땐? 카카오톡 게임별~

카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다.
갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다.

1. 다트 게임은 총 3번의 기회로 구성된다.
2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다.
4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
5. 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
6. 스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
7. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.

0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

입력 형식

점수|보너스|[옵션]으로 이루어진 문자열 3세트.
예) 1S2D*3T

• 점수는 0에서 10 사이의 정수이다.
• 보너스는 S, D, T 중 하나이다.
• 옵선은 *이나 # 중 하나이며, 없을 수도 있다.

출력 형식

3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다.
예) 37

입출력 예제

문제 풀이 접근

입력으로 주어진 문자열을 점수|보너스|[옵션]의 형식으로 쪼개기만 하면 쉽게 문제를 해결할 수 있습니다.

저는 3개의 세트가 입력으로 들어오기 때문에 for문을 이용하여 3번 반복을 하였고 i값을 인덱스로 사용하였습니다.

문제를 풀며 주의해야하는 부분은 점수가 0~10점까지 주어지기 때문에 2개의 자리수가 점수일 경우를 고려해야 합니다.

코드

언어 : JAVA

package Programmers.kakao;
import java.util.Arrays;

public class kakao2018_2_다트게임 {
    public static void main(String[] args) {
        System.out.println(solution("1S2D*3T")); // 37
        System.out.println(solution("1D2S#10S")); // 9
        System.out.println(solution("1D2S0T")); // 3
        System.out.println(solution("1S*2T*3S")); // 23
        System.out.println(solution("1D#2S*3S")); // 5
        System.out.println(solution("1T2D3D#")); // -4
        System.out.println(solution("1D2S3T*")); // 59
    }

    public static int solution(String dartResult) {
        int[] score = new int[3];
        char[] bonus = new char[3];
        char[] option = new char[3];

        int i = 0;
        for (int k = 0; k < 3; k++) {
            // 각 기회마다 얻을 수 있는 점수는 0~10
            score[k] = dartResult.charAt(i++) - '0';
            if (dartResult.charAt(i) == '0') {
                score[k] *= 10;
                i++;
            }

            // 보너스는 SDT 중 하나
            bonus[k] = dartResult.charAt(i++);

            // 옵선은 *이나 # 중 하나이며, 없을 수도 있다.
            if (i < dartResult.length() && (dartResult.charAt(i) == '*' || dartResult.charAt(i) == '#')) {
                option[k] = dartResult.charAt(i++);
            }
        }

        for (int k = 0; k < 3; k++) {
            if (bonus[k] == 'D')
                score[k] = score[k] * score[k];
            else if (bonus[k] == 'T')
                score[k] = score[k] * score[k] * score[k];

            if (option[k] == '*') {
                score[k] *= 2;
                if (k > 0)
                    score[k - 1] *= 2;
            } else if (option[k] == '#') {
                score[k] *= -1;
            }
        }
        return score[0] + score[1] + score[2];
    }
}

[2018 KAKAO] 비밀지도

제출일 : 2020-08-28

문제 풀이 시간 : 30M

---

link : https://programmers.co.kr/learn/courses/30/lessons/17681

문제 설명

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ) 또는벽(#") 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도 1과 지도 2라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. 지도 1과 지도 2는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

입력 형식

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

• 1 ≦ n ≦ 16
• arr1, arr2는 길이 n인 정수 배열로 주어진다.
• 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.

출력 형식

원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

입출력 예제

문제 풀이 접근

주어진 배열을 비트연산하고 값을 2진수로 변환하여 1을 #으로 0을 공백으로 변환하여 값을 리턴하여 문제를 해결하였습니다.

반환해야 하는 String 배열을 생성하고 입력받은 배열을 OR(|)연산을 수행한 후에 Integer.toBinaryString()를 이용아여 2진수 형식으로 바꾸어 주었습니다. 또 변환된 값의 길이가 n보다 작을 수 있기 때문에 String.format()를 이용하여 자리수를 고정하고 replaceAll()을 이용하여 문자를 치환하여 문제를 해결하였습니다.

비트연산으로 문제를 해결해야 한다는 접근은 어렵지 않았으나 Integer.toBinaryString()과 String.fomat(), replaceAll()등 사용빈도가 적은 함수들을 사용해 보았다면 더욱 쉽게 문제를 해결할 수 있을 것이라 생각합니다.

코드

언어 : JAVA

package Programmers.kakao;
import java.util.Arrays;

public class kakao2018_1_비밀지도 {
    public static void main(String[] args) {
        System.out.println(
                Arrays.toString(solution(5, new int[] { 9, 20, 28, 18, 11 }, new int[] { 30, 1, 21, 17, 28 })));
        System.out.println(Arrays
                .toString(solution(6, new int[] { 46, 33, 33, 22, 31, 50 }, new int[] { 27, 56, 19, 14, 14, 10 })));
    }

    public static String[] solution(int n, int[] arr1, int[] arr2) {
        String[] result = new String[n];
        for (int i = 0; i < n; i++) {
            result[i] = Integer.toBinaryString(arr1[i] | arr2[i]);
        }

        for (int i = 0; i < n; i++) {
            result[i] = String.format("%" + n + "s", result[i]);
            result[i] = result[i].replaceAll("1", "#");
            result[i] = result[i].replaceAll("0", " ");
        }

        return result;
    }
}

키패드 누르기

제출일 : 2020-07-27

문제 풀이 시간 : 30M

---

:link: 문제 link

문제 설명

스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.

이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.

1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
2. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
3. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
4. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
   4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• numbers 배열의 크기는 1 이상 1,000 이하입니다.

• numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.

• hand는

  "left"

또는

  "right"

입니다.

• "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.

• 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.

입출력 예

입출력 예에 대한 설명

입출력 예 #1

순서대로 눌러야 할 번호가 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5]이고, 오른손잡이입니다.

따라서 "LRLLLRLLRRL"를 return 합니다.

입출력 예 #2

왼손잡이가 [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2]를 순서대로 누르면 사용한 손은 "LRLLRRLLLRR"이 됩니다.

입출력 예 #3

오른손잡이가 [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]를 순서대로 누르면 사용한 손은 "LLRLLRLLRL"이 됩니다.

문제 풀이 접근

배열을 정렬하는 방법을 재정의 하여 문제를 해결하였다.

만약 3과 30이란 값이 들어오게 된다면

3+30과 30+3을 비교하여 정렬하게 되는데 이때는 330이 303보다 크기 때문에 3은 30 보다 큰 수가 되는 것이다. 값을 내름차순으로 정렬하여 앞에서 부터 문자열을 이어 붙여주면 정답이 된다.

문제 풀이 접근

문제에서 주어진 조건을 읽고 로직을 구현하는 문제로 처음 왼쪽과 오른쪽 손의 위치가 주어지고 위치에서

1. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
2. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
3. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
   4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

좌표의 위치를 Point배열을 이용하여 저장하고 가운데 2,5,8,0의 숫자를 입력할때 Math.abs(R.x - nums[num].x) + Math.abs(R.y - nums[num].y); 와 같이 거리를 구하고 가까운쪽의 손가락으로 누르게 된다. 만약 갚이 같다면 주어진hand의 손으로 누르게 되며

이를 StringBuilder에 추가해 결과를 출력하였습니다.

코드

언어 : JAVA

package Programmers;

import java.awt.Point;

public class Kakao2020_키패드누르기 {
    public static void main(String[] args) {
        System.out.println(solution(new int[] { 1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5 }, "right"));
        System.out.println(solution(new int[] { 7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2 }, "left"));
        System.out.println(solution(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }, "right"));
    }

    private static String solution(int[] numbers, String hand) {
        Point[] nums = new Point[10];
        nums[0] = new Point(3, 1);
        nums[1] = new Point(0, 0);
        nums[2] = new Point(0, 1);
        nums[3] = new Point(0, 2);
        nums[4] = new Point(1, 0);
        nums[5] = new Point(1, 1);
        nums[6] = new Point(1, 2);
        nums[7] = new Point(2, 0);
        nums[8] = new Point(2, 1);
        nums[9] = new Point(2, 2);
        Point L = new Point(3, 0);
        Point R = new Point(3, 2);

        StringBuilder sb = new StringBuilder();
        for (int num : numbers) {
            if (num == 1 || num == 4 || num == 7) {
                L.x = nums[num].x;
                L.y = nums[num].y;
                sb.append("L");
            } else if (num == 3 || num == 6 || num == 9) {
                R.x = nums[num].x;
                R.y = nums[num].y;
                sb.append("R");
            } else {
                int disL = Math.abs(L.x - nums[num].x) + Math.abs(L.y - nums[num].y);
                int disR = Math.abs(R.x - nums[num].x) + Math.abs(R.y - nums[num].y);
                if (disL == disR) {
                    if (hand.equals("right")) {
                        R.x = nums[num].x;
                        R.y = nums[num].y;
                        sb.append("R");
                    } else {
                        L.x = nums[num].x;
                        L.y = nums[num].y;
                        sb.append("L");
                    }
                } else {
                    System.out.println(disL + " " + disR);
                    if (disR < disL) {
                        R.x = nums[num].x;
                        R.y = nums[num].y;
                        sb.append("R");
                    } else {
                        L.x = nums[num].x;
                        L.y = nums[num].y;
                        sb.append("L");
                    }
                }
            }
        }
        return sb.toString();
    }
}

[Programmers] K번째수 - (Java)

Problem

제출일 : 2020-05-15

문제 풀이 시간 : 5M

난이도 : ★

---

link : https://programmers.co.kr/learn/courses/30/lessons/42748

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

Solution & Inpression

정렬 문제

Arrays.copyOfRange(original, from, to) 사용하여 문제를 풀어도 되지만 리스트를 사용하여 문제를 해결하였습니다.

Code

언어 : JAVA

package Programmers;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

public class Level1_K번째수 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution(new int[] { 1, 5, 2, 6, 3, 7, 4 },
                new int[][] { { 2, 5, 3 }, { 4, 4, 1 }, { 1, 7, 3 }, }))); // [5,6,3]
    }

    public static int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        for (int i = 0; i < commands.length; i++) {
            LinkedList<Integer> list = new LinkedList<>();
            for (int j = commands[i][0] - 1; j < commands[i][1]; j++) {
                list.add(array[j]);
            }
            Collections.sort(list);
            answer[i] = list.get(commands[i][2] - 1);
        }

        return answer;
    }
}

[Programmers] 체육복 - (Java)

Problem

제출일 : 2020-05-15

문제 풀이 시간 : 10M

난이도 : ★

---

link : https://programmers.co.kr/learn/courses/30/lessons/42862

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

Solution & Inpression

그리디 문제!!

• 잃어버린 사람이 앞사람에게 먼저 물어보고 없으면 뒷사람.

문제 의 조건 중 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 에 유의 하여 문제를 풀면 된다.

Code

언어 : JAVA

package Programmers;

public class Level1_체육복 {
    public static void main(String[] args) {
        System.out.println(solution(5, new int[] { 2, 4 }, new int[] { 1, 3, 5 })); // 5
        System.out.println(solution(5, new int[] { 2, 4 }, new int[] { 3 })); // 4
        System.out.println(solution(3, new int[] { 3 }, new int[] { 1 })); // 2
    }

    public static int solution(int n, int[] lost, int[] reserve) {
        int[] student = new int[n];
        for (int i = 0; i < lost.length; i++) {
            student[lost[i] - 1]--;
        }
        for (int i = 0; i < reserve.length; i++) {
            student[reserve[i] - 1]++;
        }

        int answer = n;
        for (int i = 0; i < student.length; i++) {
            if (student[i] == -1) {
                if (i - 1 >= 0 && student[i - 1] == 1) {
                    student[i]++;
                    student[i - 1]--;
                } else if (i + 1 < student.length && student[i + 1] == 1) {
                    student[i]++;
                    student[i + 1]--;
                } else
                    answer--;
            }
        }
        return answer;
    }
}

[Programmers] 모의고사 - (Java)

Problem

제출일 : 2020-05-11

문제 풀이 시간 : 20M

난이도 : ★★

---

link : https://programmers.co.kr/learn/courses/30/lessons/42840

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

입출력 예 설명

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.

Solution & Inpression

간단한 문제로 다음의 단계로 문제를 해결하였습니다.

1. 각각의 사람들이 문제를 찍는 패턴을 배열에 저장한다.
2. %연산자를 이용하여 각각의 사람들이 맞춘 문제의 수를 카운팅한다.
3. 맞춘 문제의 수의 최대값을 구한다.
4. ArrayList를 이용하여 맞춘 문제의 수가 최대값과 같은 인원을 구한다.
5. list의 값을 배열에 저장하여 리턴한다.

Code

언어 : JAVA

package Programmers;

import java.util.ArrayList;
import java.util.Arrays;

public class Level1_모의고사 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution(new int[] { 1, 2, 3, 4, 5 }))); // 1
        System.out.println(Arrays.toString(solution(new int[] { 1, 3, 2, 4, 2 }))); // 1, 2, 3
    }

    public static int[] solution(int[] answers) {
        int[] p1 = { 1, 2, 3, 4, 5 };
        int[] p2 = { 2, 1, 2, 3, 2, 4, 2, 5 };
        int[] p3 = { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 };
        int[] cnt = new int[3];
        for (int i = 0; i < answers.length; i++) {
            int now = answers[i];
            if (p1[i % p1.length] == now)
                cnt[0]++;
            if (p2[i % p2.length] == now)
                cnt[1]++;
            if (p3[i % p3.length] == now)
                cnt[2]++;
        }
        int max = Math.max(Math.max(cnt[0], cnt[1]), cnt[2]);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] == max)
                list.add(i + 1);
        }
        int[] answer = new int[list.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}