[알고리즘/자료구조] JAVA 두 수의 합 알고리즘 문제 (코딩테스트 준비)
난이도 [하]
문제: 배열과 정수형값이 input이 들어오고, 배열안에 두값을 더했을때 정수형값이 되는 인덱스를 반환하라.
각 무조건 하나의 답만 존재한다.
case 1.
입력: [1,2,3,4,5,1] , 3
출력: [0.1]
case 2.
입력: [6,3,2,1,5] , 4
출력: [1.3]
case 3.
입력: [6,3,2,1,5,4] , 5
출력: [3.5]
문제풀이.
위의 문제를 풀기위해서 천천히 알아보려고 합니다.
input형식은 배열과 정수형으로 들어오고, 출력값은 배열입니다.
그럼 코드를 작성 해봅시다.
class Solution {
public int[] twoSum(int[] nums, int resultnum) {
return new int[] {};
}
}코드를 보시면 반환값에 new를 이용하여 빈배열을 반환하는것을 보실수 있습니다.
문제에서는 [각 무조건 하나의 답만 존재한다.] 라고 답이 하나!있다 라고 말은 했지만, 혹시 모를 상황에 대비한 리턴값이라고 보시면 됩니다.
또한 int [] array = {}; 로 변수를 만들지 않은 이유는 배열에는 값이 총 2개가 들어가게 됩니다.
[첫번째인덱스,두번째인덱스]
그렇기 때문에 배열을 초기화하지않고, 리턴시 새로운 공간을 할당한 값을 반환해주는 것입니다.
그럼 다음 코드를 작성하기전에, 문제 해결하기 이전 조건을 두가지를 알고있습니다.
1. 배열이기 때문에 인덱스가 존재한다. (반환값)
2. 인덱스에 따른 값이 존재한다. (계산값)
그럼 우리는 두가지 값을 알고있기 때문에 적절한 것은 hashmap을 이용하는것일 것입니다. (두가지 값을 사용)
class Solution {
public int[] twoSum(int[] nums, int resultnum) {
HashMap<Integer, Integer> Mtemp = new HashMap<>();
return new int[] {};
}
}Mtemp라는 hashmap을 선언했습니다.
이젠 두가지 값이 존재하니, 결정을 해야합니다. [1. 반환값] 과 [2.계산값]을 어떤걸 key로 잡고, value로 잡을지 생각해보겠습니다.
계산값은 nums를 통해 바로알수가 있습니다. 그렇기에 계산하는데 무리가 없죠.
반환값은 nums를 for문을 통해 알수가 있습니다. 하지만 반환할때 사용할 [값]으로 사용될거기 때문에 value가 적절해 보입니다.
저는 key=계산값, value=반환값으로 하겠습니다.
둘이 바꿔서 사용해도 상관 없어요!
그럼 이제 배열의 크기만큼 순환을 하면서 값을 넣어주기로 합시다.
class Solution {
public int[] twoSum(int[] nums, int resultnum) {
HashMap<Integer, Integer> Mtemp = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int diff = resultnum - num;
Mtemp.put(diff, i);
}
return new int[] {};
}
}배열을 돌면서 값을 넣어줍니다.
여기서 보시면 제가 key에 [diff=resultnum-num]을 넣어놨습니다.
아까 위에서 [계산값]을 넣는다고 막연하게 이야기했는데, 코드는 잠시 잊고 다시 key-value형태를 생각해봅시다.
이해하기 쉽게 위에 case1을 사용해보겠습니다.
case 1.
입력: [1,2,3,4,5,1] , 3
출력: [0.1]
key는 계산값, value는 인덱스
우리는 배열의 두수를 더해 3이라는 결과가 나오는 숫자들의 인덱스가 궁금합니다.
그럼 첫번째 인덱스부터 비교해 보겠죠?
(1,2)(1,3)(1,4)....
이때, 계속 비교를 해본다면 빠르면 바로 찾겠지만 저 ~~뒤에 있는 인덱스가 정답인 경우 엄청 오래걸립니다. 배열의 크기 만큼 도닌깐요!
한번 봐볼까요? 위에서 입력값3을 6으로 바꿨습니다.
입력: [1,1,3,4,5,5] , 10
(1,1)(1,3)(1,4)(1,5)(1,5)
(1,3)(1,4)(1,5)(1,5)
(3,4)(3,5)(3,5)
(4,5)(4,5)
(5,5)
(5,5)를 찾기 까지 되게 많이 돌게 됩니다. 그럼 여기서 생각을 해봐야죠. 더 좋은 방법이 없나?
더 좋은 방법은 [6-인덱스값]을 해서 그 결과값을 담아 놓는거죠! 그리고 그 결과값과 동일한 값이 인덱스에 있다면?
그게 나머지 하나의 값이 되게 됩니다.
위의 예제로 한번 봐볼까요?
입력: [1,1,3,4,5,5] , 10
9
9
7
6
5
for문을 돌면서 6-인덱스값을 하면 위와 같이 key가 쌓이게 됩니다.
그럼 1,1,3,4,5 까지 돌았을때 위와 같이 key가 쌓이고, 마지막 5 연산을 하기전 들어오는 key의 5가 들어오는 값과 같으니 합이 10이라고 알수가 있죠.
다시!
[1,1,3,4,5,5] , 4
결과만 10 -> 4로 바꿨습니다.
결과값-인덱스값을 key로 쓰기위해
4-1 = 3
4-1= 3
4-3=...? 어 잠만 3이 들어왔네? key에 3이 있어. 너가 원하는 4를 찾았어! [인덱스0]또는[인덱스1] 과 방금들어온 [인덱스3]을 더하면 4야!
이해하셨나요? - 연산은 key와 비교해서 없는 경우 -연산을 적용하고, 있는 경우는 값을 반환 하면 됩니다.
그럼 다시 돌아와서 !
class Solution {
public int[] twoSum(int[] nums, int resultnum) {
HashMap<Integer, Integer> Mtemp = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int diff = resultnum - num;
Mtemp.put(diff, i);
}
return new int[] {};
}
}위코드 이해하셨죠?
그럼 우리는 if문을 사용해야한다는것도 알고 어디서 사용할지도 알고있습니다.
실제 -된 값을 넣기전에 if문이 존재하면 되겠죠?
그럼 hashmap에 내가 원하는값, 즉 resultnum이 될수 있는 또다른 수가 있는지 없는지 어떻게 아는지는 아래 코드를 보시면 됩니다.
class Solution {
public int[] twoSum(int[] nums, int resultnum) {
HashMap<Integer, Integer> Mtemp = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int diff = resultnum - num;
if (Mtemp.containsKey(nums[i])) {
return new int[] { Mtemp.get(num), i };
}
Mtemp.put(diff, i);
}
return new int[] {};
}
}
저번에 set에서는 아래와 같은 메소드를 사용했는데
contains
hashmap에서는 containsKey를 사용합니다.
containsKey
위 if문을 설명하자면,
"맵안에 지금 들어갈 값(배열값)이 있으면, 값이 있던 인덱스(Mtemp.get(num))와 지금 인덱스(i)를 반환할께"
입니다.
코딩을 처음 시작하시는 분들은 값이 있던 인덱스(Mtemp.get(num)) 그게 어디있는데..라고 하실수있어요.
위에 코드와 우리가 처음 이야기 한걸 생각해봅시다.
[key는 계산값, value는 인덱스값] value를 알수있는방법은 위의 변수
int num = nums[i]; 이녀셕을 통해 알수있습니다. 이코드는 말그대로 nums[몇번째값]을 num으로 넣어줬습니다.
그렇기때문에 Mtemp.get(num)를 key이용해 value(인덱스)값을 알수있습니다.