백준 문제 풀이 - 1차원 배열 단계 - 5579번 과제 안 내신 분...?

백준 문제를 풀어 보던 중 5579번에서 생각보다 애를 먹었다.

기본적인 문제였음에도 문제 의도를 제대로 파악하지 못해서 헤맸던것 같다.

해당 문제를 먼저 살펴보자.

 

해당 문제는 여러가지 방법으로 풀 수 있었는데, 나는 입력받은 배열을 생성해서 정렬한 후 앞의 인덱스의 1의 값을 더한 값과 일치하지 않으면 출력하는 방법으로 풀려고 하였다.

코드는 다음과 같이 구성하였는데

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

class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> arr = new ArrayList<>();
        String s = "";

        while ((s=br.readLine()) != null && !s.isEmpty()){
            arr.add(Integer.parseInt(s));
        }

        Collections.sort(arr);

        if(arr.get(0) != 1){
            System.out.println(1);
        }
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) != arr.get(i-1)+1) {
                System.out.println(arr.get(i)-1);
            }
        }
        br.close();
    }
}

먼저 ArrayList arr를 생성하고 입력값이 없을 때까지 해당 배열에 값을 집어 넣는다.

그후 Collections.sort를 이용하여 오름차순으로 정렬해 준 뒤, arr의 size만큼 반복하여 앞의 인덱스와 값을 비교해 연속되지 않은 숫자이면 해당 값의 -1을 하여 빈값을 출력하였다.

테스트 케이스를 실행해 보고 문제가 없다고 생각해서 제출을 했는데...

틀렸습니다.

생각치 못한 결과가 나와서 뭐지 하고 고민했는데... 테스트 케이스를 이것저것 넣어보다가 이유를 알았다.

문제는 1~30의 연속된 숫자에서 없는 숫자를 출력해야 하는 문제인데 내가 작성한 코드는 마지막 숫자인 30이 없는 경우 출력을 하지 못한다. 

로직 상으로 마지막이 29가 될테니 30을 검증하지 않고 바로 넘어가는 것.

그래서 마지막 30까지 검증을 하려고 하다가 문득 드는 생각이..

굳이, 앞쪽 인덱스와 검증을 해야하는가?

사실 문제의 핵심은 1~30까지의 배열을 만들고 해당 배열에서 빠진 요소를 찾으면 되는 문제였는데 완전히 생각을 잘못하고 있었다.

순차적 비교를 하지 않아도 되니 오름차순 정렬도 사실 할 필요가 없었던 것.

그럼 다음으로 생각해 봐야할 것은 어떻게 배열에서 빠진 값을 찾아낼 것인가 인데...

어차피 문제의 제약조건에서 최대 30까지라고 되어있고 중복된 번호가 없다고 하니 굳이 배열을 또 만들 필요 없이 1~30까지 for문을 돌리면서 해당값이 있는지 없는지만 찾아 없는 숫자를 출력하도록 구현하기로 했다.

 

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

class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> arr = new ArrayList<>();
        String s = "";

        while ((s=br.readLine()) != null && !s.isEmpty()){
            arr.add(Integer.parseInt(s));
        }

        for (int i = 1; i < 31; i++) {
            if (arr.indexOf(i) < 0) {
                System.out.println(i);
            }
        }
       
        br.close();
    }
}

 

딱, 봐도 아까보다 훨씬 코드가 간결해 진것을 볼 수 있다.

좀더 살펴 보자면, 입력값이 없을때 까지 ArrayList arr에 입력값을 추가하고 1~30까지 돌리면서 indexOf() 메서드로 해당 값이 있는지 찾아보고 없으면 i값을 반환하도록 하였다.

 

결과는 성공적!

문제를 풀고 다른 사람들이 어떻게 풀었는지 좀 살펴 보았는데 배열자체를 1~30까지로 생성하여 입력된 배열의 값을 하나하나 제거하면서 푼 사람도 있고, Stream으로 처리해 버린 사람도 있었다.

 

 

 

이런 방법도 있었는데

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean[] arr = new boolean[31];
        for(int i=0;i<28;i++){
            int num = Integer.parseInt(br.readLine());
            arr[num] = true;
        }
        for(int i=1;i<31;i++){
            if(!arr[i]) System.out.println(i);
        }
    }
}

이 분은 Boolean 타입으로 입력받은 인덱스에 true 값을 넣어두고 false면 출력하는 형태로 구성하셨다.

따로 다른 처리가 필요없이 넣고 바로 출력만 하면 되니 효율면에서 더 좋아보이긴 하는데 필요한 크기보다 약간 더 큰 배열을 선언하는 점만 빼고는 다 괜찮아 보였다.

생각치 못한 참신한 방법이라 좀 신선했다.