코딩 테스트 풀이 1 - Four Stack

✔ 문제

https://www.acmicpc.net/problem/25556

💡 접근 방법

문제에서 직접적으로 4개의 스택을 가지고 있다고 언급한 점과 "가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다" - LIFO 이기 때문에 스택 자료 구조 문제라는 것을 바로 깨달을 수 있었다. 그리고, 데이터를 각 Stack에 넣는 기준을 아래와 같이 잡았다 :

(1) 필수적으로 Stack의 Top 보다는 크고
(2) 위 조건에 해당하는 스택이 2개 이상일 때는 그 중에서 가장 큰 것을 고를 것 (Greedy)

(1)번 조건은 데이터를 Stack에서 꺼낼 때 오름차순이 되어야 하기 때문에 필수 조건이고, (2)번 조건은 매번 최적의 선택을 하기 위함인데, 예로 들자면 5 6 7 4 3 이 주어졌을 때, 스택 1에 5를 넣었다고 가정하자. 그럼 스택 2에 6을 넣는 것보다 1에 6을 넣는 것이 더 나은 선택이다.

⭐ 코드

import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Scanner;
import java.util.Stack;

/*
https://www.acmicpc.net/problem/25556
 */

public class Main
{
    public static boolean CheckStack(int[] arr)
    {
        int[] maxArr = new int[4];
        Arrays.fill(maxArr,-1);

        for (int num : arr)
        {
            int Max = 0;
            try
            {
                Max = Arrays.stream(maxArr).filter(h -> h < num).max().getAsInt();
            }
            catch (NoSuchElementException e)
            {
                return false;
            }

            for (int i = 0; i < maxArr.length;++i)
            {
                if (Max == maxArr[i])
                {
                    maxArr[i] = num;
                    break;
                }
            }
        }

        return true;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int num = Integer.parseInt(sc.nextLine());

        String nums = sc.nextLine();
        String numlist[] = nums.split(" "); 
        int[] newarr = new int[num];
        for(int i=0; i<numlist.length; i++)
        { 
            newarr[i] = Integer.parseInt(numlist[i]);
        }

        boolean result = CheckStack(newarr);
        String answer = result ? "YES" : "NO";
        System.out.println(answer);
    }
}

💻 더 나은 코드 분석

코드 통과는 했지만, 랭킹을 보면 더 적은 메모리와 시간으로 문제를 푼 사람들이 많다. 그 중 1등의 코드를 분석하고 어떤 점을 배우면 좋을 지 살펴 보았다.

1. Scanner 대신 BufferedReader 을 쓸 것
   Scanner는 간편하지만 코딩 테스트에서 걸리는 시간을 줄이기 위해서는 BufferedReader을 쓰는 것이 더 좋다고 한다. 쓰는 방법은 아래와 같다 :

	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int length = Integer.parseInt(br.readLine());

2. StringTokenizer 의 이용
   문제에서 두번째 Input으로 빈 칸으로 구분된 숫자들을 주게 되는데, 이런 경우 StringTokenizer Class를 활용하면 훨씬 편하게 parse 할 수 있다고 한다. 쓰는 방법은 아래와 같다 :

	StringTokenizer st = new StringTokenizer(br.readLine());
	for (int i = 0; i < arr.length; ++i)
	{
	    arr[i] = Integer.parseInt(st.nextToken());
	}