Classic_Blue_Note

자바에서는 자료구조를 사용할 때, Collection이라는 객체를 이용한다.

Collection이라는 인터페이스를 기반으로 내부에 객체를 저장하고, 조작할 수 있느 구조를 제공하고 있으며, Collection 인터페이스를 기반으로 만들어지기 때문에 Java Collection Framework라고 명명하고 있다.

Iterable 인터페이스와 Collection 인터페이스를 기반으로, List, Queue, Set이 존재하고, 그 외에도 Collection 인터페이스 기반은 아니지만, 데이터를 효율적으로 관리한다는 측면에서 일반적으로 Map도 함께 이야기되고 있다.

Collection 프레임워크의 경우 여러 가지 형태의 구현체로 만들어져 있기 때문에, 다양한 자료 구조의 특징을 알고 자신이 작성하고자 하는 프로그램에서 유용하거나 효율적인 자료구조가 어떤 것일지를 선택하는 것이 중요하다.

각 인터페이스들은 인터페이스 하위의 구현체로 구현되고, Java 코드 내에서 사용하기 위해 인터페이스에 구현 객체를 생성하여 부여하는 식으로 사용된다. 아래의 코드는 Integer를 원소로 갖는 arraylist라는 이름의 List 인터페이스를 ArrayList를 이용하여 구현한다는 의미이다.

List<Integer> arraylist = new ArrayList<>();

이때, 다양한 프로그래밍을 하다 보면 인터페이스 자체는 동일하지만 구현체만 변경해 줘야 할 필요성이 있는 경우가 있다. 따라서 인터페이스와 구현체를 분리해 주는 것을 권장한다.

ArrayList<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();

list1과 list2의 경우, 코드를 사용함에 있어서 구현상 차이는 존재하지 않는다. 하지만 성능을 측정해 본 결과, ArrayList가 아닌 LinkedList로 구현체를 변경할 필요가 있을 때, list2의 경우 인터페이스가 아닌 구현체 부분만 변경해 주면 되지만, list1의 경우 인터페이스와 구현체를 모두 변경해 주어야 한다. 따라서, 객체 지향프로그래밍에서의 가장 큰 장점인 확장성을 이용하지 못하게 되는 것이다. 따라서 객체지향 프로그래밍 언어의 대표격인 Java에서는 list2와 같이 구현하는 것을 권장하고 있다.

1. List

List 인터페이스는 순서가 존재하는 것이 가장 큰 특징이다. 각 구현체별 특징은 아래와 같다.

2. Queue

순서가 있는 데이터 중, 선입선출을 보장하는 리스트로 볼 수 있다.  Queue의 하위 인터페이스로 Deque가 존재하는데, Deque 인터페이스의 경우 양쪽에서 요소를 제거 및 추가할 수 있다. Deque는 ArrayQueue와 LinkedList 두 가지 구현체가 존재하는데, 이는 역시 Queue의 구현체로 사용될 수 있다. 각 구현체별 특징은 아래와 같다.

3. Set

순서가 없는 데이터의 집합을 의미한다. 데이터의 중복을 허용하지 않는다. 위의 사진에서, Set이라는 인터페이스 하위에 SortedSet이라는 인터페이스가 존재하는 것을 볼 수 있는데, SortedSet의 경우 요소에 대한 순서를 제공하는 Set 자료구조를 의미한다. SortedSet의 경우 구현체로 TreeSet만 존재한다. Set의 구현체별 특징은 아래와 같다.

4. Map

키-밸류 쌍을 기반으로 데이터를 저장하는 자료 구조를 의미한다. 키의 경우 중복을 허용하지 않고, 밸류의 경우 중복이 가능하다. 맵은 일반적으로 키를 기반으로 밸류를 검색/갱신/삭제해야 하는 경우에 유용하게 사용될 수 있다. Map의 하위 인터페이스로 SortedMap이 존재하는데, 키 값에 대한 순서가 존재하는 Map 자료구조를 의미한다. SortedMap의 경우 구현체로 TreeMap만 존재한다. Map의 구현체별 특징은 아래와 같다.

참고문헌

- https://www.javatpoint.com/collections-in-java

- https://www.javatpoint.com/java-map

문제

www.acmicpc.net/problem/2504

풀이

해당 문제는 스택을 이용한 연산을 진행하는 문제이다.

문제 자체를 구현하는데는 시간이 많이 걸리지는 않았으나, 예외 처리 과정에서 디버깅 시간이 많이 걸린 문제였다.

식 자체가 틀린 경우 0을 출력해야 하기 때문에, 리턴을 이용하여 한번에 끝낼 수 있도록 함수를 만들어서 사용하였고, 다양한 조건식을 이용해야 했다.

코드 흐름을 간단히 해설해 보면, 우선 식을 입력받은 뒤, for문을 이용하여 차례대로 탐색을 진행한다.

이 과정에서, try-except 문을 통째로 넣어서, 스택의 크기가 0인데 pop하는 상황이 발생하면 에러가 발생하기 때문에, 해당 에러가 발생할 시 식에 오류가 있다고 판단하고, 바로 0을 리턴할 수 있도록 했다.

이후 정상적인 식일 경우 조건문을 살펴보자.

우선 스택에 아무 값이 없는데 ) 또는 ]가 입력되었을 경우 비정상 식이라고 판단한다.

그리고 비정상 식이 아닌 경우, [나 (가 입력되면 우선 스택에 넣어 둔다.

그리고 이렇게 스택에 쭉 넣어가다가, ]나 )가 입력되는 경우를 확인해 보자.

]나 )가 입력되면, 그 순간부터 스택의 값들을 pop해나가면서 그에 대응되는 반대쪽 괄호가 나올때까지 연산을 진행해 주면 된다.

예를 들어 생각하면, ([]) 라는 식이 있을 때, 해당 식을 (3)으로 만들고, 해당 식을 다시 6으로 만드는 과정인 것이다.

이때 스택에서의 상황을 보면, "(, ["가 들어있다가, ]를 만나면서 [가 pop되고, []이 3으로 변환되어 다시 스택에 들어가면, "(, 3"이 된다.

이러한 형태로 반복 연산을 진행하고, 이때 괄호가 ]를 만나면서 pop을 진행하면 다음 [를 만나기 전까지 스택 내부에는 숫자만 존재해야 하기 때문에 int 형태의 값이 아닌 경우 잘못된 식으로 판단했다.

이런 상황에서 [이후에 바로]을 만나거나, (이후 바로 )를 만나는 경우의 예외처리를 위해 loop_flag라는 값을 이용하여 해당 경우에는 기존 값들을 더하는 것이 아니라, 3또는 2가 바로 스택에 들어갈 수 있도록 처리해 주었다.

이후 마지막에 연산이 모두 끝난 후, 스택의 값들을 확인하여 모두 숫자일 경우 더하고, 숫자가 아닌 값이 하나라도 존재할 경우 식에 오류가 존재한다고 판단하였다.

코드

exp = input()


def cal(expression):
    stack = []
    loop_flag = False
    for i in expression:
        try:
            if len(stack) == 0 and i in "])":
                return 0
                
            if i in "[(":
                stack.append(i)
                
            elif i == "]":
                tmp = stack.pop(-1)
                tmp_num = 0
                while tmp != "[":
                    loop_flag = True
                    if type(tmp) == int:
                        tmp_num += tmp
                    else:
                        return 0
                    tmp = stack.pop(-1)
                if not loop_flag:
                    tmp_num = 1
                loop_flag = False
                tmp_num *= 3
                stack.append(tmp_num)
                
            else:
                tmp = stack.pop(-1)
                tmp_num = 0
                while tmp != "(":
                    loop_flag = True
                    if type(tmp) == int:
                        tmp_num += tmp
                    else:
                        return 0
                    tmp = stack.pop(-1)
                if not loop_flag:
                    tmp_num = 1
                loop_flag = False
                tmp_num *= 2
                stack.append(tmp_num)

        except:
            return 0
            
    val = 0
    
    for i in stack:
        if type(i) == int:
            val += i
        else:
            return 0
    return val


print(cal(exp))

문제

www.acmicpc.net/problem/10799

풀이

스택을 사용하는 문제이다. 스택 개념을 이용하되, 예외 처리를 충분히 해 줘야 한다.

처음에는 해당 문제를 풀 때 플래그를 사용하지 않고, )를 만나면 바로 스택의 길이만큼 더해 주었다. 하지만 그렇게 진행했을 경우, )를 2회 연속으로 만났을 때 문제가 발생했다. ) 이후에 )가 오는 상황은 레이저가 존재하는 상황이 아니고, 항상 막대가 끝나는 부분이기 때문에 이때 막대 전체를 자르는 것이 아니라, 막대가 끝난다는 의미로 코드를 진행시켜야 한다. 따라서, (다음에 )가 오는 경우는 레이저로 자르는 경우이기 때문에 그 때 존재하는 막대의 개수인 스택의 크기만큼 조각 개수를 추가해 주고, )다음에 )가 오는 경우는 막대가 끝나는 경우이기 때문에 마지막 조각이라는 의미로 1만큼 조각 개수를 추가해 주었다. 해당 부분은 플래그 변수를 이용해서 구성했다.

코드

exp = input()


stack = []
piece = 0
flag = False

for i in exp:
    if i == "(":
        stack.append(i)
        flag = False
    else:
        if flag:
            stack.pop(-1)
            piece += 1
        else:
            stack.pop(-1)
            piece += len(stack)
            flag = True

print(piece)

문제

www.acmicpc.net/problem/1935

풀이

후위 표기식을 스택을 이용하여 연산하는 문제이다.

우선 알파벳을 인식하기 위해, 파이썬의 in 연산을 사용하였으며, 인덱스 값을 통해 알파벳에 해당하는 숫자를 확인하였다.

이후 스택에 값을 넣어 가면서 연산자가 나오면 스택의 값을 빼내서 연산하는 과정을 반복하였다.

출력 시 소수 아래 2번째 자리까지 출력하기 위해 % 서식을 이용하여 문자열 포매팅을 진행하였다.

코드

N = int(input())

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

stack = []
exp = input()
data = []

for i in range(N):
    data.append(int(input()))

for i in exp:
    if i in alphabet:
        stack.append(data[alphabet.index(i)])
    else:
        stack.append(float(eval(str(stack.pop(-2)) + i + str(stack.pop(-1)))))
print("%0.2f" % stack[0])

문제

www.acmicpc.net/problem/1874

풀이

스택을 이용하여 수열을 완성해야 하는 문제이다. 기본적인 스택 사용법을 아는지에 대해 묻는 문제로, 약간의 생각을 필요로 하는 문제였다.

해당 문제에서의 핵심은 문제의 이해이다. 필자도 처음에는 문제 자체를 이해하는데 약간의 시간이 걸렸는데, 이후 스택을 어떤 식으로 사용하라는 말인지 이해한 후에는 쉽게 문제를 풀 수 있었다.

필자는 isstackable이라는 함수를 이용하여 문제를 풀이하였는데, 그 이유는 결과값이 불가능한 경우, NO를, 가능한 경우 어떤 연산을 진행했는지 순서대로 출력해야 하기 때문에, 함수 내부에서 리턴 값을 이용하여 불가능한 경우에는 "NO"라는 원소 하나를 가진 리스트로, 가능한 경우에는 연산 리스트를 리턴하도록 했다. 그리고 해당 값을 이터레이터를 이용하여 순차적으로 출력하는 과정을 통해 출력을 용이하게 할 수 있도록 풀이하였다.

함수의 내부 동작 원리는 우선 기본 숫자 배열을 만든다. 이후 두 개의 인덱스를 이용하여 하나는 기본 숫자 배열을 가리키고, 하나는 입력값 숫자 배열을 가리키도록 이용하여 스택의 가장 위 값과 입력값 숫자 배열의 인덱스 위치의 원소가 일치하지 않을 경우 기본 숫자 배열의 값을 스택에 넣고 다음 인덱스로 넘어가는 식으로 구성하였으며, 스택이 비어 있는 경우에는 무조건 스택에 원소를 넣도록 구현하였다.

이후 과도한 오버헤드를 방지하기 위해 기본 숫자 배열의 마지막 원소까지 1차적으로 확인이 끝났으면 이제 남은 원소는 모두 스택 안에 존재하는 것이기 때문에 스택의 모든 값을 빼내고, 새롭게 만들어진 배열과 처음에 입력받은 배열이 서로 같은지 확인을 통해 스택을 통해 해당 배열을 만드는 것이 가능한지 확인하고, 결과값에 따라 리턴하였다.

해당 문제는 디버그 과정에서 약간 시간을 썼는데, 처음에는 마지막 스택을 완전히 마무리하는 과정에서 연산자 리스트에 pop했다는 내용을 넣어주지 않아서 틀린 결과가 나왔었다. 결국 디버깅이 알고리즘 연습의 시간을 좌우한다는 생각이 들었으며, 하나하나 차근차근히 디버깅하는 습관을 가지면 어떤 문제든 해결할 수 있을 것이라고 믿는다.

코드

import sys

N = int(input())

final_data = [int(sys.stdin.readline()) for i in range(N)]


def isstackable(final_data):
    data = [i for i in range(1, N + 1)]
    op_list = []
    stack = []
    my_data = []
    idx = 0
    idx2 = 0
    while idx2 < len(data):
        if len(stack) == 0:
            stack.append(data[idx2])
            idx2 += 1
            op_list.append("+")
            continue
        if stack[-1] != final_data[idx]:
            stack.append(data[idx2])
            idx2 += 1
            op_list.append("+")
        else:
            idx += 1
            my_data.append(stack.pop(-1))
            op_list.append("-")
    for i in stack[::-1]:
        my_data.append(i)
        op_list.append("-")
    if my_data == final_data:
        return op_list
    else:
        return ["NO"]


ans = isstackable(final_data)
for i in ans:
    print(i)

문제

www.acmicpc.net/problem/2164

풀이

큐 자료구조를 사용하는 문제이다. 선입선출의 원리를 이용한다.

자료구조는 python collections 모듈의 deque를 사용했고, 해당 자료구조를 이용하여 큐를 구현하였다.

큐 자료구조의 원리를 안다면 간단히 풀리는 문제이다.

종종 인덱스 에러가 발생하는 경우가 있는데, 인덱스 에러가 발생할 경우 경계값 부분을 디버깅 해 볼 필요가 있다. 조건을 확인하고, 해당 조건에서는 1과 500000이 경계값이므로 해당 값이 적절하게 들어가는지 확인해 볼 필요가 있다.

코드

from collections import deque

N = int(input())

queue = deque()

for i in range(N):
    queue.appendleft(i+1)

while True:
    if len(queue) == 1:
        break
    queue.pop()
    tmp = queue.pop()
    queue.appendleft(tmp)

print(queue[0])