두개 뽑아서 더하기

문제 : https://programmers.co.kr/learn/courses/30/lessons/68644

코딩테스트 연습 - 두 개 뽑아서 더하기

1) 풀이 방법

 기준 인덱스를 기준으로, 기준 인덱스보다 큰 인덱스들의 값들의 합과 비교해서 리스트 담기.

 

2) 나의 코드

import java.util.TreeSet;

/**
 *https://programmers.co.kr/learn/courses/30/lessons/68644
 *두개 뽑아서 더하기.
 *
 */
public class PickUpDataAndPlus {
	
	/**
	 *  테스트 1 〉	통과 (0.72ms, 52.7MB)
		테스트 2 〉	통과 (0.75ms, 53MB)
		테스트 3 〉	통과 (0.75ms, 52.5MB)
		테스트 4 〉	통과 (0.76ms, 53.6MB)
		테스트 5 〉	통과 (1.28ms, 52.3MB)
		테스트 6 〉	통과 (1.36ms, 53MB)
		테스트 7 〉	통과 (5.05ms, 53.9MB)
		테스트 8 〉	통과 (3.50ms, 52.4MB)
		테스트 9 〉	통과 (3.04ms, 52.1MB)
	 */
	public static void main(String[] args) {
		// numbers에 있는 데이터중 서로 다른 인덱스에 있는 두개의 수를 뽑아 더해서 만들수 있는 모든 수를 배열에 담기.
		
		int[] numbers = {2,1,3,4,1};
		//int[] numbers = {5,0,2,7};
		
		TreeSet<Integer> result = new TreeSet<Integer>();
		
		for(int i=0; i< numbers.length; i++) {
			for(int j=i+1; j<numbers.length; j++) {
				result.add(numbers[i]+numbers[j]);
			}
		}

		/*
		int[] answer = new int[result.size()];
		int i=0;
		for(int value : result) {
			answer[i] = value;
			System.out.print(value + " ");
		}*/
        int[] answer = result.stream().mapToInt(Integer::intValue).toArray();
        // stream 사용법 익숙해져보자
	}
}

 

 

# 순열을 푼 직후에 풀어서 처음에 n개중 2개만 뽑는 순열문제로 접근했다가 시간초과 남.

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

import org.apache.commons.collections4.list.TreeList;

/**
 *https://programmers.co.kr/learn/courses/30/lessons/68644
 *두개 뽑아서 더하기.
 * 시간초과 난 코드
 
 */
public class PickUpDataAndPlus {
	/*테스트 1 〉	통과 (0.99ms, 52.3MB)
	테스트 2 〉	통과 (2.69ms, 52.4MB)
	테스트 3 〉	통과 (0.86ms, 53.3MB)
	테스트 4 〉	통과 (3.04ms, 52.4MB)
	테스트 5 〉	통과 (274.94ms, 55MB)
	테스트 6 〉	실패 (시간 초과)
	테스트 7 〉	실패 (시간 초과)
	테스트 8 〉	실패 (시간 초과)
	테스트 9 〉	실패 (시간 초과)
	정확성: 55.6
	합계: 55.6 / 100.0*/
	static TreeSet<Integer> sumOfValues = new TreeSet<Integer>();
	public static void main(String[] args) {
		// numbers에 있는 데이터중 서로 다른 인덱스에 있는 두개의 수를 뽑아 더해서 만들수 있는 모든 수를 배열에 담기.
		
		//int[] numbers = {2,1,3,4,1};
		int[] numbers = {5,0,2,7};
		
		List<Integer> list = new ArrayList<>();
		for(int number : numbers) {
			list.add(number);
		}
		
		List<Integer> tempList = new ArrayList<>();
		for(int i=0; i<list.size(); i++) {
			permutation(list, tempList, list.size(), 2);
		}

		int i=0;
		int[] result = new int[sumOfValues.size()];
		for(int sum : sumOfValues) {
			result[i] = sum;
			i++;
			System.out.print(sum + " ");
		}
	}
	
	public static void permutation(List<Integer> list, List<Integer> temp, int n, int r) {
			if(r==0) {
				int sum = Math.addExact(temp.get(0), temp.get(1));
				sumOfValues.add(sum);
			}
			
			for(int i=0; i<n; i++) {
				temp.add(list.remove(i));
				permutation(list, temp, n-1, r-1);
				list.add(i, temp.remove(temp.size() - 1));
			}
	}

}

 

처음에 단순하게 푸는 생각을 먼저하자!