꾸준히 개발하기

문제를 읽어보면 '()' 괄호 쌍은 무조건 레이저다. 각 쇠막대기의 끝은 '(' 와 ')'로 나타내며, 쇠막대기 끼리는 겹칠 수 있으나 레이저와 각 쇠막대기의 끝은 겹치지 않는다.

처음에는 각 쇠막대기별로 몇개의 레이저를 지나가는지 체크해주는 방향으로 접근했다.

• '(' 하나만 등장하는 경우 stick 배열에 0을 넣는다.
• '(', ')'이 연속해서 등장하는 경우 stick 배열 안의 요소를 +1 해주기.
• ')'이 등장하는 경우 stick 배열에서 pop() 해준다. 

첫번째 시도 코드는 다음과 같다. 사실 작성하면서 stick 배열을 계속 반복하는데 시간초과나는 거 아니야? 싶었다.

import sys

input = sys.stdin.readline

data = input().replace("\n", "")

stick = []
razor = []

answer = 0
i = 0
while i < len(data):
    if data[i] == "(":
        if i != len(data) - 1 and data[i + 1] != ")":
            stick.append(0)
        elif i != len(data) - 1 and data[i + 1] == ")":
            stick = [i + 1 for i in stick]  # 레이저 수 count
            i += 2
            continue
    else:
        answer += stick.pop() + 1  # 레이저 수 + 1 = 조막 수
    i += 1

print(answer)

슬픈 예감은 틀리지 않지... 한 67%에서 시간초과가 났다. 

그래서 접근 방향을 바꿨다. for 반복문을 쓰지 않는 식으로 해주려면 이제 레이저의 관점에서 접근하면 될 것 같았다. 각각의 레이저가 그 순간 몇개의 쇠막대기를 지나가는지 세어주어도 똑같이 풀릴 것 같았다.

• '(' 하나만 등장하는 경우 현재 유효한 cutting_stick 값을 +1 해준다.
• '(', ')'이 연속해서 등장하는 경우 razor 배열 안에 cutting_stick을 append() 해주었다. 즉 razor[0]의 값은 0번째 레이저가 몇개의 쇠막대기를 지나가는지 저장하고 있다.
• ')'이 등장하는 경우 stick 배열에서 pop() 해준다.

최종 답안은 razor 배열 요소의 합과 총 stick의 개수를 더한 값이다. 따라서 쇠막대기가 등장할 때마다 total_stick이라는 이름의 변수로 매번 카운트해줬다.

최종 코드는 다음과 같다.

import sys

input = sys.stdin.readline

data = input().replace("\n", "")

cutting_stick = 0
total_stick = 0
razor = []

i = 0
while i < len(data):
    if data[i] == "(":
        # 쇠막대기 등장
        if i != len(data) - 1 and data[i + 1] != ")":
            cutting_stick += 1
            total_stick += 1
        # 레이저 등장
        elif i != len(data) - 1 and data[i + 1] == ")":
            razor.append(cutting_stick) # 몇개의 막대기를 지나가는지 count
            i += 2
            continue
    # 쇠막대기 끝
    else:
        cutting_stick -= 1
    i += 1

print(sum(razor) + total_stick)

모든 문제가 이렇게 아이디어가 바로 잡혔으면 좋겠다. 매일 정진하자!

문제에서 시키는대로 단순 구현만 하면 되는 문제다. 문제 이해를 잘못해서 2시간이나 걸렸다... 끙 아이디어는 맞게 잡은 것 같은데 자꾸 코드가 불필요하게 지저분해져서 잠깐 방향이 맞나 타 코드를 참고했고 너무 꼬아서 생각했다는 걸 깨달았다. 문제를 너무 어렵게 보지 말고, 매번 조건을 달아서 처리해줘야 하는 경우에는 필시... 내가 생각못한 테케에서 걸리는 경우가 많다. 범용적이게 코드를 짜자.

스택에 넣을 수 있는 숫자는 오름차순만 가능하다. 즉 내가 지금까지 넣은 숫자의 개수를 갖고 있으면 내가 새로운 숫자를 어디부터 시작해야 되는지 알 수 있다.

내가 넣은 숫자의 개수보다 출력해야 하는 숫자가 크면 더 넣어준다. 다 넣어준 뒤, pop()을 하여 해당 숫자가 출력해야하는 숫자인지 체크한다. 만약 pop() 했을 때 해당 숫자가 출력해야 하는 숫자와 다르다면 스택 수열을 만들 수 없는 상황이므로 바로 반복문을 종료하면 된다. 나는 push/pop 연산을 담은 answer 배열을 초기화해주고 끝냈다.

코드는 다음과 같다. (깃헙에는 삽질했던 버전을 함께 올려두었다... )

import sys

input = sys.stdin.readline

N = int(input())
DATA = [int(input()) for _ in range(N)]

count = 0
answer = []
nums = []
for num in DATA:
    while count < num:
        answer.append("+")
        count += 1
        nums.append(count)
    top = nums.pop()
    if top == num:
        answer.append("-")
    else:
        answer.clear()
        break

if len(answer) == 0:
    print("NO")
else:
    for i in answer:
        print(i)

어려운 문제가 아니어도 말리기 시작하면 진짜 끝도 없이 말리는 것 같다. 문제를 풀다가 딱 생각을 환기하고 새로운 마음으로 풀 수 있게 노력해야지.

https://www.acmicpc.net/problem/1406

처음에 보고 단순 구현 문제라고 생각했다. 물론 그렇게 단순하게 생각해서 문자열 슬라이싱했다가 처참하게 시간초과가 났다. 당연하긴 하다. B나 P 입력이 들어오면 문자열 cursor번째까지 살펴보고, 또 그 뒤도 살펴보는 식으로 문자열의 길이만큼을 계속 살펴보게 되어 시간효율성이 떨어진다. 

따라서 커서가 움직일 때마다 해당 데이터를 뽑아서 갖고 있는 리스트(pop_data)를 추가하는 방향으로 코드를 수정했다. 커서를 기준으로 왼쪽 데이터가 data 리스트에, 오른쪽 데이터가 pop_data에 저장되는 식이다! 그러면 매번 O(1)의 시간복잡도만 발생하여 최대 명령어의 개수(M)까지만 시간이 소요되어 0.3초라는 시간제한을 통과할 수 있다.

• L : 커서 왼쪽 이동. data의 길이가 0이 아닐 때, data.pop() -> pop_data에 append()
• D : 커서 오른쪽 이동. pop_data의 길이가 0이 아닐 때, pop_data.pop() -> data에 append()
• B : 커서 기준 왼쪽의 글자 제거. data의 길이가 0이 아닐 때, data.pop()
• P $ : 커서 기준 왼쪽에 글자 삽입. data에 바로 글자 append()

리스트를 커서를 기준으로 2개 둔다는 아이디어만 떠올리면 금방 구현할 수 있는 문제다. 마지막에 출력해줄 때는 data안의 요소와 pop_data안의 요소는 역순으로 출력해주면 된다. (리스트의 역순 접근은 [::-1] 이다. 잊지말자!)

코드는 다음과 같다.

import sys

input = sys.stdin.readline

data = list(map(str, input().replace("\n", "")))
m = int(input())
commands = [input() for _ in range(m)]

pop_data = []
for c in commands:
    if c[0] == "L":
        if len(data) != 0:
            pop_data.append(data.pop())
        else:
            continue
    elif c[0] == "D":
        if len(pop_data) != 0:
            data.append(pop_data.pop())
        else:
            continue
    elif c[0] == "B":
        if len(data) != 0:
            data.pop()
        else:
            continue
    elif c[0] == "P":
        input_c = list(c.split(" "))[1][0]
        data.append(input_c)


print("".join(map(str, data)) + "".join(map(str, pop_data[::-1])))

스택을 언제 쓰는게 효율적인지 살짝씩 감을 잡아가는 것 같다. 더 풀어보자!

후위 표기식은 연산자가 피연산자의 뒤에 등장하는 구조다. 앞에서부터 차근차근 보면서 연산자가 등장한 경우 그간의 숫자 중 가장 마지막 2개를 뽑아와 계산하면 되는 문제였다.

문제 이해를 이상하게 해서 1시간 넘게 헤맸다. 방향을 잘못 잡으니까 계속 그 방향으로만 생각이 빙빙 돌아서 결국 2시간정도 지난 뒤에 다른 사람 풀이를 봤더니 슬퍼졌다. 도대체 왜 난 뒤에서부터 계산한거지 ...? 

코드는 다음과 같다.

import sys

input = sys.stdin.readline

n = int(input())
data = input()
data = data.replace("\n", "")
nums = [int(input()) for _ in range(n)]

# nums인덱스 <- ord() - 65

tmp = []

num_list = []
for s in data:
    # 숫자
    if 65 <= ord(s) <= 90:
        num_list.append(nums[ord(s) - ord("A")])
    # 연산자
    else:
        back = num_list.pop()
        front = num_list.pop()
        if s == "+":
            num_list.append(front + back)
        elif s == "-":
            num_list.append(front - back)
        elif s == "*":
            num_list.append(front * back)
        else:
            num_list.append(front / back)


# 소숫점 두번째 자리까지 표기
print("{:.2f}".format(num_list[0]))

다시금 기억하면 좋을 파이썬 문법 기록하기

- ord('문자') : 아스키코드값으로 바꿔준다

- "{:.2f}".format(숫자) : 소숫점 n번째 자리까지 출력

여러 곳에서 두루두루 쓰이는 파이썬의 자료구조에 대해서 정리해보자.

1. 해시

key-value 로 이루어진 데이터를 저장하는 자료구조. 조회가 매우 빠르다!

파이썬에서는 dict() 자료구조로 구현 가능하다.

딕셔너리는 다음과 같은 구조다. { key1: value1, key2:value2, ... }

빈 딕셔너리를 만들 때 {} 기호로 만들어주면 된다.

딕셔너리의 value에 접근하는 방법은 인덱스에 키 값을 적어주면 된다. 새로운 데이터를 추가할 때도 동일하다.

dictionary = {"name":"jibok"}
print(dictionary[name])
dictionary["age"] = 3

딕셔너리의 요소를 삭제할 때는 del 함수를 사용해주면 된다.

del dictionary["age"]

주의할 점은 key는 고유한 값이므로 중복되는 key값이 들어가게 되면 하나를 제외한 나머지 것들은 모두 무시된다. 고유한 key를 조회함으로써 value를 빠르게 가져오는 장점이 사라지는 행위이므로 하지 말자!

또한 key에 들어갈 수 있는 자료구조는 immutable한 요소만 가능하다. 가령 수정이 가능한 리스트는 안되고 수정이 안되는 튜플은 key로 쓸 수 있다. 

딕셔너리에서 제공하는 유용한 함수들은 다음과 같다.

• keys() : 모든 key를 리턴해준다. * dict_keys() 객체 자체를 돌려주는데 for문 등은 사용 가능하다. 만약 리스트로 값을 써야한다면 list(tmpDict.keys()) 로 변환해주자.
• values() : 모든 value를 리턴해준다.
• items() : key-value 쌍을 튜플로 묶은 값을 리턴해준다. 
• clear() : 안의 데이터 모두 지우기 (key, value 모두)
• get(key) : key에 대응되는 value값을 리턴해준다. 인덱스로 접근하는 것과 동일한 기능인데, 차이가 존재한다. 만약 없는 키값으로 접근했을 때 get 함수는 None을 리턴해주고, 인덱스는 에러를 발생시킨다.
• key in _ : 해당 딕셔너리 안에 key가 있는지 True/False값을 리턴해준다.

2. 스택

후입선출(Last In First Out)의 자료구조이다. 파이썬에서 기본적으로 제공해주는 list() 자료구조를 사용하면 된다.

자료구조의 가장 끝에서만 삽입, 삭제가 이루어진다.

• append() : 리스트의 맨 뒤에 삽입
• pop() : 리스트 맨 뒤의 요소를 꺼내어 리턴

* 맨 앞의 요소에 접근해서 빼려는 시도를 하면 O(N)의 시간복잡도를 가진다. 이런 경우 뒤에서 소개하는 deque 자료구조를 써야 시간 효율적이다.

3. 큐

선입선출(First In First Out)의 자료구조이다. 다양하게 구현하나 코딩테스트를 볼 땐 주로 collections 모듈의 deque를 사용하는 편이다.

from collections import deque
queue= deque()

위와 같이 선언하여 사용한다.

4. 덱

맨앞, 맨뒤에서 모두 자료의 삽입,삭제가 이루어질 수 있는 큐이다. collections 모듈의 deque를 사용한다. 하단의 메소드는 모두 O(1)의 시간복잡도를 가진다. 

• append() : 오른쪽 끝에 삽입
• appendleft() : 왼쪽 끝에 삽입
• pop() : 오른쪽 끝 요소를 꺼내어 리턴
• popleft() : 왼쪽 끝 요소를 꺼내어 리턴

from collections import deque

dq= deque()

dq.append(3)
dq.appendleft(2)
dq.pop()
dq.popleft()

5. 힙

최댓값, 최솟값을 빠르게 찾기 위해 고안된 자료구조로 완전 이진트리이다.

자식 노드의 key 값 < 부모 노드의 key 값 : 최대 힙

자식 노드의 key 값 > 부모 노드의 key 값 : 최소 힙

우선순위에 따라 데이터가 정렬되어 있으므로, 가장 우선순위가 높거나/낮은 요소가 루트 노드에 존재한다. heapq 모듈을 사용한다. heapq 모듈은 리스트를 최소 힙처럼 다뤄준다. 따라서 빈 리스트를 선언하여 매번 넘겨줘야 한다.

• heapq.heappush( heap, item ) : heap에 item 삽입
• heapq.heappop( heap ) : heap에서 가장 작은 원소를 꺼내어 리턴

import heapq
hq = []
heapq.heappush(hq, 1)
heapq.heappop(hq)

기본적으로 heapq 모듈은 최소 힙으로 동작한다. 따라서 최대 힙을 구현해줄 때는 item에 '-'를 붙여 간단하게 구현한다.

여기까지 많이 쓰이는 자료구조는 한번 짚고 넘어간다. 문제 딱 보면 무슨 자료구조 써야되는지, 문법은 뭔지 더 이상 헷갈리지는 말자!

https://www.acmicpc.net/problem/2981

맞왜틀을 외치면서 풀이를 참고했다. 틀렸었다^^

일단 수학적으로 규칙을 좀 찾아야 된다. 

4개의 수를 기준으로 일단 생각해보자.

a = M * a` + r

b = M * b` + r

c = M * c` + r

d = M * d` + r

인 경우 r을 없애보면 다음과 같다.

(a-b) = M * (a`-b`)

(c-d) = M * (c`-d`)

즉 입력받는 숫자들의 차이들의 최대공약수를 구해주면 그게 바로 M이다. 

해당 M의 약수를 1 제외하고 모두 출력해주면 문제가 원하는 답이 된다.

자, 여기서^^... 약수도 그냥 출력하면 안된다. 그냥 출력하다보면 최대 입력 가능한 숫자의 범위(1,000,000,000)가 워낙 커서 시간초과가 난다. 따라서 골드바흐 문제 풀때 for문 1개로 다 처리해줬던 것처럼 다 살펴보지 말자!

예를 들어, 10의 약수는 다음과 같다 (1, 2, 5, 10) 그러면 1*10, 2*5 두 쌍으로 연산을 줄일 수 있다. 즉, 제곱근까지만 살펴본 뒤 그 수로 나눈 몫까지 함께 넣어주면 절반까지만 보면 된다!

혹시 모를 중복을 제거해주기 위해 set 자료형으로 한번 변환한 뒤, 오름차순 출력을 위해 list로 바꾼 뒤 sort하여 출력해주었다. 잊지말고 최종 숫자인 M도 출력해주자~!

코드는 다음과 같다.

import math
import sys

input = sys.stdin.readline

n = int(input())

nums = sorted([int(input()) for _ in range(n)])

gaps = []
for i in range(1, len(nums)):
    gaps.append(abs(nums[i] - nums[i - 1]))

answer = math.gcd(*gaps)

answer_list = []
i = 2

# 약수 구하는 while문 (통과)
while i <= (answer ** (1 / 2)) + 1:
    if answer % i == 0:
        answer_list.append(i)
        if i != (answer // i):
            answer_list.append(answer // i)
    i += 1

# 약수 구하는 for문 (시간초과)
# for i in range(2, int(answer ** 1/2)+1):
#     if answer % i == 0:
#         answer_list.append(i)
#         if i != (answer // i):
#             answer_list.append(answer//i)

for i in sorted(list(set(answer_list))):
    print(i, end=" ")

print(answer)

자,,, 저 코드에서 while문 for문의 차이가 뭔지 바로 보이는가..^^ 바로 거듭제곱과 나눗셈 연산자의 우선순위를 고려하지 않고 짰더니 처참하게 틀린 코드다. 나눗셈보다 거듭제곱이 연산자 우선순위가 높다...! 꼭 괄호를 생활화하자!

그리고 여러 줄을 입력받는 경우 속도가 더 빠른 sys 라이브러리를 사용하도록 코드도 바꿔보았다. 이제 input() 바로 쓰지 말고 sys.stdin.readline 기능을 활용하자

한 일주일 있다가 다시 풀어보자 잊지말고..!^^ 제목에다가 박아둬야겠다. 다시 제대로 푼 날 게시물을 수정해야겠다

소수판별 알고리즘과 시간초과의 늪의 반복이었던 문제... 계속 풀었던 골드바흐 파티션 문제 중 아마 시간이 제일 짧게 주어졌던 문제였던 듯 하다. 물론 그거 고려 안하고 무작정 들박했다가 처참한 시간 초과의 늪에 빠졌다.

처음에는 최대 MAX 값만큼 안 돌리고 테스트케이스 내에서 max값까지만 에라토스테네스의 체를 이용하는 것도 고려해봤는데 여전히 시간초과가 나더라. 생각해보면 max값까지 돌리나 백만까지 돌리나 시간은 크게 차이가 없었다. 그러면 이제 따져볼건 골드바흐 파티션을 구하는 과정에서 불필요한 for문이 있다는 거였다. 아무리 생각해도 for문을 2개를 돌려야될 것 같다고 생각하면서 break문 열심히 넣어줘도 계속 시간초과가 났다.

for문을 1개로 줄여야 통과될 것 같은데, 하면서 보다가 답을 찾아냈다.

-> 굳이 for문을 2개 돌릴 필요 없이, 앞에서부터 보는거 + 뒤에서부터 보는거 는 for문 1개로 충분했다!

흐뭇하게 .. 시간초과의 늪에서 벗어났다. 코드는 다음과 같다.

def getPrimes(MAXCASE):
    erato = [True] * (MAXCASE + 1)
    erato[0], erato[1] = False, False

    for i in range(2, int(MAXCASE ** 0.5) + 1):
        if erato[i] == True:
            for j in range(i + i, MAXCASE + 1, i):
                erato[j] = False
    return erato


erato = getPrimes(1000001)
t = int(input())

for _ in range(t):
    num = int(input())
    cnt = 0
    for i in range(2, num // 2 + 1):
        if erato[i] and erato[num - i]:
            cnt += 1
    print(cnt)

굳이 에라토스테네스의 체를 함수로 선언해준 이유는... 입력받은 숫자 중 max값까지만 소수판별을 하려고 했었다 원래는 ^.T 중첩 for문을 줄여야 시간복잡도를 확 줄일 수 있다고 또다시 몸으로 깨달은 문제였다. 

1초 뒤에 D만큼 움직여야 하고 모든 동생에게 닿을 수 있는 D의 최댓값을 구해야 되는 문제다.

즉, n개의 수 <-> 정수 s 차이의 최대공약수를 구해주면 되는 문제다.

편하게 파이썬의 math.gcd() 함수를 사용했다. gcd() 함수를 자세히 보니 다음과 같이 애스터리스트(*)표시가 있었다.

따라서 거리 차이 리스트를 '*' 표시를 붙여서 함수에 넘겨준 뒤 그 값을 출력하면 되는 문제였다. 파이썬 최고 .. 물론 이 방법이 아니면 유클리드 호제법으로 계속 수를 반복적으로 gcd구해주면 되겠다. 이번에는 파이썬 애스터리스트 문법을 배웠다는 거에 의의를 두고 라이브러리르 쓰겠다 ㅎㅎ

코드는 다음과 같다.

import math

n, s = map(int, input().split())

data = list(map(int, input().split()))
gaps = []

for v in data:
    gaps.append(abs(s - v))

print(math.gcd(*gaps))