항해 같은 팀인 지성님이 주신 문제

[제한사항]

• 이미 값이 채워진 인덱스에는 또 다시 같은 값을 채우지 않는다. 

[입출력 예]

[1,2,3,4,5,6,7,8,9,10,11,12, .... 44,45]

추측) 

배열 개수가 정해져있고 들어가야하는 숫자 또한 1부터 45까지의 나열이기 때문에 인덱스가 0부터 시작임을 생각해 임의의 정수값에 -1을 적용해 인덱스를 잡고 값을 집어넣는다. 집어넣기 전에 해당 자리가 int배열의 디폴트 값인 0이 아니면 값은 집어 넣지 않으면 될 거 같다. 

소스코드) 

import java.util.*;

public class chap01 {
    public static void main(String[] args) {

        int[] flag_arr = new int[45];
        while(true) {
            int randomNum = (int) (Math.random() * 45 + 1);
            if (flag_arr[randomNum - 1] != randomNum) {
                flag_arr[randomNum - 1] = randomNum;
            }

            int cnt = 0;
            for (int one : flag_arr) {
                if (one == 0) {
                    cnt++;
                }
            }

            if (cnt == 0) {
                break;
            }
        }
        System.out.println(Arrays.toString(flag_arr));
    }
}

리뷰) 

일단 생각한대로 코드 작성함에 있어서 루프문을 멈추는 부분에 대해서도 필요함을 깨달았다. 알고리즘을 막 시작해서 그런가 아직 문제를 풀면서 고려해야할 점을 많이 놓치고 있다는 생각이 든다. 만들기 전에 구체적으로 생각할 수 있는 연습이 필요하다는 생각이 들었다.

또한 무한 루프문 안에 또 for문이 너무 많이 돌아가는 게 아닌가 하는 생각이 든다. 이걸 줄일 수 있는 방법이 없을까?  

flag에 관련된 거라고 하셨는데 공부하려니 키워드를 뭐로 검색해야할지 모르겠다. 

보통 flag하면 boolean 값으로 토글처럼 사용하는 방식만 나오는데 ㅠ

[제한사항]

• N의 범위 : 100,000,000 이하의 자연수

[입출력 예]

추측) 

숫자를 문자열로 만들어 각각 잘라 배열을 만든다! 이를 for문으로 하나씩 꺼내 숫자화 시키고 변수하나에 합산시키면 될 듯하다.

소스코드) 

public class Solution {
    public int solution(int n) {
        int answer = 0;

        String a = Integer.toString(n);
        String[] s_arr = a.split("");

        for(int i=0; i<s_arr.length; i++){
            answer += Integer.parseInt(s_arr[i]);
        }

        return answer;
    }
}

리뷰) 

추측한 대로 결과를 도출하는데 성공했다. 다른 풀이도 보면 형변환없이 10으로 나누어 일의 자리수, 십의 자리수 등 순서대로 뽑아내 각각 더하는 방식도 있었고 심지어 숫자를 문자열화하고 배열로 변환해 아스키코드를 이용한 방법도 있었다. 

+ 아스키 코드로 푸는 방식이 너무 신기해서 추가

mport java.util.*;

public class Solution {
    public int solution(int n) {
        int answer = 0;

        char[] arr = Integer.toString(n).toCharArray();

        for(int i = 0; i < arr.length; i++){
            answer += arr[i] - 48;
        }

        return answer;
    }
}

여기서 for문 안에 있는 arr[i]를 풀면 9,8,7 들이 출력되는데 이상태로 더하면 24가 아니라 168이 나온다.

왜냐면 출력되는 9,8,7은 숫자가 아니라 char 타입의 문자이기 때문! 따라서  char타입은 int와 연산을 하면 int로 바뀜

각각 9 문자는 57, 8은 56, 7은 55의 int값이 되며 여기서 숫자 9,8,7이 되게 하기 위해서 -48의 값을 연산하게 된 것이다.

알고리즘을 푸는 방법이 이렇게 다양할 수 있구나 싶고 다른 사람들의 다양한 방법을 접하면서 생각을 많이 넓혀보고 싶다는 생각이 든다. 

[제한사항]

• arr은 자연수를 담은 배열입니다.
• 정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 입니다.
• divisor는 자연수입니다.
• array는 길이 1 이상인 배열입니다.

[입출력 예]

추측) 

일단 for문으로 array에서 값을 하나하나 출력하여 divisor 값으로 나누어 나머지가 0이 되는 것을 다시 배열에 넣어 반환하면 될 것 같다. 배열의 길이가 0이라면 그 배열에 -1를 넣어주고, 배열을 다시 오름차순으로 정렬하면 원하는 대로 결과를 도출할 수 있을거 같다.

소스코드) 

import java.util.*;

class Solution {
    public int[] solution(int[] arr, int divisor) {
        ArrayList<Integer> arr1 = new ArrayList<Integer>();

        for(int i=0; i<arr.length; i++){
            if(arr[i]%divisor == 0){
                arr1.add(arr[i]);
            }
        }

        if (arr1.size() == 0){
            arr1.add(-1);
        }
        
        arr1.sort(Comparator.naturalOrder());
        
        int[] answer = new int [arr1.size()];
        for(int j=0; j<arr1.size(); j++){
            answer[j] = arr1.get(j);
        }
        
        answer.sort();
        
        return answer;
    }
}

리뷰) 

자바의 기본 배열은 이미 선언된 배열에 길이를 더하여 데이터를 넣는 것이 안된다. 그래서 찾아보니 ArrayList 클래스로는 데이터를 원하는대로 추가하는게 가능했다. ArrayList의 길이를 구하는 것 역시 달라 size()라는 ArrayList 메소드를 사용한다.

for문을 통해 divisor로 나눠지는 것을 ArrayList에 추가하고 size가 0이 나온경우는 -1를 데이터로 넣어주었다.

기본 배열과 ArrayList는 다르므로 답으로 배열로 반환하기 위해 ArrayList를 다시 배열로 바꿔주는 과정이 필요했다.for문을 통해 값을 하나씩 이동시킨다.  그리고 최종적으로 배열을 정렬하며 답을 반환한다.

+ 위에서는 배열을 정렬했지만 ArrayList를 정렬하는 방법도 있다

: arr1.sort(Comparator.naturalOrder()); 

+ 제한사항

• 정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 입니다. (배열 안에 동일한 값이 없다는것)

[제한사항] 

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

[입출력 예]

추측) 

참가자의 for문에서 한명한명 이름 값을 완주자의 for문으로 넣어 비교하는 중첩 for문을 사용하면 될거 같다. 

카운트 변수를 둬서 동일 인물이 있다면 카운트를 올리고 없다면 0이 되어 0인 참가자를 출력하면 될 듯 하다.

소스코드) 

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        
        String answer = "";
        
        Arrays.sort(participant);	// 참가자 명단 정렬
        Arrays.sort(completion);	// 골인한 사람 명단 정렬
        
        for(int i=0; i<completion.length; i++){		// 골인한 사람 명단을 기준으로 for문을 돌린다
            if(!participant[i].equals(completion[i])){	// 앞에서 정렬했기 때문에 같은 인덱스를 비교한다 
                answer = participant[i];	// 같은 인덱스에 이름이 달라졌다면 동명이인이 발견된 것 답에 넣는다.
                break;
            }
            answer = participant[participant.length - 1];	// if를 거치지 않았다면 하나를 뺀 모든 인덱스가 같다. 마지막 1인 한명이 바로 골인못한 사람이므로 출력
        }       
        return answer;
    }
}

리뷰) 

추측한 방법으로는 동명이인을 가릴수 없었다. 그래서 다시 생각해봐야했다. 

규리님이 정렬을 이용해 푸셨다는 것을 듣고 코드를 작성해봤다. 

참가자와 완주자를  같은 방법으로 정렬한다. 그리고 같은 인덱스를 비교하다보면 이름이 안맞는 순간이 온다.

(참고로 배열 길이가 다를때 긴 쪽을 기준으로 동일하게 비교하면 ArrayIndexOutOfBoundsException이 발생한다.)

완주를 실패한 사람이 단 한명인 상황에서 이름이 안맞는 순간이라는 건 동명이인이 있어 같은 인덱스끼리의 이름이 달라진것! 달라진 그때의 참가자의 이름을 출력하면 그 사람이 바로 완주하지 못한 사람이다.

또한 배열을 계속 비교하면서 이름이 달라지는 순간을 찾다가 완주자의 배열이 다 끝났다면 완주자 보다 배열 길이가 하나 더 큰 참가자 배열의 마지막 사람이 바로 완주하지 못한 사람이므로 출력한다.

+ 제한사항을 정말 잘 이해해야한다 (하나 빼고 보기도 했고 ㅠ 반성합니다 ㅠ)

• completion의 길이는 participant의 길이보다 1 작습니다.

이 부분은 끝까지 골인하지 못한 사람은 단 한명이라는 힌트를 준다. 

[제한사항] 

• n은 길이 10,000이하인 자연수입니다.

[입출력 예]

추측) 

홀수에 수, 짝수에 박을 출력하면 될거 같다. 매개변수로 받은 int만큼 for문을 돌려 String 타입에 홀수에서는 수, 짝수에서는 박 문자를 더해 출력하면 될거 같다.

소스코드) 

String answer = "";
for (int i=0; i<n; i++){
    if(i%2==0){
        answer += "수";
    } else {
        answer += "박";
    }        
}
return answer;

리뷰) 

첫날 알고리즘 문제에 허덕이는 나에게 단비가 되어준 문제 였다. 홀수 짝수를 판별해 각각 맞는 문자열을 더해주는 문제로 추측에 맞게 성공하였다.