꾸준히 개발하기

입출력 기본 문제들

(https://plzrun.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4PS-%EC%8B%9C%EC%9E%91%ED%95%98%EA%B8%B0참고)

22.10.7 (금)

백준 : 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992

아래 커리큘럼 시작

https://dev-dain.tistory.com/155

1. 수학

(합공식, 피보나치수, 약수, 최대공약수, 최소공배수, 소수, 조합과 순열)

https://www.acmicpc.net/workbook/view/8997

22.10.7 (금)

22.10.8 (토)

22.10.9 (일)

문제를 이해하면 다음과 같다.

높이가 다른 탑이 일렬로 있고, 모든 탑은 자기 기준 왼쪽으로 레이저를 송신한다. 수신 가능한 탑은 해당 레이저가 발사된 탑보다 높이가 크거나 같아야 하며, 레이저는 가장 먼저 닿은 탑 1개에서만 수신된다.

처음에 한 1시간정도 계속 뒤에서 접근해가면서 봐서 끙끙 앓았다. 앞에서 어느 탑이 수신 가능한지 알 수 없는데 뒤에서부터 본 게 잘못이었다.

자고 일어나서 다음날 다시 앞에서부터 보는 방향으로 생각의 방향을 틀었다. 앞에서부터 차근차근 보면 된다. 수신 가능한 탑을 배열로 저장하고, 최신순으로 꺼내보면 된다. 

1. 첫번째 탑 : 이전 탑이 없으므로 수신 가능한 탑 배열에 (높이, 탑번호) 넣어주기만 하면 된다.
2. 두번째 탑 : 수신 가능한 탑 배열에서 pop() 하여 높이를 비교한다. pop() 한 요소의 데이터는 prev_를 붙여 저장했고 현재 탑의 데이터는 now_를 붙여 저장했다.
   • prev_h > now_h : prev_i번째 탑이 현재 레이저를 수신 가능한 경우.
     pop()한 데이터를 다시 수신가능한 탑에 append해줘야 한다. 현재 탑 데이터도 수신 가능한 탑 배열에 append
   • prev_h == now_h : prev_i번째 탑이 현재 레이저를 수신 가능한 경우.
     높이가 같은 경우 최신 탑이 먼저 수신하게 되므로 현재 탑의 데이터만 수신 가능한 탑 배열에 append
   • prev_h < now_h : prev_i번째 탑이 현재 레이저를 수신 불가능한 경우.
     pop()한 데이터를 저장해줄 필요 없이 넘어간다.
     만약 모든 데이터를 다 훑었음에도 수신 가능한 탑이 없다면 현재 탑의 데이터를 수신 가능한 탑 배열에 append해주고 넘어간다.
3. i번쨰 탑 : 뒤와 동일한 로직이다.

이렇게 풀어주니 별 문제 없이 통과했다!

코드는 다음과 같다.

import sys

input = sys.stdin.readline

N = int(input())
Heights = list(map(int, input().split(" ")))

# 맨 앞 탑은 수신 불가능하므로 미리 저장하고 고려X
answer = [0]
available_tower = [(Heights[0], 1)]  # (높이, 탑번호)

for i in range(1, len(Heights)):
    now_h, now_i = Heights[i], i + 1

    received = False
    while len(available_tower) > 0:
        prev_h, prev_i = available_tower.pop()
        # 수신 가능한 탑 발견
        if prev_h > now_h:
            available_tower.append((prev_h, prev_i))
            answer.append(prev_i)
            available_tower.append((now_h, now_i))
            received = True
            break
        # 수신 가능한 탑 발견
        # 높이가 같은 경우 최신 탑이 더 우선이므로 최신 탑 데이터만 저장
        elif prev_h == now_h:
            answer.append(prev_i)
            available_tower.append((now_h, now_i))
            received = True
            break
        else:
            continue
    # 모든 탑이 다 수신 불가능한 경우
    if received == False:
        available_tower.append((now_h, now_i))
        answer.append(0)

print(" ".join(map(str, answer)))

현재 접근한 방법으로 문제가 안 풀릴때 빠르게 다른 방향으로 생각의 전환을 해보는 것이 중요하다고 어제 깨달았고, 오늘 직접 전환해보니 실제로 문제가 풀려서 매우 좋다. 골드 V 문제도 풀리기 시작하는 걸 보니 늘긴 느나보다.

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

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

• '(' 하나만 등장하는 경우 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번째 자리까지 출력

매우 간단한 문제긴 한데 놓쳤던 부분이 있어서 시간 소요가 꽤 있었다. 기억을 위해 기록한다!

조합 공식은 위 그림과 같다. 조합은 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 없음)

팩토리얼을 구현하는 방법이 여러가지가 있으나 재귀함수 구현에 좀 시간이 걸렸다. 부끄럽다... 일단 재귀함수 ... 후 ... return문이 있어야 함수를 빠져나간다... 재귀 억지로라도 계속 손에 익히자 ㅠㅠ! 재귀로 팩토리얼을 구해도 되고 반복문으로 해도 된다.

그러고 나서 나눗셈을 해줘야 하는데 파이썬에서 '/' 과 '//' 연산자 차이를 이제야 다시 알았다.

'/' : 나눗셈 결과를 float형으로 반환

'//' : 나눗셈 결과를 int형으로 반환

그래서 /로 연산해준뒤 형변환하면 틀렸다고 나온다. 뭐 뒤의 자리를 까고 그러다가 그랬겠지..? 어차피 저 결과는 무조건 정수가 나올 수 밖에 없으니까 int형으로 리턴하는 '//' 연산자를 쓰는게 맞겠다.

코드는 다음과 같다.

n, m = map(int, input().split())
def recur_f(n):
    if n == 1:
        return 1
    else:
        return n * recur_f(n - 1)

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

print(factorial(n) // ((factorial(m) * factorial(n - m))))

소수 판별 알고리즘 중 에라토스테네스의 체 방식을 알고 있어야 시간 초과가 안 나는 문제다. 물론 나는 에라토스테네스의 체 방식을 매번 입력받을 때마다 하고 반복문도 많이 써서 시간초과만 우다다 받았다 ^^ 

시간초과를 막는 중요한 포인트가 2개였다...

1. 에라토스테네스의 체를 범위 내의 모든 숫자에 한해서 1번만 돌리기
2. 최대한 반복문 줄이기

최대 입력 가능한 숫자 범위가 1000000이니까 그 안을 일단 다 소수를 판별해버린다! 가능한 소수를 미리 다 계산한 뒤 또 범위 내에서 새로운 리스트를 만들지 말고, 반복문 안에서 True, False값을 체크해서 보기만 해야 시간 초과가 안 난다.

시간초과가 이렇게 머리를 아프게 하는지 간만에 느껴본 문제...^^ 같은 골드바흐 문제는 꽤 금방 시간초과를 잡아서 기가 살아있었는데 1시간 내내 계속 시간 줄이다 보니까 기가 쪼그라들었다... 그래도 풀긴 푼거니까... 어디서 시간초과가 나는지 잘 살펴보는 능력도 정말 중요하구나, 또 느낀다.

파이썬 코드는 다음과 같다.

erato = [True] * 1000001
erato[0], erato[1] = False, False
for i in range(2, 1001):
    if erato[i]:
        for j in range(i + i, 1000001, i):
            erato[j] = False

while True:
    n = int(input())
    wrongFlag = True
    if n == 0:
        break

    for i in range(3, n):
        if erato[i] == True:
            if erato[n - i] == True:
                wrongFlag = False
                print(n, "=", i, "+", n - i)
                break
    if wrongFlag:
        print("Goldbach's conjecture is wrong.")

눈물의 코드... (쓸 필요도 없었고 시간초과만 유발했던 녀석들이다)

# n 미만의 수 중 홀수인 소수 리스트 리턴
def getPrimeNums(n):
    return [i for i in range(n) if erato[i] == True and i % 2 != 0]


def getGoldB(target, nums):
    middleIdx = -1
    for i in range(len(nums)):
        if nums[i] > int(target / 2):
            break
        middleIdx = i

    for i in range(middleIdx + 1):
        for j in range(len(nums) - 1, middleIdx, -1):
            if nums[i] + nums[j] < target:
                break
            if nums[i] + nums[j] == target:
                return [nums[i], nums[j]]
    return False

나름 시간 좀 줄여보겠다고 다른 골드바흐 문제에서 시간초과 잡아줬던, 중간값 구해서 어찌저찌 해봤는데 역시나 시간초과였다. 그냥 T/F 값 판단해서 바로바로 계산하는게 제일 빠르구만