Find the Smallest Missing Positive Integer

문제 이해

"가장 작은 missing positive integer"

• [3, 4, -1, 1] → 답: 2 (1 있음, 2 없음, 3 있음)
• [1, 2, 0] → 답: 3 (1,2 있음, 3부터 없음)
• [7, 8, 9] → 답: 1 (1부터 없음)

내가 짠 코드의 문제점

로직 자체가 틀림: 정렬 후 첫 번째 요소+1을 리턴 → 완전 오답

• [1,2,3] 정렬하면 [1,2,3], 첫 요소+1 = 2 (정답은 4)
• 복잡한 정렬 시도: 직접 정렬 구현하려다 꼬임
• 음수 처리가 이상함: 음수는 무시하면 되는데 복잡하게 처리

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;



class Result {

    /*
     * Complete the 'findSmallestMissingPositive' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY orderNumbers as parameter.
     */

    public static int findSmallestMissingPositive(List<Integer> orderNumbers) {
        int temp = 0;
        int returnValue = 0;
        int t = 0;
        if(orderNumbers.size() == 0) {
            return returnValue+1;
        }
        for(int i=0; i < orderNumbers.size(); i++){   
            //System.out.println("i=>"+i);         
            temp = orderNumbers.get(t);
            //System.out.println(t+")orderNumbers.size()==="+orderNumbers.size());
            if( temp < 0 && t < orderNumbers.size()) {  
                t = t+1;        
                //System.out.println("t="+t);  
                if(t!=orderNumbers.size()) 
                temp = orderNumbers.get(t);                
            }
            //System.out.println("[i]="+i+"/temp="+temp);
            if(orderNumbers.size() == 1){
                returnValue = orderNumbers.get(0)+1;
                return returnValue;
            }
            for(int j=t+1; j < orderNumbers.size(); j++){
                //System.out.println(temp+")orderNumbers.get(j)"+orderNumbers.get(j));
                if(temp > orderNumbers.get(j)){
                    // 3 > -1
                    orderNumbers.set(t, orderNumbers.get(j));
                    orderNumbers.set(j,temp);
                }           
                
            }
            
        }
        //System.out.println("----------------------");
        for(int p=1; p < orderNumbers.size(); p++){
            if(orderNumbers.get(0) < 0 && orderNumbers.get(p) > 0) {  
                orderNumbers.set(0, orderNumbers.get(p));
            }    
        }
        
        returnValue = orderNumbers.get(0)+1;
        
        return returnValue;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int orderNumbersCount = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> orderNumbers = IntStream.range(0, orderNumbersCount).mapToObj(i -> {
            try {
                return bufferedReader.readLine().replaceAll("\\s+$", "");
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        })
            .map(String::trim)
            .map(Integer::parseInt)
            .collect(toList());

        int result = Result.findSmallestMissingPositive(orderNumbers);

        System.out.println(result);

        bufferedReader.close();
    }
}

HashSet 이용하면 쉽게 풀린다!!

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;



class Result {

    /*
     * Complete the 'findSmallestMissingPositive' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY orderNumbers as parameter.
     */

    public static int findSmallestMissingPositive(List<Integer> orderNumbers) {        
        int returnValue = 0;
        Set<Integer> hs = new HashSet<>();
        //System.out.println("orderNumbers.size()->"+orderNumbers.size());
        if(orderNumbers.size() <= 0) return 1;
        for(int orderNumber:orderNumbers) {
            hs.add(orderNumber);
        }
        // 3 ,4,-1, 1
       // System.out.println("hs.size()"+hs.size());
        for(int i=0; i <= hs.size(); i++){
           // System.out.println("i="+i);
            if(!hs.contains(i+1)) {
                returnValue = i+1;
                break;
            }
        
        }      
        return returnValue;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int orderNumbersCount = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> orderNumbers = IntStream.range(0, orderNumbersCount).mapToObj(i -> {
            try {
                return bufferedReader.readLine().replaceAll("\\s+$", "");
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        })
            .map(String::trim)
            .map(Integer::parseInt)
            .collect(toList());

        int result = Result.findSmallestMissingPositive(orderNumbers);

        System.out.println(result);

        bufferedReader.close();
    }
}

문제이해를 정확히 못함!! ㅠ

ㅁ HashSet을 이용하면 빠름!

 

• ArrayList였으면 매번 처음부터 끝까지 확인 (O(n))
• HashSet은 바로 확인 (O(1))

출처 : https://www.hackerrank.com/contests/software-engineer-prep-kit/challenges/find-smallest-missing-positive-integer