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

문제

programmers.co.kr/learn/courses/30/lessons/42885

풀이

해당 문제도 풀이 과정 자체는 떠올리기가 쉬운 편이다. 하지만 속도를 최적화하는 과정에서 오래 걸린 문제였다.

조건을 생각해 보면, 2명까지만 탑승이 가능하고, 가능한 한 적은 숫자의 보트를 보내는 것이 목표이다. 따라서 무게를 최대한 한계에 맞춰서 태워 보내는 것이 중요하다.

그래서 해당 조건을 만족하기 위해 필연적으로 탐색을 진행해야 한다. 하지만 이 탐색 과정에서, 연산을 최소한으로 사용하는 것이 목표이다.

필자는 다음과 같은 방식으로 그리디 알고리즘을 적용했다.

1. 사람을 무게 오름차순으로 배열한다.
2. 사람 배열을 순환하면서 자기 자신과 바로 앞 위치의 값을 더하면 한계보다 클 경우, 바로 멈춘다.
3. 그게 아닐 경우, rightidx라는 값을 이용한다. 이를 통해 뒤쪽 가장 큰 값부터 차례대로 자기 자신의 값과 더해서 한계보다 크지 않을 경우, 뒤쪽의 값을 리스트에서 빼내고, 이후의 반복은 빼낸 값 바로 앞의 값부터 다시 앞쪽으로 쭉 반복한다.

3번과 같이 반복하는 이유는, 소팅을 진행했기 때문에 맨 앞에는 가장 작은 값, 맨 뒤에는 가장 큰 값이 배치되게 된다. 첫번째 순환을 생각해 보자, 이때 맨 앞의 값과 맨 뒤의 값부터 차례로 앞쪽으로 가면서 비교하게 되는데, 두개의 합이 한계보다 큰 경우 그 다음 값으로 넘어가는 식으로 순환이 진행된다. 그러다 합이 한계값보다 크지 않을 경우, 해당 값을 빼낸 뒤 그 다음 순환에서는 앞쪽은 두번째 값, 뒤쪽은 빼낸 값의 바로 앞쪽 값부터 음의 방향으로 비교한다. 왜냐하면 첫번째 값보다 두번째 값이 무조건 크거나 같기 때문에, 빼낸 값보다 양의 방향에 있는 값은 굳이 비교할 필요도 없이 한계값보다 커지기 때문이다. 이러한 방식으로 앞쪽, 뒤쪽으로 포인터를 사용하였고, 이 역시 투포인터를 사용하여 값을 구하는 편이 pop연산을 사용하는 것보다 속도가 빠르지만, pop연산을 사용해서 코드가 간결해졌고, 문제가 해결되었기 때문에 이 방식을 사용하였다.

마지막에 전체에 대한 순환이 끝나면 전체 리스트의 길이를 구하는 것으로 답안을 구해주면 된다.

코드

def solution(people, limit):
    people.sort()
    rightidx = len(people)
    
    for i in range(len(people)):
        if people[i] + people[i+1] > limit:
            break
            
        while True:
            rightidx -= 1
            
            if people[i] + people[rightidx] <= limit:
                people.pop(rightidx)
                break
                
    answer = len(people)
    
    return answer

문제

programmers.co.kr/learn/courses/30/lessons/42883

풀이

조건을 간단하게 정리해 보면, 전체 숫자에서 몇 개의 숫자를 빼서 가장 큰 숫자를 만드는 게 관건이다. 그래서 필자는 우선 전체에서 숫자를 빼내는 것보다는, 전체 중 숫자들을 골라내서 가져오는 것이 알고리즘 구상에 더 용이하다고 판단하였다.

그래서 처음에 choose라는 전체 길이에서 k값만큼을 뺀, 선택해야 하는 숫자의 개수를 이용하였고, choose가 0이 되면 빠져나올 수 있도록 알고리즘을 작성하였다.

이후 반복 과정에서의 아이디어는, 뒤쪽 숫자를 모두 선택한다고 가정했을 때, 앞쪽에서 가장 큰 숫자를 고를 때가 가장 큰 값이 된다는 점이다. 이후 앞쪽에서 숫자를 고르면, 그 숫자 이후로 다시 반복을 진행하면 된다. 그러다가 고른 숫자가 앞쪽에서 맨 뒤 숫자일 경우, 그 이후의 숫자들을 모두 선택한다고 판단하면 된다. 또한 시간을 줄이기 위해, 큰 값을 선택할 때 숫자가 9가 나오는 경우에는 그 뒤쪽을 확인할 필요가 없기 때문에 바로 넘어가는 방식으로 시간을 줄여 주었다.

처음에는 pop 연산을 이용하여 프로그램을 진행했는데, pop 연산 자체가 O(n)의 시간 복잡도를 갖기 때문에, 시간 초과가 자주 일어났다. 그래서 이 시간 초과를 해결하기 위해 startidx와 endidx를 통해 투포인터 알고리즘을 적용하였다. 반복을 idx를 이용해 주고, 앞쪽 값들의 시작점과 끝점을 각각 포인팅하여 문자열의 슬라이싱 없이도 순환할 수 있도록 적용하였다.

해당 알고리즘 문제에서는 알고리즘 구상 단계에서 k를 이용해서 단순히 빼내는 것이 아니라 유효한 숫자들을 골라내는 방식으로 반대로 생각하는 것, 시간 관련해서는 pop을 사용하지 않고 투포인터를 사용하여 시간을 줄이는 것, 그리고 9가 나오는 경우 뒤쪽을 확인할 필요 없이 바로 넘어간느 방식으로 시간을 줄이는 것이 주요했다.

코드

def solution(number, k):
    answer = ''
    startidx = 0
    endidx = 0
    choose = len(number) - k
    
    while True:
        idx = -1
        endidx = len(number)-1 - (choose-1)
        
        if endidx < startidx or choose == 0:
            break
            
        elif startidx == endidx:
            answer += number[startidx:]
            break
            
        maxval = -1
        
        for i in number[startidx:endidx+1]:
            if maxval < int(i):
                maxval = int(i)
                
            if maxval == 9:
                break
                
        idx = number[startidx:endidx+1].find(str(maxval))
        answer += str(maxval)
        startidx += idx+1
        choose -= 1
        
    return answer

문제

programmers.co.kr/learn/courses/30/lessons/42860

풀이

속을 많이 썩인 문제였다. 해당 문제도 조건이 다양한 문제로, 문제에 제시되어 있긴 하지만, 조건이 다양하면 그리디를 사용해 보면 좋다는 생각을 갖고, 조건을 정리하면서, 세 가지 경우 중 최솟값을 구하면 된다는 생각이 들었다.

1. 조이스틱으로 오른쪽으로 쭉 가는 경우
2. 조이스틱으로 왼쪽으로 쭉 가는 경우
3. 조이스틱으로 오른쪽으로 가다가 왼쪽으로 가는 경우

해당 3가지 경우를 제외하고는 없기 때문에, 셋 중 최소인 값을 구해주면 좌우로 이동하는 횟수가 계산된다.

그리고, 위아래로 움직여야 하는 경우를 계산해야 하는데, 위아래로 움직이는 경우는 각 문자마다 위로 움직이는 경우, 아래로 움직이는 경우 중 작은 값을 이용하면 된다. 해당 값을 계산하기 위해, 알파벳 문자열을 선언한 뒤, 해당 인덱스까지 가기 위해 위로 눌러야하는 횟수와 아래로 눌러야 하는 횟수를 계산하여 둘 중 작은 값을 더해주었다.

해당 문제는 좌우로 움직이는 경우의 수 중 3번째 경우를 고려하지 않고 풀이를 진행하면서 막혔었는데, 갔다가 다시 오는 경우도 있다는 것을 판단하는 게 조금 어려울 수 있다. 하지만 해당 경우를 파악한다면 금방 풀 수 있는 문제로, 갔다 오는 경우 A가 가장 많은 위치에서 전진하는 방향을 돌려야 하기 때문에, A가 가장 많은 위치를 찾아서 돌려 주었다.

코드

def solution(name):
    answer = 0
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    
    for i in name:
        answer += min(alphabet.index(i), 26-alphabet.index(i))
        
    mov1 = len(name.rstrip("A")) - 1    # 앞으로만 가는경우
    mov2 = len(name.lstrip("A"))        # 뒤로만 가는경우
    
    idx = 0
    n = 1
    while True:
        tmp = name.find("A"*n)
        if tmp == -1:
            break
        idx = tmp
        n += 1                      # A가 가장 많은 곳 위치 찾기
        
    mov3 = 1000000000000
    
    if idx != 0 and idx != len(name.rstrip("A"))-1:
        # A가 가장 많은 곳이 맨앞 또는 맨 뒤쪽인 경우 배제
        mov3 = (idx-1)*2 + len(name) - (idx + n - 1)    
        # A가 가장 많은 곳을 기준으로 갔다가 돌아오는 경우
        
    answer += min(mov1, mov2, mov3)
    
    return answer

문제

programmers.co.kr/learn/courses/30/lessons/42862

풀이

프로그래머스 그리디 문제의 첫번째 문제이다. 간단하게 문제를 소개하면, 학생들 중 체육복을 도난한 학생과 여벌의 체육복을 갖고 있는 학생이 있는데, 바로 앞번호 또는 바로 뒷번호의 학생들에게만 빌려줄 수 있다. 수업을 들을 수 있는 학생의 최댓값을 구하는 문제이다.

조건이 복잡한만큼, 각 조건들을 하나하나 고려해가면서 구현해 주기만 하면, 그리디 알고리즘으로 문제를 해결할 수 있을 것으로 보인다. 따라서 조건들을 정리해 주었다. 이때, 우선적으로 고려되어야 할 조건들부터 차례대로 정리했다.

1. 여벌 체육복을 가져온 학생이 체육복을 도난했을 경우, 본인이 사용해야 하기 때문에 체육복을 빌려줄 수 없다.
2. 앞 번호 또는 뒷 번호 학생에게만 빌려줄 수 있다.

우선 여벌 체육복을 가져왔는데 잃어버린 학생들을 찾기 위해, set을 이용하여 lost와 reserve 배열을 합치고, 해당 set에서 각각 reserve와 lost를 빼서 새로운 lost_new와 reserve_new 리스트를 만든다. 이 과정은 reserve와 lost에 겹치는 학생들의 경우 자기가 사용해야 하기 때문에, 우선 배제해주는 과정이다.

이후 앞 번호 또는 뒷 번호 학생에게만 빌려주는 과정을 거치는데, 단순하게 reserve_new 리스트를 순환하면서 1 작은 값 또는 1 큰 값이 하나라도 있으면 그 값을 lost_new 리스트에서 빼내는 방식으로 알고리즘을 작성하였다.

해당 코드를 리뷰하면서 생각해 보면, 그다지 괜찮은 코드는 아닌 것 같다. 문제에서는 n이 30 이하라고 주어져서 시간 문제는 없긴 했지만, 만약 N이 커진다면 n^2만큼의 시간 복잡도에 pop의 n만큼의 시간 복잡도까지 합쳐져 n^3의 시간 복잡도가 나타나게 된다.

아이디어만 안다면 금방 풀 수 있는 문제였지만, 나중에는 시간 복잡도까지 고려해가면서 문제를 풀 필요가 있어 보인다.

코드

def solution(n, lost, reserve):
    answer = 0
    lost.sort()
    reserve.sort()
    
    lost_reserve_set = set(lost + reserve)
    lost_new = list(lost_reserve_set - set(reserve))
    reserve_new = list(lost_reserve_set - set(lost))
    
    for i in reserve_new:
        j = 0
        while j < len(lost_new):
            if i-1 == lost_new[j] or i+1 == lost_new[j]:
                lost_new.pop(j)
                break
            j = j+1
            
    answer = n - len(lost_new)
    
    return answer

문제

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))