[알고리즘/자료구조] JAVA 중복 확인 알고리즘 문제 (코딩테스트 준비)

난이도 [하]

문제: 배열로 input이 들어오고, 배열안에 값이 중복인 경우 true, 중복이 아닌경우 false가 나오도록 작성하여라.

case 1.

입력: [1,2,3,4,5,1] 

출력: true

 

case 2.

입력: [1,4,3,4] 

출력: true

 

case 3.

입력: [1,5,3,4] 

출력: false

 

문제풀이.

위의 문제를 풀기위해서 천천히 알아보려고 합니다.

input형식은 배열로 들어왔고, 출력은 true or false입니다.

 

우리의 목적은 [중복값이 있는지 확인]입니다. 

즉, 목적 자체가 이 문제를 풀 로직이 될것입니다.

 

출력값은 true or false 둘중 하나이기 때문에 하나의 기준을 잡고 시작하겠습니다.

class Solution {
    public boolean array(int[] nums) {
		return false;
    }
}

 

다음은 배열에 있는 값을 확인할 차례인데, 방법은 크게 두가지 있습니다.

1. 첫번째 인덱스부터 마지막 인덱스까지 비교하기.

ex) inputData: 1,3,4,1

(1,3)(1,4)(1,1) 

2. set 컬렉션을 이용

 

1번은 여러번 순회하기 때문에 2번이 적절해 보입니다.

2번의 set의 특징중 하나가 중복을 허용하지 않는다는 장점이 있기 때문입니다.

 

그럼 set을 사용하기 위해 set을 선언해줍니다.

받은 숫자는 int형이기 때문에 제네릭도 선언해줍니다.

class Solution {
    public boolean array(int[] nums) {
    	Set<Integer> temp = new HashSet<>();
        
    	return false;
    }
}

 

다음은 set을 사용하겠다고 선언했으니 실제 input데이터를 하나하나 넣어줍니다.

 

class Solution {
    public boolean array(int[] nums) {
    	Set<Integer> temp = new HashSet<>();
        
        for(int i=0;i<nums.length;i++){
        	temp.add(nums[i])
        }
    	return false;
    }
}

 

for문을 보시면 input크기만큼 순회를 할거고, 조건이 맞다면 set에 input값을 하나하나 넣어주는 것을 보실수 있습니다.

 

우리의 목적은 로직완성입니다. 제가 초반에 목적은 [중복값이 있는지 확인]한다고 했죠? 실제 중요 로직을 완성해 봅시다.

set에 여러 기능중 중복된 값을 찾는 기능이 존재합니다.

바로 "contains" 우리는 이기능을 사용하여 중복을 찾고, 중복이 발견된다면 true를 반환해줍시다.

 

class Solution {
    public boolean array(int[] nums) {
    	Set<Integer> temp = new HashSet<>();
        
        for(int i=0;i<nums.length;i++){
        	if(temp.contains(nums[i])){
            	return true;
            }
        	temp.add(nums[i])
        }
    	return false;
    }
}

 

if문을 살펴보면 temp에 현재값(nums[i])가 있다면 true로 반환해라~ 라는 로직이 생겼습니다.

 

저 두줄이 우리가 풀고자하는 문제를 풀어주는 주요로직이 됩니다.