[백준/Python] 11501. 주식 & 1254. 팰린드롬 만들기

 

1. 백준 11501. 주식  

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

11501번: 주식

문제

홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.

예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.

입력

입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 날 별 주가는 10,000이하다.

출력

각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다.

 

import sys

input = sys.stdin.readline

T = int(input())
for _ in range(T):

    n = int(input())
    nums = list(map(int, input().split()))

    max_n = 0
    profit = 0

    for each in nums[::-1]:
        if each > max_n:
            max_n = each
        else:
            profit += (max_n - each)

    print(profit)

• 이 문제는 도대체 왜! 거꾸로 푸는 걸까에 대한 답을 이해하기까지 시간이 오래 걸렸다.
• 사실 이해에 그렇게 어려운 것도 아니었는데, 내 풀이에 몰입해있다보니 더 지친 것 같기도 하다. ㅎㅎ..ㅎㅎ..
• 나는 처음에 max(nums)를 구해서 앞에서 부터 비교해가며 이익을 구하는 방식으로 구현했다. 그러나 max(nums) 자체가 가지는 시간 복잡도가 현재 문제에서 주어지는 메모리를 고려했을 때 시간초과로 이어졌다.
• 결국 해답은 끝에서부터 max_n이라는 변수로 제일 큰 값을 업데이트 해주면서 풀이 해나가는 것이었다. max_n 보다 작은 값은 뒤의 max_n일 때 팔면 되므로 매수해도 되는 가격이 된다.

 

---

 

2. 백준 1254. 팰린드롬 만들기   

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

1254번: 팰린드롬 만들기

문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.

동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.

출력

첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다.

 

import sys

input = sys.stdin.readline

words = list(input().rstrip())
words_rv = words.copy()
words_rv.reverse()

for i in range(1, len(words) + 1):
    # 문자 자체가 팰린드롬인 경우
    if words == words[::-1]:
        new_w = words
        break
    # 그 외
    new_w = words + words_rv[-i:]
    if new_w == new_w[::-1]:
        break

print(len(new_w))

• 동호야 왜... 팰린드롬을 만들어줬니?
• 그동안 팰린드롬 문제 그래도 꽤 풀어봐서 껌이겠지 ㅋ 하고 덤볐다가 매우매우매우 고생했다.
• 이 문제 해결을 위해 고민도 해보고 요리조리 코드도 왕 길게 작성했는데, 도움을 받아 해결한 코드는 살짝 간결했다.
• 위의 코드로 문제 해결이 가능한 이유는 주어지는 문자열의 길이가 많이 길지는 않기 때문이다.
• 현재 내 코드에서는 아이템을 하나씩 추가하며 비교를 하고 있기 때문에 문자열이 매우 길면 시간초과 우려가 있다. 그러나 여기서는 문자열의 길이를 50자로 제한하고 있어서 해당 풀이가 가능하지 싶다.
• 또 하나의 마지막 헛발질은 파일 input을 받을 때 문자열은 꼭 .rstrip()을 해야한다는 점.... 간과하고 있다가 놓쳐버렸다. 주의 또 주의하자.
• 마지막으로 실패의 기록을 남기며......... 지금 시각 오전 2시 반 얼른 자러가야겠닭