자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 중복 확인

 

https://hyejin.tistory.com/1243

자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : Least Recent

-> 이전 문제 풀이 

 

 

5. 중복 확인 

설명

현수네 반에는 N명의 학생들이 있습니다.

선생님은 반 학생들에게 1부터 10,000,000까지의 자연수 중에서 각자가 좋아하는 숫자 하나 적어 내라고 했습니다.

만약 N명의 학생들이 적어낸 숫자 중 중복된 숫자가 존재하면 D(duplication)를 출력하고,

N명이 모두 각자 다른 숫자를 적어냈다면 U(unique)를 출력하는 프로그램을 작성하세요.

 

입력

첫 번째 줄에 자연수 N(5<=N<=100,000)이 주어진다.

두 번째 줄에 학생들이 적어 낸 N개의 자연수가 입력된다.

 

출력

첫 번째 줄에 D 또는 U를 출력한다.

 

예시 입력 1 

8
20 25 52 30 39 33 43 33

 

예시 출력 1

D

 

 

문제 풀이 1

public String solution(int n, int[] arr)
{
   String answer = "U";
   ArrayList<Integer> arrayList = new ArrayList<>();
   
   for (int i : arr)
   {
      if (!arrayList.contains(i)) {
         arrayList.add(i);
      }else
      {
         return "D";
      }
   }
   
   return answer;
}

👩‍💻 : 나는 우선 이 문제를 Arraylist에 arr 요소를 하나씩 넣는데, 이때 arraylist에 contains 메서드를 사용해서 이 요소가 이미 들어있으면 "D" 를 리턴해주고, 들어있지 않다면 arraylist에 add해줬다. 

 

 

 

문제 풀이 2

public String solution2(int n, int[] arr)
{
   String answer = "U";
   Arrays.sort(arr);
   
   for (int i = 0; i< n-1; i++)
   {
      if (arr[i] == arr[i + 1]) {
         return "D";
      }
   }
   
   return answer;
}

👾 : 강사님은 이 문제를 HashMap으로 풀었을 거라고 얘기했는데.. 나는 Arraylist로 풀긴했다.. ㅋㅋ 

아무튼 HashMap 으로 문제를 푸는 방법도 있지만 이 문제를 정렬로도 풀 수 있다는 것을 알려주기 위해서 이 문제를 강의에 포함시켰다고 한다. 

 

Arrays.sort 메서드를 이용해서 arr 배열을 오름차순으로 정렬해주고, 반복문을 도는데 n-1 까지만 돌면서 arr[i]와 arr[i+1]이 서로 같으면 "D"를 리턴해주고 모두 다르면 "U" 를 리턴하도록 했다.