1. 문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

 

2. 제한사항

  • 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
  • 각 숫자는 1 이상 50 이하인 자연수입니다.
  • 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

 

3. 입출력 예

numbers target return
[1, 1, 1, 1, 1] 3 5

 

 

4. 문제를 보고 가진 생각 정리

위 문제는 5개수를 모두 사용하여 나올 수 있는 경우의 수를 생각하여야 한다. 위 테스트 케이스 기준 나올 수 있는 총 경우의 수는 2^5로 32개이다. 이 경우의 수를 이진 그래프로 나타내보았다.

 

모든 경우의 수를 표현하려면 그림이 너무 커져서 2개의 수에 대해서만 생각을 해보았다. 문제 예시처럼 5개의 수가 주어진다면, 깊이가 5인 곳에서의 모든 경우의 수에 대한 합을 구하여 target과 일치하는 로직으로 풀이를 하면 될 것이라고 생각하였다. 또한, 깊이 우선으로 탐색을 하여야 하기 때문에, 함수에서 함수를 호출하는 재귀 함수를 선택하기로 하였다. 

 

 

5, 풀이 코드

class Solution {
    
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
    	//4번의 그림에서 start와 같은 로직
        search(numbers, target, 0);
        return answer;
    }
    
    public void search(int[] numbers, int target, int depth){
    
    	//입력된 numbers의 length까지 탐색을 완료하였을 경우, 배열의 합을 구하여 target과 비교
        if(numbers.length == depth){
            int sum=0;
            for(int i=0;i<numbers.length;i++){
                sum+=numbers[i];
            }
            if(sum==target)
                answer++;
        //탐색이 완료되지 않았다면, 다음 depth에 해당하는 탐색을 진행한다.
        //numbers에서 제공된 수가 양수일 수도 있고, 음수일 수도 있기 때문에 두 경우에 대해 탐색 진행.
        }else{
            search(numbers, target, depth+1);
            numbers[depth]*=-1;
            search(numbers, target, depth+1);
        }
    }
}

'IT > Algorithm' 카테고리의 다른 글

[프로그래머스] 타겟 넘버  (0) 2020.05.07
[프로그래머스] 완주하지 못한 선수  (0) 2020.04.29

1. 문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

 

 

2. 제한사항

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

 

 

3. 입출력 예

participant completion return
[leo, kiki, eden] [eden, kiki] leo
[marina, josipa, nikola, vinko, filipa] [josipa, filipa, marina, nikola] vinko
[mislav, stanko, mislav, ana] [stanko, ana, mislav] mislav

 

 

 

4. 입출력 예 설명

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

 

 

 

5. 문제 해석 및 회고

위 문제는 배열을 비교하여 participant 배열에는 없는 것을 찾는 문제였다. 지금까지 C++위주로 학습하다 JAVA로 풀이하려니 JAVA 자료형에 대한 이해가 부족한 것을 많이 느꼈다. 다음은 내가 몰랐던 부분이거나, 짚고 넘어가야 할 부분이다.

 

  • Java에서 Map 자료형은 같은 key가 입력될때, 기존 값을 덮어쓰기 해버린다
  • String[] 자료형과 ArrayList자료형의 길이(사이즈)를 구할때는 각각 .length와 .size()를 사용한다.
  • Map자료형을 탐색시, Iterator를 사용하여 키 값을 기준으로 탐색이 가능하다.

맨 처음 풀때는, string값 하나하나를 .equals()로 비교하다보니 정답은 나왔지만 효율성에서 매우 꽝이었다. 효율성을 위해 고민한 결과, 탐색시, 나왔던 값과 나오지 않은 값에 대한 판단을 HashMap에 <key, value>로 담아 관리하게 되면 string 비교를 하지 않고 등장 횟수 처리를 통해 조금 더 효율적으로 처리할 수 있을 것이라 판단했다.

위 생각을 확장하면, 데이터가 모두 다른 사람으로 주어진다면, 0 or 1로 처리가 가능하다. 그러나 이 문제는 동명이인이 있을 수 있기 때문에, 이에 대한 처리도 필요하였다. 그래서 달릴 거리가 남아 있는 상태를 1 이상의 수, 완주하여 complete한 상태를 0으로 하여 문제를 풀기로 마음먹었다. 풀이 코드는 다음과 같다.

 

 

 

 

6. 풀이 코드

import java.util.Map;
import java.util.HashMap;
import java.util.Iterator;

class Solution {
    public String solution(String[] participant, String[] completion) {

        String answer = new String();
        Map<String, Integer> map = new HashMap<>();
        
        //마라톤 참가자의 map 등록, 동명이인은 1번 더 같은 거리를 뛰는 것으로 간주하고, 동일인 취급.
        for(int i=0;i<participant.length;i++){
            if(map.get(participant[i])==null){
                map.put(participant[i], 1);
            }else{
                map.put(participant[i], map.get(participant[i])+1);
            }
        }
        
        //완주자는 완주거리에 대한 값 빼줌.
        for(int i=0;i<completion.length;i++){
                map.put(completion[i], map.get(completion[i])-1);
        }

		//아직 뛸 거리가 남은 사람을 탐색한다.
        //완주할 거리가 남아있으면, 1이상의 값을 나타낸다.
        //완주 하였으면 더이상 뛸 거리가 없으므로 0으로 표기한다.
        Iterator<String> iter = map.keySet().iterator();
        while(iter.hasNext()){
            answer = iter.next();
            //완주하지 못한 사람이 걸리면 바로 값을 return 한다.
            if(map.get(answer)!=0){
                return answer;
            }
        }
        
        //while문에 안걸리면 마지막 Map 원소의 key값이 덜 뛴 사람이다.
        return answer;
    }
}

 

 

 

 

7. 출처

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

'IT > Algorithm' 카테고리의 다른 글

[프로그래머스] 타겟 넘버  (0) 2020.05.07
[프로그래머스] 완주하지 못한 선수  (0) 2020.04.29

+ Recent posts