[알고리즘]수 찾기

package org.example.수찾기;

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        try (
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)))
        ) {
            int n = Integer.parseInt(br.readLine());
            String inputForCheck = br.readLine();
            StringTokenizer st = new StringTokenizer(inputForCheck, " ");
            
            Set<NaturalNumber> inspectators = new HashSet<>();
            for (int i = 0; i < n; i++) {
                String inputForNaturalNumber = st.nextToken();
                NaturalNumber checkNumber = NaturalNumber.of(inputForNaturalNumber);
                inspectators.add(checkNumber);
            }
            
            int m = Integer.parseInt(br.readLine());
            String targetNumbers = br.readLine();
            StringTokenizer st2 = new StringTokenizer(targetNumbers, " ");
            
            List<NaturalNumber> targets = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                String inputForNaturalNumber = st2.nextToken();
                NaturalNumber checkNumber = NaturalNumber.of(inputForNaturalNumber);
                targets.add(checkNumber);
            }
            
            for (NaturalNumber target : targets) {
                if (inspectators.contains(target)) {
                    pw.println(1);
                    continue;
                }
                pw.println(0);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    
    public static class NaturalNumber {
        private final int value;
        
        public NaturalNumber(int value) {
            this.value = value;
        }
        
        public static NaturalNumber of(String other) {
            Objects.requireNonNull(other, "other must be provided.");
            int value = Integer.parseInt(other);
            return new NaturalNumber(value);
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof NaturalNumber)) return false;
            
            NaturalNumber that = (NaturalNumber) o;
            
            return value == that.value;
        }
        
        @Override
        public int hashCode() {
            return value;
        }
        
        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("NaturalNumber{");
            sb.append("value=")
              .append(value);
            sb.append('}');
            return sb.toString();
        }
    }
    
}

• 기본적인 자료구조의 사용법만 알면 쉽게 해결할 수 있는 문제이다.

• 사실 별도 클래스도 필요한 문제도 아니였다. 생성자 검증도 필요하지도 않은 문제였음.

1. of 팩토리 메서드

   public static NaturalNumber of(String other) {
         Objects.requireNonNull(other, "other must be provided.");
         int value = Integer.parseInt(other);
         return new NaturalNumber(value);
     }

   • 입력값을 String 으로 받아야하는 부분이 있었다.
   • 외부에서 Integer.parseInt 로 변환해서 생성자 호출을 하도록 해도 되지만, 사용자가 String 값을 그대로 주입할 수 있도록 편의를 위해 팩토리 메서드를 생성하였다.

2. 검사 대상되는 수열

   Set<NaturalNumber> inspectators = new HashSet<>();
     for (int i = 0; i < n; i++) {
         String inputForNaturalNumber = st.nextToken();
         NaturalNumber checkNumber = NaturalNumber.of(inputForNaturalNumber);
         inspectators.add(checkNumber);
     }

   • 검사의 대상이 되는 수열은 중복이 될 이유가 없다고 생각했다.
   • 그래서 Set 자료구조를 채용하여 향후 입력되는 중복을 제거하였다.
   • Set 자료구조 사용시 클래스에서는 클래스의 중복값 제거를 위해 equals 와 hashcode 를 재정의 해야한다는 것을 잊지 말자.

3. 제한조건의 강조

   for (NaturalNumber target : targets) {
       if (inspectators.contains(target)) {
           pw.println(1);
           continue;
       }
       pw.println(0);
   }

   • if else 를 사용해도 되지만.
   • if문에 continue 를 사용하여 도입부 코드 부분이 예외 케이스라는 것을 강조하고 싶어서 continue; 를 사용하였다.

시간 복잡도는 기존적인 입력 반복문 때문에 O(n) 으로 예상한다.

Uploaded by N2T