Classic_Blue_Note

문제

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.boannews.com/media/view.asp?idx=95646

2021년 2월 현대자동차와 기아자동차의 미국 및 아랍에미리트 법인 기업정보로 추정되는 자료들이 다크웹에 공개되는 사건이 있었다. 해커조직들이 이렇게 노출한 자료들은 매우 중요한 기업정보로, 회사들은 정보 유출 사실을 감추려 하였으나, 가격협상 불발 등의 이유로 인해 정보를 공유한다며 자료를 올렸다. 해커조직들은 SQL 인젝션 공격으로 해킹했다고 알렸으며, 해당 자료의 일부를 트위터에 공개하기도 하였다.

이렇듯 해커조직들은 기업을 공격한 뒤 얻은 정보를 이용하여 금전적 이득을 보고자 한다. 그러나 일부 기업들은 협상에 응하지 않고, 결국 해커조직에서 해킹으로 유출한 정보를 다크웹에 공개하는 상황이 발생하게 된다.

기본적으로 해커조직과의 협상에는 응하지 않는 것이 원칙이지만, 주요 내부 정보가 유출될 시 입는 피해도 막대하고 한번 노출된 정보는 수습할 수 없기 때문에 기업들의 고민이 많아지게 된다.

기사에서는 발빠른 대처를 통해 추가적인 피해를 막아야 하고, 애초에 보안사고가 발생하지 않도록 보안을 강화하는 한편, 기업의 보안문화가 정착되어야 한다고 하고 있다. 특히 해외 법인과 협력업체 등을 통해 본사 자료가 유출되는 경우도 많기 때문에, 해외법인이나 협력사에 대한 보안 관리와 보안 교육이 강화되어야 한다는 말도 언급하고 있다.

만약 해당 정보들이 기업의 핵심 정보였으면 어땠을까? 기업은 울며 겨자먹기로 해킹범과 협상을 해야 했을 것이고, 결국 과거 인터넷나야나 랜섬웨어 감염 사태와 같이 해킹범에게 어마어마한 금전적 이득을 가져다 주었을 것이다. 오히려 기업 입장에서는 공격당한 정보가 어떤 정보인지 파악하고, 해킹범들이 제시한 금액만큼의 효용이 없다고 판단했을지도 모른다.

이러한 관점에서 보았을 때, 보안은 결국 경영의 핵심이 되어야 하고, 리스크 관리 측면에서 봐야 한다. 완벽하다고 생각하더라도 허점이 있을 수밖에 없고, 그러한 허점들 중 기업에 큰 리스크가 될 수 있는 문제점들은 빠르게 파악해서 고쳐나가야 한다. 이를 통해 리스크를 해소하고, 추후 발생할 수 있는 금전적인 문제들을 사전에 예방하여 결국 ROI를 극대화하는 것이 중요한 것이다. 그것이 기업이 해야 할 목표이긴 하다. 결국 100% 보안이란 불가능하고, 위험을 감수할 수 있는 범위까지 최소화하고 이익을 극대화하는 것이 최고의 보안 전략이다.

하지만 기사에서도 볼 수 있듯이 아직은 주로 형식적인 보안, 법으로 강제된 보안을 통해 이루어지는 경향이 크다고 언급하고 있다. 이처럼 보안을 일종의 규제로만 생각하고, 수익을 창출하는 컨텐츠가 아니라고 생각하기 때문에 보안에 대한 관심이 미비할 수 밖에 없다. 하지만 소를 잃고 외양간을 고치는 것은 결국 소가 사라진 후일 뿐이다. 외부에서 소를 탐내는 도둑들이 많다고 판단되면, 그 소를 지키기 위해 외양간에 투자해야 하는 것이다.

소를 잃어버리면 다시 사면 되지 않느냐, 겨우 소를 위해 외양간에 이만큼 투자해야 하느냐 라는 의문이 있을 수도 있다. 하지만, 디지털 공간으로 돌아와 보면 "겨우 소 한마리" 가 아니다. 오늘날은 데이터 경제 사회에서 살고 있다. 데이터의 양은 점점 더 방대해지고 있고, 데이터의 양이 결국 경제적 가치가 되는 것이다. 소로 비유하자면, 외양간 안에 소가 계속해서 추가되고 있는 상황인 것이다. 이런 상황에서 외양간이 부서지고, 소를 도둑맞는다면 당연히 손해가 막심할 것이고, 이러한 손해를 다시 보지 않기 위해 외양간을 고칠 것이다.

이럴 거면 미리 외양간을 고쳐 놓자는 것이다. 내 외양간은 안 부서지겠지, 그런 안일함 때문에 수많은 기업들이 손해를 본 뒤 유출 지점을 확인하고 있다. 사전에 대비하고, 위험에 대비한다면 그 손해를 없던 것으로 만들거나, 최소화할 수 있을 것이다.

문제

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)