쌉쌀한 무화과의 개발로그

[문제 설명]

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.

ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

​

<제한 사항>

name은 알파벳 대문자로만 이루어져 있습니다.

name의 길이는 1 이상 20 이하입니다.

​

<입출력 예>

>문제 풀이

조이스틱을 상하 좌우로 움직여서 입력받은 String name을 최소로 몇 번 만에 만들 수 있는지 구해야합니다.

이 문제는 최소한의 좌우 조작 횟수를 어떻게 구할지가 관건이었습니다.

만약 "BBBAAB" 의 경우에 BBBAAB -> BBBAAB 이와 같은 순서로 움직일 때 최소 횟수가 나옵니다.

​

근데 이 문제가 테스트 케이스가 좀 부족하다고 느낀게 위에 제가 예시로 든 "BBBAAB"의 경우 답이 8이라고 생각되는데, 9로 출력되는 코드의 경우에도 채점을 통과합니다.

그래서 풀어놓고도 풀이하는데 오래 걸린 것 같습니다..ㅎㅎ.;;ㅜ

​

입력받은 name에 A가 포함되어 있다면 A가 가장 긴 부분을 기준으로 좌우 조작을 하는게 최소값이 나올 것으로 생각했는데, 이경우

1) 오른쪽으로 쭉 갔다가 "AA~A"를 만나면 다시 index=0으로 돌아오고, 뒤로 가서 "AA~A"를 만난다.

2) 뒤로 가서 "AA~A"를 만나면 다시 index=0로 돌아오고, 오른쪽으로 가서 "AA~A"를 만난다.

두가지 방법이 있습니다.

즉 name.length()-1 / 1번 / 2번 중에 최소값이 좌우조작의 최소횟수 인거죠.

*근데 문제의 테스트 케이스에는 1번 2번에 대해 처리가 달라도 정답이 되는 것 같습니다.

(제가 문제를 잘못 이해한 건가요.. 일단 내일 일어나서 다시 살펴봐야 할 것 같습니다.)

​

+수정하겠습니다.) 문제를 다시 읽어보니까 ◀:커서가 왼쪽으로 이동할 때, 첫번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서 라는 조건은 있지만, ▶:커서가 오른쪽으로 이동할 때, "마지막 위치에서 오른쪽으로 이동하면 첫번째 문자에 커서"라는 조건은 없습니다!

즉, "BBBAAB" 의 경우에 BBBAAB -> BBBAAB 이와 같은 순서로 움직일 때 최소 횟수가 나옵니다. (=9회)

​

◀ 왼쪽 화살표의 조건을 읽고 오른쪽도 같은 조건이라고 생각했었네요...(역시 정신이 똘망똘망 할 때 풀어야하나 봅니다..ㅎㅎ)

>전체 코드

import java.util.*;
class Solution {
    public int solution(String name) {
        int answer = 0;
        char d;
        
        for(int i=0; i<name.length(); i++){
            d= name.charAt(i);
            answer+=Math.min(d-'A', Math.abs('A'+26-d));
        }
        
        int minlen= name.length()-1;
        int end, cnt;
        for(int i=0; i<name.length(); i++){
            if(name.charAt(i)=='A') continue;
            end= i+1;
            while(end<name.length()&&name.charAt(end)=='A'){
                end++;
            }
            cnt=i*2+(name.length()-end);
            minlen= Math.min(minlen, cnt);
        }
        
        return answer+minlen;
    }
}

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

[문제 설명]

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

​

[제한 사항]

numbers의 길이는 1 이상 100,000 이하입니다.

numbers의 원소는 0 이상 1,000 이하입니다.

정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

​

<입출력 예>

>문제 풀이

문제의 숫자가 꼭 한자릿수만 나오는게 아니기 때문에 잘 생각해야합니다.

예를 들어 만약 10, 6 의 경우 610> 106 이기 때문에 마냥 배열을 오름차순으로 정렬할 수 없습니다.

그래서 숫자를 정렬할 때 comparator을 써서 10 과 6을 붙여본 결과를 비교하여 오름차순으로 정렬 했습니다. 106과 610을 비교한 결과로 정렬을 하는 것이죠.

        Arrays.sort(str, new Comparator<String>(){ //정렬하기
            public int compare(String o1, String o2){
                return -(o1+o2).compareTo(o2+o1);
            }
        });

>전체 코드

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        String[] str= new String[numbers.length];
        
        int j=0;
        for(int i: numbers){
            str[j++]= String.valueOf(i);
        }
        
        Arrays.sort(str, new Comparator<String>(){
            public int compare(String o1, String o2){
                return -(o1+o2).compareTo(o2+o1);
            }
        });
        
        for(String i: str){
            answer+=i;
        }
        
        for(int i=0; i<answer.length(); i++){
            if(answer.charAt(i)!='0'||i==answer.length()-1){
                answer= answer.substring(i);
                break;
            }
        }
        
        return answer;
    }
}

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

[문제 설명]

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

​

<제한사항>

입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.

각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.

심사관은 1명 이상 100,000명 이하입니다.

​

<입출력 예>

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

>문제 풀이

( 수학이든 알고리즘이든 안하면 까먹는다고,, 이분탐색을 너무 오랜만에 풀어본 것 같습니다.)

​

n이 10억까지 들어올 수 있기 때문에 범위에 주의해야합니다.

간단하게 n이 10억이고 심사관은 1명 이며 3초씩 걸릴 경우, 30억의 시간이 걸립니다.

int의 범위는 -2,147,483,648 ~ 2,147,483,647 라서 범위 초과가 발생합니다.

​

이제 min=0; max= (long)times[times.length-1]*n; sum=0; min=0; 선언

mid 시간 안에 심사관들이 심사할 수 있는 인원수(sum)을 n과 비교하여 min 또는 max값을 조정해가며 이분탐색을 해줍니다.

>전체 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        Arrays.sort(times);
        long min= 0;
        long max= (long)times[times.length-1]*n;
        long mid=0, sum;
        answer=max;
        
        while(min<=max){
            sum=0;
            mid= (min+max)/2;
            for(int i: times){
                sum+=mid/i;
            }
            if(sum>=n){
                if(mid<answer){
                    answer=mid;
                }
                max=mid-1;
            }else{ //sum<n
                min=mid+1;
            }
        }
        
        return answer;
    }
}

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