• 문자열을 나눠서 문제를 풀이하는 경우가 굉장히 많다. 특히, 문자열을 단어 하나 단위로 쪼개거나, 띄어쓰기, 특수문자 등을 기준으로 잘라 사용해야 하는 경우가 많은데, 여기서는 활용도가 높은 split() 위주로 활용하여 단어를 나누는 방법에 대해 서술할 예정이다.

문자 하나를 가져올 때

public class stackPracticeQuestion {
    public static void checkParenthesis(String str){
        Stack stack = new Stack();
        boolean checkFlag = true;

        for (String s: str.split("")){
            if (s.equals("(")) {
                stack.push(s);
            } else {
                if (stack.isEmpty()){
                    checkFlag = false;
                    break;
                } else {
                    stack.pop();
                }
            }
        }
 }

• for (String s: str.split("")) 를 기준으로 문자를 하나씩 잘라서 확인할 수 있다.

• 이외에도 tocharArray()로 변환하여 한 문자씩 가지고 올 수 있다. (다만, char로 문자형태가 바뀌긴 할 것이다.)

  String str = "ABCDE";
  char[] arr = str.toCharArray();
  for (int i = 0; i <arr.length; i++){
    System.out.println(arr[i]+" ");
   }

(참고) charAt()

• String으로 저장된 문자열 중에서 한 글자만 선택해서 char 타입으로 변환할 수 있는 기능을 가진다.

  String str = "안녕하세요";
  char c = str.charAt(0);
  System.out.println(c); // "안"

띄어쓰기를 기준으로 할 때

String[] arStr = "ABC DEF".split("\\s");

• \\s는 공백을 의미하는데, 이러한 정규식을 사용하여 띄어쓰기 한 칸을 기준으로 단어를 분리할 수 있다.
• 또한, 한 칸 이상의 공백을 제거하기 위해서 아래와 같은 코드를 사용할 수 있다.

  String[] arStr = "ABC   DEF".split("\\s+");

그 외 (replace, trim)

• replace는 한 문자를 다른 문자로 치환한다는 뜻으로 아래와 같이 특수문자를 공백 등으로 변경하고 싶을 때 사용할 수 있다.

  s = s.replace("?"," ");

• trim은 양 옆 공백을 지우고 싶을 때 사용할 수 있다.

  s = s.trim();

종합하면 아래와 같이 코드를 구성할 수 있다.

public class Solution {
    public statuc void main(Stinrg[] args) {
        String s = "?ab???c "; 
        s = s.replace("?"," "); // " ab   c "
        s = s.trim(); // "ab   c"
        String[] answer = s.split("\\s+"); // {ab , c}
    }
}

• 문제를 풀다보면, 자료형을 변환해야하는 일이 자주 발생한다. 특히 문자를 숫자형으로 변환하는 일들이 자주 발생하는데 이를 미리 정리하여 추후 헷갈리는 일이 없도록 할 예정이다.

String -> int

Integer.parseInt

• 해당 함수를 사용할 경우 문자열을 기본 정수 (int)로 변환해준다.

• parseInt(string, radix);

Parameter

• string: 숫자로 변환하고 싶은 문자열
• radix: string 문자열을 읽을 진법

public class StringToInt {    
    public static void main(String[] args) {        
        String str1 = "123";        
        String str2 = "0xF";         

        int intValue1 = Integer.parseInt(str1);        
        int intValue2 = Integer.parseInt(str2, 16);     

        System.out.println(intValue1); // 123
        System.out.println(intValue2); // 15
    }
}

• 예시1. "123"이라는 String을 10진법 Int로 읽어온다.
• 예시2. "0xF"라는 String을 16진법으로 생각하여 10진법 Int로 변환한다.

(참고) Integer.valueOf()

• 해당 함수를 사용할 경우 문자열을 정수 객체 (Integer Object)로 변환한다. 즉, int가 아닌 Integer가 필요할 때 사용하면 된다. 이는 Integer(Integer.parseInt(s))와 동일한 결과값을 출력할 것이다.

int -> String

Integer.toString(), String.valueOf()

• Integer 클래스 혹은 String 클래스 내에 있는 기능을 사용하여 숫자를 문자로 변환할 수 있다.

public class IntToString {
    public static void main(String[] args) {
        int intValue1 = 1234;
        int intValue2 = 1234;

        String str1 = Integer.toString(intValue1);
        String str2 = String.valueOf(intValue2);

        System.out.println(str1); // 1234
        System.out.println(str2); // 1234
    }
}

개념 정리

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

그렇다면 이를 정리하는 해시 함수가 존재할 것이다. 예를 들어, 나눗셈 결과의 나머지를 해시 함수로 사용할 수 있을 것이다. (이를 division Method라고도 부른다.) 그 외에도 다양한 함수들이 존재하는데, 여기서의 공통적인 문제는 해시함수가 같은 값을 출력하는 경우 어떻게 대처할 것인지다.

이렇게 값이 충돌하는 경우를 '해시충돌'이라고 부르며, 이 경우를 해결할 수 있는 방법이 많이 알려져 있다. 크게는 분리 연결법과 개방 주소법이 있는데 이에 대한 설명은 추후 진행할 예정이다.

Hash Map vs. HashTable

자바에는 Map Inferface를 구현한 자료구조로 HashMap과 HashTable가 존재하는데, 둘의 차이를 살펴보자.

public class myHashTableStudy {
    public static void main(String args[]){
        Hashtable<String, Integer> ht = new Hashtable();

        ht.put("key1", 10);
        ht.put("key2", 20);

        HashMap<Integer, Integer> hm = new HashMap<>();
        hm.put(0,10);
        System.out.println(hm.get(0));

        // ht.put(null, 999) : Error Occured.
        hm.put(null, -999);
        System.out.println(hm.get(null));


}

가장 단순한 차이로는 key 값에 null을 쓸 수 있는지에 있다. HashTable에는 null 값을 key로 사용할 수 없으며, Map에서는 가능하다. 그 외에도 Thread-Safe 여부에 따라 사용성이 달라지는데, 이는 더 공부한 이후에 추가로 작성할 예정이다. 이해한 만큼만 쓰자면, 병렬 처리를 하면서 자원의 동기화를 고려할 때는 해시테이블(HashTable)을, 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않을 때는 해시맵(HashMap)을 사용하면 된다.

어디서 사용하는가?

예제1. Array 값 비교하기

    public static void solution(int[] arr1, int[] arr2){
        Hashtable<Integer, Integer> ht = new Hashtable<>();
        for (int i = 0; i < arr1.length; i++) {
            ht.put(arr1[i],arr1[i]);
        }

        for (int i = 0; i < arr2.length; i++) {
            if (ht.containsKey(arr2[i])){
                System.out.print("True ");
            } else {
                System.out.print("False ");
            }
        }
    }

HashTable에 arr1의 데이터를 저장한 후, for문을 통해 arr2에 arr1과 같은 값이 있는지를 containsKey()를 통해 확인한다.

예제2. 숫자 조합하기

    public static int[] targetCheck(int[] numbers, int target){
        int[] result = new int[2];
        Hashtable<Integer, Integer> ht = new Hashtable<>();

        for (int i = 0; i < numbers.length; i++){
            if (ht.containsKey(numbers[i])){
                result[0] = ht.get(numbers[i]);
                result[1] = i;
                return result;
            }
            ht.put(target - numbers[i], i);
        }
        return null;
    }

1. HashTable에 target - 처음 숫자 값을 키로 저장한다.
2. 만약 키 값과 일치하는 숫자를 찾는다면, 그 숫자와 함께 HashTable에 저장했었던 처음 숫자 값의 인덱스를 같이 반환한다. 이를 통해 O(n)으로 문제를 해결할 수 있게 된다.

개념 정리

Array는 우리가 직관적으로 알고 있는 표 / 테이블과 유사하다. 여기서는 조금 더 언어를 명확히 하여 자료구조의 의미를 써보겠다. Array란 각 데이터와 인덱스가 1:1로 대응하는 구조를 의미한다. 그래서, 데이터와 함께 '인덱스'라는 것이 반드시 존재한다.

이는 추후 설명할 Linked List와 비교하면 그 차이가 더 두드러진다. Array는 인덱스가 있어 값의 위치를 바로 확인할 수 있는 반면, Linked List는 인덱스가 없어 값을 탐색하려면, Head부터 쭉 찾아봐야한다는 단점이 있다. 아까 위에서 "각 데이터와 인덱스가 1:1로 대응하는 구조"라고 한 말이 바로 이 뜻이다. 결국 데이터에 맞는 인덱스가 있기 때문에 '탐색'이 쉽다고 이해하면 좋을 것이다.

그러면 반대로 인덱스를 써서 안 좋은 점도 있을 것이다. 인덱스를 쓰게 되면 데이터를 추가/삭제할 떄 인덱스를 다시 할당해야하는 문제점이 생긴다. 예를 들어 보자. {1,2,3,4,5}이라는 배열이 있다고 하자. 이 경우 '2'라는 데이터를 삭제하면, 남은 3,4,5의 인덱스 값을 모두 바꿔줘야 하는 문제가 생긴다. (물론 배열의 size도 변경해야 한다.) 그렇기 때문에, 추가/삭제가 빈번한 경우 다른 자료구조를 쓰는 것이 적절할 것이다.

주요 기능

주요 기능은 단순하게 add, remove만 확인해보고, 아래에서 이를 다양하게 활용하는 방법에 대해 알아보자.

import java.util.ArrayList;
import java.util.Arrays;

public class myArrayStudy {
    public static void main(String[] args){
        // Basics
        System.out.println("== 1차원 배열 ==");
        int[] arr = {1,2,3,4,5};
        for (int item : arr){
            System.out.println("item = " + item);
        }

        System.out.println("== 2차원 배열 ==");
        int[][] arr2 = {{1,2,3},{4,5,6}};
        System.out.println(arr2[0][1]);

        for (int[] row: arr2){
            for (int item: row){
                System.out.println("item = " + item);
            }
        }

        // ArrayList
        System.out.println("== Array List 활용 ==");
        ArrayList list1 = new ArrayList(Arrays.asList(1,2,3));
        System.out.println("list1 = " + list1);
        list1.add(4);
        list1.add(5);
        System.out.println("list1 = " + list1);
        list1.remove(2);
        System.out.println("list1 = " + list1);
        list1.remove(Integer.valueOf(2));
        System.out.println("list1 = " + list1);

        System.out.println("== Array List 2D ==");
        ArrayList list2d = new ArrayList();
        ArrayList list1d1 = new ArrayList(Arrays.asList(1,2,3));
        ArrayList list1d2 = new ArrayList(Arrays.asList(4,5,6));
        list2d.add(list1d1);
        list2d.add(list1d2);
        System.out.println("list2d = " + list2d);

    }
}

여기서 주목할 점 몇 가지를 살펴보자.

• Array 출력방법 Array를 출력할 때는 for문을 돌려서 가져오자.

        // Basics
        System.out.println("== 1차원 배열 ==");
        int[] arr = {1,2,3,4,5};
        for (int item : arr){
            System.out.println("item = " + item);
        }
  
        System.out.println("== 2차원 배열 ==");
        int[][] arr2 = {{1,2,3},{4,5,6}};
        System.out.println(arr2[0][1]);
  
        for (int[] row: arr2){
            for (int item: row){
                System.out.println("item = " + item);
            }
        }

• ArrayList 활용

        System.out.println("== Array List 활용 ==");
        ArrayList list1 = new ArrayList(Arrays.asList(1,2,3));
        System.out.println("list1 = " + list1);
        list1.add(4);
        list1.add(5);
        System.out.println("list1 = " + list1);
        list1.remove(2);
        System.out.println("list1 = " + list1);
        list1.remove(Integer.valueOf(2));
        System.out.println("list1 = " + list1);

자바의 ArrayList()를 활용하여 다양한 기능을 사용하며, 이때 값을 넣기 위해서 Arrays.asList()를 사용하는 것을 참고하자. 또한, 값을 제거하고 싶을 때 reemove()를 쓰면 인덱스 기준으로, remove(Integer.valueOf())를 쓰면 값 (여기서는 정수 값)을 기준으로 값을 제거할 수 있다는 점을 참고하자.

어디서 사용하는가?

예제1. 값 찾기

이전의 출력 방법을 응용하여 for문 기반의 값을 찾을 수 있다. 이때 int[]로도 구현하여 풀이하는 것이 주목하자.

public class arrayPracticeQuestions {
    public static void main (String[] args){
        int[] arr2 = {1,1,100,1,1,1,100};
        int target = 100;
        int idx = -1;
        for (int i = 0; i < arr2.length; i++){
            if (arr2[i] == target){
                idx = i;
            }
        }
        if (idx == -1){
            System.out.println("No target here.");
        } else {
            System.out.println("idx = " + idx);
        }
    }
}

예제2. Peek 찾기

양 옆의 값보다 큰 수를 찾는 방법이다. 양끝 값을 별도로 처리해준 것을 참고하자.

 public class arrayPracticeQuestions {
    public static void main (String[] args){
         int[] arr4 = {3,1,2,6,2,2,5,1,9,10,1,11};

        if (arr4[1] < arr4[0]){
            System.out.println(arr4[0]);
        }

        for (int i = 1; i < arr4.length-1; i ++)
            if (arr4[i] > arr4[i-1] & arr4[i] > arr4[i+1]){
                System.out.println(arr4[i]);
            }

        if (arr4[arr4.length-2] < arr4[arr4.length-1]){
            System.out.println(arr4[arr4.length-1]);
        }
    }
}

예제3. 출력 90도 뒤집기

2차원 배열에서 arr[0].length을 사용하면 행의 길이가, arr.length를 사용하면 열의 길이가 나온다는 점에 주목하자. 그 이후 newArr[i][cnt1] = row[i];를 통해 값을 정리해주면 된다.

 public class arrayPracticeQuestions {
    public static void main (String[] args){
        int[][] arr7 = {{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15}};
        int[][] newArr = new int[arr7[0].length][arr7.length];
        int cnt1 = arr7.length-1;

        for (int[] row: arr7){
            int rowLength = row.length;
            for (int i = 0; i < rowLength; i++){
                newArr[i][cnt1] = row[i];
            }
            cnt1 --;
        }

        for (int[] row: newArr){
            for (int item: row){
                System.out.print(item + " ");
            }
            System.out.println();
        }
    }
}

Array를 활용하여 최소, 최대 값을 출력하는 문제이다.

import java.io.IOException;
import java.util.Scanner;

public class Q3 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] seq = new int[n];

        for(int i = 0; i < n; i++) {
            seq[i] = sc.nextInt();
        }

        int maxInt = Integer.MIN_VALUE;
        int minInt = Integer.MAX_VALUE;

        for (int item: seq){
            if (item >= maxInt){
                maxInt = item;
            } if (item <= minInt){
                minInt = item;
            }
        }

        System.out.print(minInt +" "+ maxInt);

    }
}

별도의 코멘트는 없으나, maxInt, minInt가 처음부터 오류없이 들어가게 하려면 MIN_VALUE, MAX_VALUE 등을 활용해야 했다. 숫자의 범위 등에 대해서 다시 체크할 수 있는 좋은 기회였다!

문제 설명

결국 제시된 3가지 연산을 이해하는 것이 중요하다.

1. 첫 번째 원소를 뽑아낸다. 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.

2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.

3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

앞뒤로 값을 한 칸씩 옮기거나 지울 수 있다는 점에서 "Deque"를 떠올릴 수 있다.

• 1번 연산은 결국 removeFirst()
• 2번 연산은 deque.addLast(deque.removeFirst())
• 3번 연산은 deque.addFirst(deque.removeLast())

의 개념과 연결될 수 있을 것이다.

코드 설명

1번 연산은 바로 수행하면 되지만, 2,3번 연산은 수행하기 전에 2번 연산에 해당하는지, 3번 연산에 해당하는지 판단할 필요가 있다.

그래서, distance라는 개념을 도입하여 왼쪽까지의 거리, 오른쪽까지의 거리를 계산하였다. 이를 통해 더 거리가 짧은 쪽으로 이동하면 될 것이다.

import java.io.IOException;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.stream.IntStream;

import static java.lang.Math.abs;

public class Q2 {
    public static Integer checkDistance(int item, int target, LinkedList<Integer> deque) {
        int distance = abs(deque.indexOf(item) - deque.indexOf(target));
        int halfIndex = deque.size() / 2;
        if (distance > halfIndex) {
            distance = deque.size() - distance;
        }
        return distance;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        LinkedList<Integer> deque = new LinkedList<Integer>();

        int N = sc.nextInt();
        int M = sc.nextInt();
        int cnt = 0;
        int target = 0;

        IntStream.range(1, N+1).forEach(deque::add);

        int[] seq = new int[M];

        for(int i = 0; i < M; i++) {
            seq[i] = sc.nextInt();
        }

        for (int item: seq){
            target = (int) deque.getFirst();
            int distance = checkDistance(item, target, deque);
            if (distance == 0){
                deque.getFirst();
            } else if (abs(deque.indexOf(item) - deque.indexOf(target)) <= deque.size() / 2) {
                for (int i = 0; i < distance; i++) {
                    deque.addLast(deque.removeFirst());
                }
            } else {
                for (int i = 0; i < distance; i++){
                    deque.addFirst(deque.removeLast());
                }
            }
            cnt += distance;
            deque.removeFirst();
        }
        System.out.println(cnt);
    }
}

소감

처음에 indexOf()를 쓸 수 없다고 생각해서 구현에 시간이 다소 오래 걸렸다. 해당 기능에 대한 숙지가 필요할 것 같다..!

개념 정리

Queue는, 일반적으로 우리가 줄을 서는 모습을 상상하면 이해하기 쉽다. 한 쪽에서 줄을 서고 (= Enqueue), 다른 쪽에서 줄이 마무리 (= Dequeue)가 된다. 이러한 구조를 FIFO (First In First Out) 구조라고도 한다.

여기서 Dequeue가 발생되는 구간을 Front, Enqueue가 발생되는 구간을 Rear라고 자주 부른다. 이를 바탕으로 어떤 주요 기능들이 있는지 살펴보자.

주요 기능

먼저 Queue에서 주목할 점 중 하나는 바로 Queue가 Inferface의 형태로 구현되었다는 점이다. 따라서, Queue를 바로 불러오지 않고,LinkedList()를 활용하여 값을 불러올 수 있다. (즉, 다형성을 활용하겠다는 뜻이다.)

public class myQueueStudy {
    public static void main(String args[]){
        Queue queue = new LinkedList(); // Queue가 Interface임..
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        System.out.println("queue = " + queue);
        System.out.println("== Poll ==");
        System.out.println(queue.poll());
        System.out.println("queue = " + queue);
        System.out.println("== Peek ==");
        System.out.println(queue.peek());
        System.out.println("queue = " + queue);
        System.out.println("== Else ==");
        System.out.println(queue.contains(3));
        System.out.println(queue.size());
        System.out.println(queue.isEmpty());
        queue.clear();
        System.out.println("queue = " + queue);
    }
}

또 주의할 점이 하나 있는데, 여기서 enqueue가 add(), dequeue가 poll()로 구현되었음에 주의하자. 특히, front 단의 값을 확인만 하는 것(즉, 삭제 X)은 peek()임에 주의하자.

어디서 사용하는가?

예제1. Find Last Card

여기서는 마지막 카드를 찾는 규칙을 확인하고 remove -> add를 쓰는 기법에 대해 알아보자.

    public static int findLastCard(int N){
        Queue queue = new LinkedList();
        IntStream.range(1, N + 1).forEach(x -> queue.add(x));

        while (queue.size() > 1){
            queue.remove(); // 하나 지우고
            int data = (int) queue.remove(); // 하나 더 꺼내서
            queue.add(data); // 맨 아래로
        }
        return (int) queue.remove();
    }

front에 위치한 값을 꺼내서 지운 후, 하나 더 꺼낸 값을 add하는 장면이 중요하다. 결과적으로 하나의 값만이 삭제되는 것을 확인해보자.

            queue.remove(); // 하나 지우고
            int data = (int) queue.remove(); // 하나 더 꺼내서
            queue.add(data); // 맨 아래로

예제2. Josephus

 public static ArrayList getJosephus(int N, int k){
        Queue queue = new LinkedList();
        ArrayList result = new ArrayList();

        IntStream.range(1, N+1).forEach(x -> queue.add(x));

        int cnt = 0;
        while (!queue.isEmpty()){
            int data = (int) queue.remove();
            cnt += 1;
            if (cnt % k == 0){
                result.add(data);
            } else {
                queue.add(data);
            }
        }
        return result;
    }

여기서 주목할 점은 2가지.

1) IntStream의 활용 -> 모든 값에 같은 내용을 적용할 때 사용해보자.

IntStream.range(1, N+1).forEach(x -> queue.add(x));

2) k개마다 삭제 -> 즉, cnt % k == 0을 기준으로 특수 동작을 수행한다는 점 - queue를 remove한 후 -> result에 저장: 즉, queue에서 값 하나 빠짐. - queue를 remove한 후 -> queue에 저장: 즉, 한 칸씩 값이 밀림.

        int cnt = 0;
        while (!queue.isEmpty()){
            int data = (int) queue.remove();
            cnt += 1;
            if (cnt % k == 0){
                result.add(data);
            } else {
                queue.add(data);
            }
        }

Deque란?

개념 정리

말 그대로, 여러 곳에 값을 넣을 수 있다는 뜻이다. 상황에 따라서 입/출력 위치 값을 제한할 수도 있으나 여 기서는 Front, Rear 둘 다에서 값을 넣을 수 있다고 가정하자.

주요 기능

Deque 역시 Inferface의 형태로 구현되었다는 점이다. 따라서, deque를 바로 불러오지 않고,LinkedList()를 활용하여 값을 불러올 수 있다. (즉, 다형성을 활용하겠다는 뜻이다.)

front에서 값을 꺼내오는 removeFirst, rear에서 값을 꺼내오면 removeLast를 사용할 수 있다. 반대로 값을 넣는 값은 addFirst, addLast를 사용한다.

poll()의 경우 remove()와 유사하나, 값이 비어있으면 "null"을 출력한다는 점에서 차이가 있다.

public class myDequeStudy {
    public static void main(String[] args){
        Deque deque = new ArrayDeque();

        deque.addFirst(1);
        deque.addFirst(2);
        deque.addFirst(3);
        System.out.println("deque = " + deque);

        deque.addLast(10);
        deque.addLast(20);
        deque.addLast(30);
        System.out.println("deque = " + deque);

        // Front
        System.out.println(deque.removeFirst());
        System.out.println(deque);

        // Rear
        System.out.println(deque.removeLast());
        System.out.println(deque);

        // Poll
        System.out.println(deque.pollFirst());
        System.out.println(deque);


        System.out.println(deque.pollFirst());
        System.out.println(deque.pollFirst());
        System.out.println(deque.pollFirst());
        System.out.println(deque.pollFirst());
        System.out.println(deque);

    }
}

• 출처: https://www.acmicpc.net/problem/25556

처음에 이거 내용 이해가 조금 어려웠는데, 구현은 그에 비해 쉬웠다. 여기서는 이해에 초점을 맞춰서 설명하겠다. (아래는 본인의 언어로 재구성한 문제 내용이다.)

포닉스는 길이가 $N$인 순열 $A$와 네 개의 비어 있는 스택을 가지고 있다.

• 순열을 오름차순으로 정렬하는 것이 목적

1. 순열 $A$의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
2. 순열 $A$의 모든 원소를 스택에 삽입했다면, 네 개의 스택에서 모든 수를 꺼낸다.
3. 꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.

Stack의 어떤 성질을 이용하는가?

Stack은 가장 마지막 값을 꺼낼 수 있다는 특징을 가진다. 이는 "가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다."와 일치하는 내용으로 Stack으로 구현이 가능할 것이다. (물론 문제에서 아예 Stack을 제시하고 있다.)

풀이

즉, 위의 상황을 다시 말하면 맨 뒤에 있는 수(즉, 가장 나중에 넣은 수)가 가장 큰 수가 되어야 한다. 예를 들어, $5,4,3,2,1$ 가 있다고 하자.

• "5"은 1번째 스택에 들어간다.
• "4"은 2번째 스택에 들어간다.
• "3"은 3번째 스택에 들어간다.
• "2"은 4번째 스택에 들어간다.
• "1"은 스택은 4개뿐이라 들어갈 곳이 없다. "1"은 어디에 들어가도 가장 큰 수가 될 수 없다.

즉 우리는 들어갈 스택이 없는 수가 발생하는 경우를 잡으면 된다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력 1
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] array = new int[num];
        Stack<Integer>[] stackList = new Stack[4];
        int cnt = 0;

        // 입력 2
        for (int i = 0; i < num; i++) {
            array[i] = sc.nextInt();
        }

        // 포스택 생성

        for (int i = 0; i < 4; i++) {
            stackList[i] = new Stack<>();
        }

        // 조건 처리

        for (int item: array){
            for (Stack stack: stackList){
                if (stack.isEmpty() || (int) stack.peek() <= item){
                    stack.push(item);
                    cnt ++;
                    break;
                }
            }
        }

        // 출력

        if (cnt == num){
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }

    }
}

아직 입력이 익숙하지 않아, Scanner를 통해 단순하게 받아왔다.

핵심1. 조건 처리

        // 조건 처리

        for (int item: array){
            for (Stack stack: stackList){
                if (stack.isEmpty() || (int) stack.peek() <= item){
                    stack.push(item);
                    cnt ++;
                    break;
                }
            }
        }

for문 2번을 활용하여 순열 A에서 숫자를 하나씩 꺼내고, 이를 Stack에 하나씩 넣어보는 시도를 진행한다.

조건1. 스택이 비었거나 조건2. 스택의 가장 위의 값보다 숫자 값이 큰 경우

Stack에 해당 숫자를 넣고 cnt를 증가시켜준다.

핵심2. 출력

        // 출력

        if (cnt == num){
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }

스택에 넣은 횟수(cnt)와 수열의 길이 (num)를 비교하여 모든 수를 Stack에 넣었다면 "YES"를 출력한다.

느낀 점

아직 입력 함수가 익숙하지 않아, 이를 일부 찾아봤다. 또한, 문제에서 쓰이는 아이디어가 다소 겹치는듯 보이는데 이에 대한 유형화 / 아이디어 정리를 같이 하면 좋을 것 같다.

개념 정리

Stack은, 가장 대표적으로 순서가 보존되는 데이터 구조로, 아래와 같은 그림으로 직관적으로 표기될 수 있다.

그림에서 표현되듯이, 가장 나중에 들어온 데이터가 가장 먼저 나가게 되며 이를 LIFO (Last in Frist Out)이라고도 부른다.

주요 기능

가장 윗단을 가리키는 커서를 top이라고 부르며 값을 넣는 행위를 push(), top의 값을 꺼내는 행위를 pop(), top의 값을 확인하는 행위를 peek()으로 표현한다. Java에서는 java.util.Stack을 통해 표현되며 함수를 사용하는 방법도 위의 함수명과 동일하다.

public class myStackStudy {
    public static void main(String args[]){
        Stack stack = new Stack();
        System.out.println("== Push ==");
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println("stack = " + stack);
        System.out.println("== Pop ==");
        System.out.println(stack.pop());
        System.out.println("stack = " + stack);
        System.out.println("== Peek ==");
        System.out.println(stack.peek());
        System.out.println("stack = " + stack);
        System.out.println("== Contains ==");
        System.out.println(stack.contains(1));
        System.out.println("== Size ==");
        System.out.println(stack.size());
        System.out.println("== Clear ==");
        stack.clear();
        System.out.println(stack.size());

    }
}

어디서 사용하는가?

Stack은 주로 최근 값의 데이터를 꺼내 쓸 때 사용하며, 컴퓨터의 "실행 취소"를 생각하면 이해하기 쉬울 것 같다.

예1. reverseString()

    public static String reverseString(String str){
        Stack stack = new Stack();
        String result = "";

        for (String s: str.split("")){
            stack.push(s);
        }

        while (!stack.isEmpty()){
            result = result + stack.pop();
        }
        return result;
    }

String을 반대로 뒤집는 함수로, 끝 값부터 꺼내온다는 점에서 Stack이 적합하다.

TIP) 문자열 -> 잘라서 저장하는 법

        // 방법1. split() 활용
        for (String s: str.split("")){
            stack.push(s);
        }

        // 방법2. toCharArray() 활용
        for (char c: str.toCharArray()){
            stack.push(c);
        }

예2. 전위 / 중위 / 후위 표기식

public static double calculate(String string){
        Stack<Double> stack = new Stack();
        for (String s: string.split(" ")){
            if (s.equals(("+"))){
                stack.push(stack.pop() + stack.pop());
            } else if (s.equals("-")){
                stack.push(- stack.pop() + stack.pop());
            } else if (s.equals("*")){
                stack.push( stack.pop() * stack.pop());
            } else if (s.equals("/")){
                stack.push( 1/stack.pop() * stack.pop());
            } else {
                stack.push(Double.parseDouble(s));
            }
        }
        return stack.pop();
    }

전위, 중위, 후위 표기식의 예시로, 연산을 만나면 2개의 값을 pop()하고, 그 외에는 push()를 하는 방법에 주목하자.