Leetcode - Twosum

2020-08-24

⏱ 4 min.

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the *same* element twice.

주어진 int형 배열에서 2개의 수를 더했을때 특정값(target)이 되는 배열의 인덱스를 반환하는 문제이다.

Example

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution

class Solution {
    public int[] twoSum(int[] nums, int target) {
   
    int[] results = new int[2];
   
    for (int i = 0; i < nums.length; i++) {
		for (int j = nums.length-1; j > i; j--) {
			if(nums[j]+nums[i]==target) {
				results[0] = i;
				results[1] = j;
			}
		}
	}
	return results;
}

오랜만에 알고리즘 문제를 풀어봤다. 올초만 하더라도 1일1백준을 했었는데, 취업 준비를 하며 알고리즘 문제를 전혀 안풀어봤었다. 그러다 이렇게 아예 손놓으면 나중에 더 힘들어지겠다 싶어서 점심시간에 잠시 짬내서 leetcode 문제를 풀어보았다.

간단한 문제였다. int형 배열을 반복문으로 더해보며 target에 해당하는 연산결과가 나오면 해당 인덱스들을 새로운 int형 배열에 담아서 반환하면 되는 문제였다.

문제 풀이 결과 코드는 맞췄지만, Runtime 성능이 133ms로 하위 5% 대로 나왔다. 퇴근하면서 유튜브로 다른 사람의 해설을 참고해봐야겠다.

처음 풀었을때는 안쪽 중첩 for문을 아래의 코드로 동작시켰더니 Runtime 성능이 133ms로 하위 5%대의 결과가 나왔다.

for (int i = 0; i < nums.length; i++) {
    for(int j = nums.length-1; j > 0; j--) {
	    results[0] = i;
		results[1] = j;
	}
}

그런데 중첩 for문을 개선해서 5ms로 엄청나게 효율적으로 수정할 수 있었다.

DevQuiz

Problem

Example

Solution