P-coding

이번 글에서는 백준 26069번 문제를
hashSet를 활용해서 풀어보자

문제 핵심

• N : 사람들이 만난 기록 수
• 최대 길이 20의 문자열인 다른 문자열 A와 B가 공백과 함께 한줄에 주어진다.
• ChongChong 기록에서 1회 이상 주어짐
• ChongChong을 만난 사람은 무지개 댄스에 감염
  • ( ChongChong과 chongchong은 다른 이름 )

풀이 과정

ChongChong을 만난 순간 무지개 댄스를 추게 된다.

즉, 무지개 댄스를 한 명이라도 추고 있다면 모두 HashSet에 넣는다.

(Hash)Set에서는 중복값을 제외시켜 저장하기 때문에 모든 입력이 끝난 후  HashSet의 크기를 측정 한다. 

핵심 코드

1. 한 줄씩 읽어온다.

2. 두 사람 모두 댄스를 무지개 댄스를 추는지 확인

3. 한 명이라도 춘다면 HashSet에 삽입

        rainbowDanceHumans.add("ChongChong");
        for (int i = 0; i < N; i++) {
           stringTokenizer = new StringTokenizer(bufferedReader.readLine());
           String firstPerson = stringTokenizer.nextToken();
           String secondPerson = stringTokenizer.nextToken();

           if(rainbowDanceHumans.contains(firstPerson) || rainbowDanceHumans.contains(secondPerson)) {
               rainbowDanceHumans.add(firstPerson);
               rainbowDanceHumans.add(secondPerson);
           }
        }

Set에 특성만 활용한다면 아주 쉽게 풀 수 있는 문제이다.

(추가) 다들 환절기에 몸 조심 하시길 바랍니다.
두통에 2일 간 작성하지 못했네요..
백준 문제뿐만 아니라 Java class나 다양한 예제로 찾아 뵙겠습니다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;
        int N = Integer.parseInt(bufferedReader.readLine());

        HashSet<String> rainbowDanceHumans = new HashSet<>();

        rainbowDanceHumans.add("ChongChong");
        for (int i = 0; i < N; i++) {
           stringTokenizer = new StringTokenizer(bufferedReader.readLine());
           String firstPerson = stringTokenizer.nextToken();
           String secondPerson = stringTokenizer.nextToken();

           if(rainbowDanceHumans.contains(firstPerson) || rainbowDanceHumans.contains(secondPerson)) {
               rainbowDanceHumans.add(firstPerson);
               rainbowDanceHumans.add(secondPerson);
           }
        }

        System.out.println(rainbowDanceHumans.size());

    }
}

이번글에서는 백준 25192번 문제를 통해 집합과 맵에 대해 알아보고자 한다.
원래는 집합과 맵에 대해 설명하고 문제를 포스팅하지만,
해시, 트리, 맵, 집합 자바에서는 함께 사용되기 때문에
추후에 포스팅 하려고 한다.

문제 핵심

• N : 채팅방 총 기록 수
• ENTER : 사람의 입장
• 나머지 : 유저의 닉네임
• 구하려는 값 : 곰곰티콘 사용횟수

풀이 과정

채팅 봇으로 ENTER이후 처음으로 나타난 닉네임은 인사하는 곰곰티콘이다.

즉, 동일한 닉네임이 두번 나타났다면 일반채팅으로 곰곰티콘이 아니다.

우리는 곰곰티콘을 사용하는 순간으로 ENTER 이후 나타나는 닉네임을 한 번씩 체크하면 된다.

즉, Set 클래스를 이용해서 중복없이 저장하여 그 크기를 통해 알 수 있다.

핵심 코드

1. 한 줄씩 읽어온다.

2. ENTER인 HashSet을 초기화

3. 존재하지 않는 경우에만 값을 넣고 카운트 증가

HashSet<String> nickNames = new HashSet<>();

for (int i = 0; i < recordCount; i++) {

    String line = bufferedReader.readLine();

    if(line.equals("ENTER")) {
        nickNames.clear();
        continue;
    }

    if(!nickNames.contains(line)){
        nickNames.add(line);
        bearGreetCount++;
    }
}

다른 풀이

HashSet 클래스를 사용하며 Set이라는 클래스 의미를 생각하면 사실 위 코드는 Set 보다는 Hash를 이용하여 값을 빨리 찾아내는 방식이다. Set이라는 클래스도 모두 이용하려면 다음과 같다.

1. ENTER가 나온 경우에만 지금까지 넣었던 값 개수를 카운트 해주고 초기화 한다.

2. 이후 반복문이 종료된 이후에는 카운트 되지 않은 값들이 남아있기 때문에 추가로 카운트 한다.

HashSet<String> nickNames = new HashSet<>();

for (int i = 0; i < recordCount; i++) {

    String line = bufferedReader.readLine();

    if(line.equals("ENTER")) {
    	bearGreetCount += nickNames.size();
        nickNames.clear();
        continue;
    }

    nickNames.add(line);

}

bearGreetCount += nickNames.size();

이번 문제에서 사용한 HashSet 또한 다른 문제 풀이에 자주 사용되는 클래스이다.
Hash, Set, Map, Tree 등 다양한 구조를 이해하는 것이 좋다.
기본 구조로써 기본 개념을 숙지하고 넘어가자.

전체 코드

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

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

        int recordCount = Integer.parseInt(bufferedReader.readLine());

        int bearGreetCount = 0;

        HashSet<String> nickNames = new HashSet<>();

        for (int i = 0; i < recordCount; i++) {

            String line = bufferedReader.readLine();

            if(line.equals("ENTER")) {
                nickNames.clear();
                continue;
            }


            if(!nickNames.contains(line)){
                nickNames.add(line);
                bearGreetCount++;
            }
        }

        System.out.println(bearGreetCount);
    }
}

이번 글에서는 백준 1037번 문제를 통해,
알고리즘 기본 문제 단골인 소수, 약수, 공배수 들 중 하나인 약수를 활용하여 문제를 풀어보자

문제 핵심

• 첫째 줄 : 약수의 개수
• 둘째 줄 : 약수들
• 구하려는 정수 : N
  • ( 풀이 과정에서는 구하려는 정수 N을 x라고 설명 )

풀이 과정

자연수 x을 구하려면 1과 x을 제외한 주어진 약수 중에서 선택해야 한다.

만약 이 때 조건과 같이 30의 약수를 차례대로 나열하면 [ 2, 3, 5, 6, 10, 15 ] 이다.

그렇다면 양쪽에서 순서대로 모두 짝지어서 곱한다면 x인 30을 구할 수 있다.

즉, 제일 큰 값과 작은 값을 구한 후 곱해주면 된다.

핵심 코드

for (int i = 0; i < N; i++) {
    int num = Integer.parseInt(stringTokenizer.nextToken());
    if(num > max) {
        max = num;
    }
    if(num < min) {
        min = num;
    }
}

예외

9와 같은 약수는 1과 9는 제공되지 않기 때문에 3 숫자 하나만 주어진다.

이때 3의 제곱이 x가 되므로 첫째 줄이 1이라면 제곱해준다.

if(N == 1) {
    int num = Integer.parseInt(bufferedReader.readLine());
    stringBuilder.append(num * num);
}

단계적 풀이에서 브론즈 문제 수준으로
사실 비교적 아주 쉬운 문제이다.

이제는 마지막 브론즈 문제로 앞으로는 실버 상위부터 골드 문제가 다량으로 나올 예정이다.
지금까지 기초와 개념을 활용한다면 문제없이 풀 수 있을 것이다.

전체 코드

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;
        StringBuilder stringBuilder = new StringBuilder();
        int N = Integer.parseInt(bufferedReader.readLine());

        if(N == 1) {
            int num = Integer.parseInt(bufferedReader.readLine());
            stringBuilder.append(num * num);
        } else {
            int max = 0;
            int min = Integer.MAX_VALUE;

            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int i = 0; i < N; i++) {
                int num = Integer.parseInt(stringTokenizer.nextToken());
                if(num > max) {
                    max = num;
                }
                if(num < min) {
                    min = num;
                }
            }

            stringBuilder.append(max * min);
        }

        System.out.println(stringBuilder);

    }
}

이번 글에서는 백준 110번 문제를 통해 이항계수를 활용하고
최대 값을 넘어서는 순간을 다루는 방법을 알아보자.

문제 핵심

• 서쪽 ( N )
• 동쪽 ( M )
• N <= M
• 최대 한 개의 다리만 연결

풀이 과정

이 문제는 조합론으로 mCn이라고 할 수 있다.

다만 M의 최대값이 30일 때 factorial의 값은 다음과 같다.

• 1! = 1
• 2! = 2
• 3! = 6
• 4! = 24
• 5! = 120
• 6! = 720
• 7! = 5040
• 8! = 40,320
• 9! = 362,880
• 10! = 3,628,800
• 11! = 39,916,800
• 12! = 479,001,600
• 13! = 6,227,020,800
• 14! = 87,178,291,200
• 15! = 1,307,674,368,000
• 16! = 20,922,789,888,000
• 17! = 355,687,428,096,000
• 18! = 6,402,373,705,728,000
• 19! = 121,645,100,408,832,000
• 20! = 2,432,902,008,176,640,000
• 21! = 51,090,942,171,709,440,000
• 22! = 1,124,000,727,777,607,680,000
• 23! = 25,852,016,738,884,976,640,000
• 24! = 620,448,401,733,239,439,360,000
• 25! = 15,511,210,043,330,985,984,000,000
• 26! = 403,291,461,126,605,635,584,000,000
• 27! = 10,888,869,450,418,352,160,768,000,000
• 28! = 304,888,344,611,713,860,501,504,000,000
• 29! = 8,841,761,993,739,701,954,543,616,000,000
• 30! = 265,252,859,812,191,058,636,308,480,000,000

한계는 이미 초과했다.

이 때 우리는 각 프로그래밍언어에서 제공하는 클래스를 사용하면 된다.

Java에서는 BigInteger가 있다.

핵심 코드

이항 계수1 문제 처럼 나왔지만 이번에는 동쪽이 숫자가 항상 크다.

( 값을 받을 때 반대로 받았다. 헷갈리지 않게 N M으로 선언하는게 좋다. )

int T = Integer.parseInt(bufferedReader.readLine());
int N, K;
BigInteger result;

for (int i = 0; i < T; i++) {
    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
    K = Integer.parseInt(stringTokenizer.nextToken());
    N = Integer.parseInt(stringTokenizer.nextToken());


    result = factorial(N).divide(factorial(K).multiply(factorial(N - K)));
    stringBuilder.append(result).append("\n");
}

이번 문제는 자료형의 최대값을 한참 넘어서기 때문에,
그 부분만 해결할 수 있다면 이전 이항계수 문제를 활용해 아주 쉽게 풀 수 있는 문제이다.

꼭 BigInteger같은 클래스를 사용하지 않더라도 비슷한 방식으로
직접 문자로 만들어서 처리하는 방법도 존재한다.

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {

    public static BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;
        StringBuilder stringBuilder = new StringBuilder();

        int T = Integer.parseInt(bufferedReader.readLine());
        int N, K;
        BigInteger result;

        for (int i = 0; i < T; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            K = Integer.parseInt(stringTokenizer.nextToken());
            N = Integer.parseInt(stringTokenizer.nextToken());


            result = factorial(N).divide(factorial(K).multiply(factorial(N - K)));
            stringBuilder.append(result).append("\n");
        }

        System.out.println(stringBuilder);
    }
}

다음 문제를 통해 재귀 함수와 이항계수를 활용해 보자.

---

 

문제 핵심

• N : 자연수
• K : 정수

풀이 과정

이항 계수는 다음과 같은 공식에 따라 이루어 진다. 이걸 코드로 구현해 보자.

재귀 방식

재귀를 통해 factorial를 해결한다.

public static int factorial(int n){
    if(n == 1){
        return 1;
    }
    return factorial(n-1) * n;
}

반복문 방식

반복문을 통해 factorial를 해결한다.

public static int factorial(int n){
    int result = 1;
    for (int i = n; i > 1; i--){
        result *= i;
    }
    return result;
}

int result = factorial(N) / (factorial(K) * factorial(N - K));

재귀 방식은 위와 같이 StackOverflow현상이 일어났다.
자바의 JVM의 기준 스택 크기의 한계 때문에 재귀 함수 호출 과정에서
StackOverflow현상이 일어난 것으로 보인다.

때문에 반복문을 통해 이를 해결하였다.

이번 글에서는 백준 2346번 문제를 통해
queue 개념에 관해 좀 더 복잡한 문제를 풀어보자

문제 핵심

• N : 풍선의 개수 ( 자연수 ) 1 ~ 1000
• 각 종이에 이동할 숫자가 적혀 있다. ( 0은 없다 )
• 적힌 종이 별로 양수면 오른쪽, 음수는 왼쪽으로 이동한다.

풀이 과정

다음 Deque를 통해 문제를 풀어 나가며, 인덱스를 기억해 두는 것이 핵심이다.

1. 풍선 번호와 종이 저장

1. 큐에 인덱스 값들을 저장한다.

2. move 정수 배열에 해당 종이를 저장한다.

        Deque<Integer> indexQueue = new ArrayDeque<Integer>();

        int[] move = new int[N];
        for (int i = 0; i < N; i++) {
            move[i] = Integer.parseInt(stringTokenizer.nextToken());
            indexQueue.add(i);
        }

2. 반복

첫 시작은 앞에서부터 시작하기 때문에 미리 처리 한다.

큐에서 꺼낸 값은 인덱스 값이고, 이 인덱스 값을 가지고 move 정수 배열에서 이동할 거리를 확인할 수 있다.

        int removeIndex = indexQueue.removeFirst();
        stringBuilder.append(removeIndex + 1).append(" ");

값을 제외한 후에 for문을 통해 값을 원형 큐 처럼 뒤로 보내기 때문에 -1 한다.

ex) 3번 이동해야 할 때, 값을 제거한다면, 값들이 땡겨지기 때문에 2번 이동한다.

        while(!indexQueue.isEmpty()) {
            int step = move[removeIndex];

            if(step < 0) {
                for(int j = 0; j < -step - 1; j++) {
                    indexQueue.addFirst(indexQueue.removeLast());
                }
                removeIndex = indexQueue.removeLast();

            } else {
                for(int j = 0; j < step - 1; j++) {
                    indexQueue.addLast(indexQueue.removeFirst());
                }
                removeIndex = indexQueue.removeFirst();
            }
            stringBuilder.append(removeIndex + 1).append(" ");
        }

아래의 실패 코드로 이중 리스트 구조로 만들었으나 메모리 초과로 실패하게 되었다.
이 후 불필요한 메모리를 제거하기 위해 분리하여 생성하였고, 성공하였다.

물론 여러 방법 중 하나이니 '틀리다' 라고 말할 수 없겠지만, 
이번 경우는 불필요한 메모리 사용으로 틀렸다고 생각한다.

요즘 컴퓨터 성능은 메모리나 속도면에서 문제 없지만, 막대한 수치가 들어온다면 영향을 끼친다.
때문에 '불필요한' 코드는 줄이도록 하자

실패 코드

다음과 같이 큐 안에 index와 종이의 값들을 모두 넣어서 처리하였으나 과도하게 메모리가 사용되어 메모리 초과되었다.

이후 불필요한 메모리를 제거하기 위해 분리하여 생성하였다.

        Deque<int[]> queue = new LinkedList<>();

전체 코드

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(input.readLine());
        StringTokenizer stringTokenizer = new StringTokenizer(input.readLine());
        StringBuilder stringBuilder = new StringBuilder();
        Deque<Integer> indexQueue = new ArrayDeque<Integer>();

        int[] move = new int[N];
        for (int i = 0; i < N; i++) {
            move[i] = Integer.parseInt(stringTokenizer.nextToken());
            indexQueue.add(i);
        }

        int removeIndex = indexQueue.removeFirst();
        stringBuilder.append(removeIndex + 1).append(" ");

        while(!indexQueue.isEmpty()) {
            int step = move[removeIndex];

            if(step < 0) {
                for(int j = 0; j < -step - 1; j++) {
                    indexQueue.addFirst(indexQueue.removeLast());
                }
                removeIndex = indexQueue.removeLast();

            } else {
                for(int j = 0; j < step - 1; j++) {
                    indexQueue.addLast(indexQueue.removeFirst());
                }
                removeIndex = indexQueue.removeFirst();
            }
            stringBuilder.append(removeIndex + 1).append(" ");
        }
        System.out.println(stringBuilder);
    }
}

자료형 변환시 주로 ParseInt가 권장된다.
하지만 valueOf 함수도 있는데 왜 저걸 권장할까?

ParseInt()

Java 라이브러리에서 ParseInt()는 다음과 같이 정의하고 있다.

public static int parseInt(String s) throws NumberFormatException {
    return parseInt(s,10);
}

기본 자료형( int )로 반환하며, 오버로딩(Overloading) 되어서 다시 재정의가 이루어진다.

다음은 오버로딩 ( Overloading ) 전체 코드이다. 문자열( s )를 진법( radix )을 통해 변환이 이루어진다.

public static int parseInt(String s, int radix)
            throws NumberFormatException
{
    /*
     * WARNING: This method may be invoked early during VM initialization
     * before IntegerCache is initialized. Care must be taken to not use
     * the valueOf method.
     */

    if (s == null) {
        throw new NumberFormatException("Cannot parse null string");
    }

    if (radix < Character.MIN_RADIX) {
        throw new NumberFormatException("radix " + radix +
                                        " less than Character.MIN_RADIX");
    }

    if (radix > Character.MAX_RADIX) {
        throw new NumberFormatException("radix " + radix +
                                        " greater than Character.MAX_RADIX");
    }

    boolean negative = false;
    int i = 0, len = s.length();
    int limit = -Integer.MAX_VALUE;

    if (len > 0) {
        char firstChar = s.charAt(0);
        if (firstChar < '0') { // Possible leading "+" or "-"
            if (firstChar == '-') {
                negative = true;
                limit = Integer.MIN_VALUE;
            } else if (firstChar != '+') {
                throw NumberFormatException.forInputString(s, radix);
            }

            if (len == 1) { // Cannot have lone "+" or "-"
                throw NumberFormatException.forInputString(s, radix);
            }
            i++;
        }
        int multmin = limit / radix;
        int result = 0;
        while (i < len) {
            // Accumulating negatively avoids surprises near MAX_VALUE
            int digit = Character.digit(s.charAt(i++), radix);
            if (digit < 0 || result < multmin) {
                throw NumberFormatException.forInputString(s, radix);
            }
            result *= radix;
            if (result < limit + digit) {
                throw NumberFormatException.forInputString(s, radix);
            }
            result -= digit;
        }
        return negative ? result : -result;
    } else {
        throw NumberFormatException.forInputString(s, radix);
    }
}

1. 초기 예외 검사

문자열(s)가 null이면 변환이 불가 함으로 NumberFormatException 예외 발생

if (s == null) {
    throw new NumberFormatException("Cannot parse null string");
}

radix(진법)이 2~36 진법 범위 내에서만 변환 가능함으로 Min, Max 값 범위 예외 처리

if (radix < Character.MIN_RADIX) {
    throw new NumberFormatException("radix " + radix +
                                    " less than Character.MIN_RADIX");
}
if (radix > Character.MAX_RADIX) {
    throw new NumberFormatException("radix " + radix +
                                    " greater than Character.MAX_RADIX");
}

2. 부호 판별 및 기본 설정

부호 +(43), -(45)은 0(48)보다 아래이기 때문에 부호를 찾고 '+'은 무시 나머지 경우에만 처리한다.

'-'인 경우 음수로 설정하고, limit를 int 자료형의 변환이기 때문에 Integer.MIN_VALUE 로 설정한다.

        if (firstChar < '0') { // Possible leading "+" or "-"
            if (firstChar == '-') {
                negative = true;
                limit = Integer.MIN_VALUE;
            } else if (firstChar != '+') {
                throw NumberFormatException.forInputString(s, radix);
            }

길이가 1이라면 앞 부호 하나만 있기 때문에 예외 처리

        if (len == 1) { // Cannot have lone "+" or "-"
            throw NumberFormatException.forInputString(s, radix);
        }

3. 숫자로 변환

먼저 자릿수를 가져오고, digit가 0보다 작거나 오버플로우가 나는지 체크한다.

사실 이 코드만 보고 이해하기는 어려울 수 있다. 성공과 실패의 두 가지 예시가 있다.

        int multmin = limit / radix;
        int result = 0;
        while (i < len) {
            // Accumulating negatively avoids surprises near MAX_VALUE
            int digit = Character.digit(s.charAt(i++), radix);
            if (digit < 0 || result < multmin) {
                throw NumberFormatException.forInputString(s, radix);
            }
            result *= radix;
            if (result < limit + digit) {
                throw NumberFormatException.forInputString(s, radix);
            }
            result -= digit;
        }

ex) 성공한 연산 10진수 "2147483647"

 multmin = -2147483647 / 10 = -214748364

이 값을 통해 미리 오버플로우 발생을 예측한다.

마지막 결과에서 -2147483647을 부호판별 후 반환한다. -(-2147483647) = 2147483647

ex) 실패한 연산 10진수 "2147483648"

다음과 같은 결과로 ( result < limt + digit ) 조건이 참이 되어 예외가 발생하게 된다.

result = -2147483640
limit = -2147483647
digit = 8

limit + digit = -2147483647 + 8 = -2147483639

valueOf()

Java 라이브러리에서 valueOf()는 다음과 같이 정의하고 있다.

    public static Integer valueOf(String s) throws NumberFormatException {
        return Integer.valueOf(parseInt(s, 10));
    }

객체형으로 반환하고 있고, 여기서도 오버로딩( Overloading ) 했던 parseInt()가 보인다.

또 하나 valueOf 메서드도 오버로딩( Overloading ) 되었는데 다음과 같다.

1. 미리 생성된 값 IntegerCache.low(-128) ~ IntegerCache.high(127) 사이면 새 객체를 생성하지 않고 반환한다.

2. 그 값이 아니라면 새로 객체를 생성하여 반환한다.

( 미리 생성되는 값 범위는 JVM option에 따라 조정 가능 )

    @IntrinsicCandidate
    public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

(추가) parseInt() 사용 예

예제)

System.out.println(Integer.parseInt("123", 10));   // 123
System.out.println(Integer.parseInt("-123", 10));  // -123
System.out.println(Integer.parseInt("101", 2));    // 5 (2진수 변환)
System.out.println(Integer.parseInt("7F", 16));    // 127 (16진수 변환)
System.out.println(Integer.parseInt("Z", 36));     // 35 (36진수에서 'Z'는 35)
System.out.println(Integer.parseInt("007", 8));    // 7 (8진수)

예외발생)

System.out.println(Integer.parseInt("abc", 10));  // 예외 발생 (숫자가 없음)
System.out.println(Integer.parseInt("12345", 2)); // 예외 발생 (2진수 범위 초과)
System.out.println(Integer.parseInt("", 10));     // 예외 발생 (빈 문자열)
System.out.println(Integer.parseInt(null, 10));   // 예외 발생 (null)

결국 valueOf() 메서드도 parseInt()를 사용하며
Integer를 사용하지 않고, 정수만을 반환받기 원한다면 parseInt() 메서드를 사용해야 한다.
Integer객체를 통해 불필요하게 메모리를 사용하게 된다.

오늘은 자료구조의 기본 구조 중 하나인 큐에 대해서 알아보고자 한다.
가장 기본적인 구조로 선입선출 ( FIFO, First In First Out ) 방식을 가진다.
먼저 온 사람이 나가는 흔히 매장에 줄 서는 과정이라 볼 수 있다.
( Queue 단어 자체가 표 같은 것을 구매하기 위해 줄 서는 것을 의미 )

큐 ( Queue )

• 선입 선출 ( FIFO, First In First Out )
• 데이터가 들어오는 위치는 가장 뒤 Rear or Back 에서 이루어지고, 데이터가 나가는 위치인 가장 앞 Front, 양쪽에서 삽입 삭제가 이루어진다.
• BFS ( 너비 우선 탐색 ), 프로세서 핸들링 ( CPU 헤드링 ) 등에 사용.

class Queue{
    private LinkedList<Integer> queue;

    public Queue(){
        queue = new LinkedList<>();
    }
    ....
}

큐의 기본 연산

1. Enqueue(value): 데이터 삽입

• 큐의 맨 뒤(back)에 데이터를 추가하는 연산

    public void enQueue(int x){
        queue.addLast(x);
    }

2. Dequeue(): 데이터 제거

• 큐의 맨 앞(front)에 있는 데이터를 제거하고 반환하는 연산

    public int depQueue(){
        if(queue.isEmpty()){
            return -1;
        }
        return queue.removeFirst();
    }

3. peek() : 최상단 데이터 확인

• 큐의 맨 앞(front)에 있는 데이터를 반환하지만, 제거하지 않음

    public int peek(){
        if(queue.isEmpty()){
            return -1;
        }
        return queue.getFirst();
    }

4. isEmpty(): 큐이 비어 있는지 확인

• 큐가 비어 있으면 true, 아니면 false 반환

    public boolean isEmpty(){
        return queue.isEmpty() ? true : false;
    }

로직 예시)

1. 빈 큐다

2. Enqueue ( 2 ) 를 통해 가장 앞 부터 채워 넣는다.

3. Enqueue ( 4 ) 를 통해 2 다음에(뒤에서부터) 채워 넣는다.

4. Dequeue 릍 통해 가장 앞에 있는 2를 꺼내고 4를 앞으로 옮긴다.

추가 - JAVA의 큐 관련 클래스

자바에서 큐는 Interface로 구현되어 ArrayDeque, LinkedList, PriorityQueue로 직접 구현할 수 있다.

그 밖에도 Blocking 즉 고정된 크기의 배열을 사용하는 큐도 존재한다.

이는 자바에서 원형 큐의 고정된 크기를 구현하기 위함으로 보인다.

이 글에서는 LinkedList로 정의된 큐와 달리 양쪽에서 삽입과 삭제가 이루어질 수 있는 양방향 큐이며, 메모리 동적인 요소를 가지고 있다.

ArrayDeque도 비슷하나 LinkedList와는 다르다. 배열로 사용되며 동적으로 변하긴 하지만, 배열을 다시 늘려야하는 번거로움이 있다. 추후 ArrayList와 LinkedList의 차이에 대해 포스팅할 예정이다.

DeQueue

 양방향에서 삽입/삭제가 이루어 질 수 있는 양방향 큐를 의미한다.

원형 큐

blocking으로 정의된 큐는 원형 큐라고 할 수 있으며 다음과 같은 형태을 가진다.

데이터가 삽입/삭제 됨에 따라 front와 back(rear)를 가리키는 위치가 계속 변하지만, 크기는 고정된 상태로 이루어진다.

다음과 같이 예시를 볼 수 있다.

PriorityQueue

우선순위 큐로 우선순위 비교는 Comparable interface를 활용하여 구현하거나 Comparator를 사용하여 설정할 수 있다.

중복 요소를 허용하고, 정렬된 순서로 요소를 처리하기 때문에 성능에 영향이 줄 수 있는 큐다.

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(3);
queue.add(1);
queue.add(2);

System.out.println(queue.poll());  // 1 (가장 작은 값이 먼저 출력됨)

PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
queue.add(1);
queue.add(3);
queue.add(2);

System.out.println(queue.poll());  // 3 (가장 큰 값이 먼저 출력됨)

이미 많고 다양한 큐가 만들어져 있기 때문에
편한 방법과 편한 클래스가 자바처럼 다양하게 존재하지만,
기본 자료구조를 이해하지 못한다면 활용하기가 어렵다.
때문에 그걸 사용하기 이전에 기본에 대한 이해를 점검하고 사용하도록 하자.
( ctrl + 클릭 을 통해 자바 클래스 내부를 확인 할 수 있다. )

이번 글에서는 백준 28278번 문제를 통해
스택(자료구조)를 구현하고 활용해 보자.

문제 핵심

• N : 명령의 수 ( 1 <= N <= 1,000,000 )
• 명령 1 ~ 5 까지 주어진다.
• 1. Push
• 2. Pop
• 3. Size
• 4. IsEmpty
• 5. Peek
• 명령은 하나씩 주어진다.

풀이 과정

다음 문제는 스택을 구현하고 처리하는 과정이라고 할 수 있다.

1. 함수 구현하기

1 ~ 5의 명령어와 같이 스택에 필요한 함수들을 구현하자.

	private static int isEmpty() {
        if (list.isEmpty()) {
            return 1;
        }
        return 0;
    }

    private static Integer peek() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.getFirst();
    }

    private static Integer pop() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.removeFirst();
    }

    private static void push(int num) {
        list.addFirst(num);
    }

문제에 맞게 명령어들을 변형하여 함수를 구현하였다.

2. 구현한 함수 활용하기 ( Main 작성 )

• 문제를 다음과 같이 풀었지만, 1 ~ 5의 단순한 숫자나 문자열로 처리할 경우 Switch문이 더 적합하며 범위 계산이나 null 값 계산 등이 아니라면 Switch문으로 처리하는 것이 좋아 보인다.
• List 는 JAVA의 LinkedList<> 클래스를 활용하였다.
  • ArrayList or List를 활용해서 사용할 수 있기도 하지만, 미리 만들어두는 구조보다는 문제제목과 같은 자료구조에 맞춰서 사용하였다.

private static final LinkedList<Integer> list = new LinkedList<>();

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

        int num = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer;

        String command;

        for (int i = 0; i < num; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            command = stringTokenizer.nextToken();

            if (command.equals("1")) {
                push(Integer.parseInt(stringTokenizer.nextToken()));
            } else if (command.equals("2")) {
                stringBuilder.append(pop())
                        .append("\n");
            } else if (command.equals("3")) {
                stringBuilder.append(list.size())
                        .append("\n");
            } else if (command.equals("4")) {
                stringBuilder.append(isEmpty())
                        .append("\n");
            } else if (command.equals("5")) {
                stringBuilder.append(peek())
                        .append("\n");
            }

        }
        System.out.println(stringBuilder);
    }

백준에서는 여러 프로그래밍 언어 중 Java가 비교적 느린 편이기 때문에, 많은 사람이 속도 최적화에 집중하거나 단순히 문제를 해결하는 데만 초점을 맞춰 코드를 작성하는 경우가 많다. (물론 브론즈 ~ 실버 수준의 문제에서는 속도 차이가 크게 중요하지 않다.)

하지만 이러한 문제의 핵심은 스택을 직접 구현하고 이해하는 것에 있다.

예를 들어, 명령어가 4일 때 list.isEmpty() ? 1 : 0을 사용하면 간편하게 해결할 수 있다.
그러나 이는 LinkedList 클래스의 isEmpty() 메서드를 활용한 것이지,
우리가 구현해야 할 스택의 isEmpty()가 아니다.
비록 같은 기능을 수행하지만, 개념적으로 다른 의미를 가진다.

즉,
문제를 통과하는 것에만 집중하기보다는, 정확한 개념을 이해하고 접근하는 것이 더 중요하다.

전체 코드

물론 다음 코드도 완벽하지는 않다.

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    private static final LinkedList<Integer> list = new LinkedList<>();

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

        int num = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer;

        String command;

        for (int i = 0; i < num; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            command = stringTokenizer.nextToken();

            if (command.equals("1")) {
                push(Integer.parseInt(stringTokenizer.nextToken()));
            } else if (command.equals("2")) {
                stringBuilder.append(pop())
                        .append("\n");
            } else if (command.equals("3")) {
                stringBuilder.append(list.size())
                        .append("\n");
            } else if (command.equals("4")) {
                stringBuilder.append(isEmpty())
                        .append("\n");
            } else if (command.equals("5")) {
                stringBuilder.append(peek())
                        .append("\n");
            }

        }
        System.out.println(stringBuilder);
    }

    private static int isEmpty() {
        if (list.isEmpty()) {
            return 1;
        }
        return 0;
    }

    private static Integer peek() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.getFirst();
    }

    private static Integer pop() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.removeFirst();
    }

    private static void push(int num) {
        list.addFirst(num);
    }
}

Integer와 Int 같은 정수형을 나타내는 자료형으로 볼 수 있다.
하지만 이는 객체와 기본형으로 다르게 같지만서도 다르다.
이번에는 그 차이를 알아보자.

1. primitive type ( 기본형 )

• 값 자체를 스택 메모리에 직접 저장하는 Primitive 즉, 원시적인 자료형이다. 
• 별도의 정의가 필요없이 사용할 수 있으며 고정된 크기를 차지한다.
• 메소드를 사용할 수 없으며 값을 직접 저장하기 때문에 null 을 저장할 수 없습니다.

2. Wrapper Class ( 객체형 )

• 값은 힙 메모리에 객체에 저장되고, 스택 메모리는 그 객체를 가리키는 주소값을 저장한다.
• 참조형 데이터이기 때문에 추가적인 메모리가 소모된다.
• 기본 상태는 null로 초기화 된다.

3. 메모리 구조 예시 ( 정수 )

다음과 같은 코드를 적용할 때 그림과 같이 메모리에 할당된다.

int num = 10;
Integer num = Integer.valueOf(num);

차이점 요약

Wrapper Class는 제네릭 형태로 자주 사용되며,
특히 List<Integer> 와 같은 컬렉션 프레임워크에서 흔히 활용된다.
간단한 코드에서는 당연하게 사용하지만,
방대한 코드 작성 시에는 메모리나 성능, 기능적 요소를 고려해야 한다.
이러한 상황에 닥쳤을 때 비로소 이유를 고민하기보다, 미리 원리를 이해하고 사용하면 더 효율적일 것이다.