방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 N이 1,000,000 이므로 일반적인 이중 for문으로는 해결할 수 없습니다. 그렇다면 한번 뒤집어보면 어떨까요?

각각의 테스트 케이스를 뒤집으면 다음과 같습니다.

6 7 10 -> 증가하는 경우는 따지지 않음

9 5 3 -> (9-5) + (9-3) = 10

2 1 3 1 1 -> (2-1) + (3-1) + (3-1) = 5

즉 뒤집으면 보다 쉽게 해결할 수 있음을 알 수 있습니다. 

뒤집어진 배열을 조회하면서 다음날의 주가가 더 낮다면 현재까지 있는 주가 중 최대 주가 - 다음날 주가를 더하면 쉽게 해결할 수 있습니다.

소스코드

T = int(input())
for t in range(T):
  n = int(input())
  arr = list(map(int, input().split()))
  revArr = arr[::-1]
  cost = revArr[0]
  ans = 0
  for i in range(1, len(revArr)):
    if cost < revArr[i]:
      cost = revArr[i]
    else:
      ans += (cost - revArr[i])
  print(ans)

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

문제 해결을 위한 과정

이 문제의 경우 입력받은 문자열을 조합해서 팰린드롬을 만드는 문제입니다. 과정은 다음과 같습니다.

1. 입력받은 문자열의 짝수, 홀수 개수를 파악한다.(각 알파벳의 등장 횟수)

2. 전부 짝수로 이루어져 있거나 홀수의 개수가 하나라면 팰린드롬이다. (Ex. ABBA, ABBCBBA)

3. 홀수의 개수가 2개 이상이면 팰린드롬이 불가능하다. (Ex. ABBBC) 

또한 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다 라는 조건이 있는데 이 경우는 알파벳 리스트를 A부터 Z순으로 조회하며 팰린드롬을 생성한다면 자동적으로 사전순으로 배열됩니다.

소스코드

word = input()
arr = [0] * 26
for i in range(len(word)):
  arr[ord(word[i]) - ord('A')] += 1

flag = True
numOfOdd = 0
temp = ""
rest = ""
for i in range(len(arr)):
  if arr[i] % 2 != 0:
    numOfOdd += 1
    rest = chr(i + 65)
    for _ in range(arr[i]//2):
      temp += chr(i + 65) 
  elif arr[i] % 2 == 0:
    for _ in range(arr[i]//2):
      temp += chr(i + 65) 
temp += rest
if numOfOdd >= 2:
  flag = False
  
if flag == False:
  print("I'm Sorry Hansoo")
else:
  if numOfOdd == 0:
    for i in range(len(temp)-1, -1, -1):
      temp += temp[i]
  else:
    for i in range(len(temp)-2, -1, -1):
      temp += temp[i]
  print(temp)

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

문제 해결을 위한 과정

이 문제의 경우 N 이 200,000 이므로 이중 for문으로는 해결하지 못한다는 것을 알 수 있습니다. 40,000,000,000 이므로.

따라서 종료시점 중 가작 작은 값을 꺼내려면 최소힙을 사용해야 함을 알 수 있습니다. 만약 sort를 사용해서 매번 오름차순으로 한다면 

N * NlogN이므로 2 * 10^13 정도로 이 역시 시간초과가 난다는 것을 알 수 있습니다.

소스코드

import heapq

n = int(input())
arr = []
q = []
ans = 0
for _ in range(n):
  a, b = map(int, input().split())
  arr.append((a, b))

arr.sort(key = lambda x: (x[0], [1]))
heapq.heappush(q, arr[0][1])
ans += 1

for i in range(1, n):
  a, b = arr[i]
  if q[0] > a:
    heapq.heappush(q, b)
    ans += 1
  else:
    heapq.heappop(q)
    heapq.heappush(q, b)
print(ans)

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

문제 해결을 위한 과정

이 문제의 경우 순열을 이용하면 쉽게 해결할 수 있습니다. 최대가 10^9 이므로 9자리 숫자를 순열로 배치하는 수입니다.

9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362880 이므로 시간이 충분합니다. 

첫 번째 숫자가 0인 것을 제외해야 하므로 문자열로 바꾸면 쉽게 해결할 수 있습니다.

소스코드

from itertools import permutations
a, b = input().split()
ans = -1
arr = []
for i in range(len(a)):
  arr.append(a[i])

for p in permutations(a, len(a)):
  str = ""
  for i in range(len(list(p))):
    str += p[i]
  if str[0] == "0":
    continue
  else:
    temp = int(str)
    if temp < int(b):
      ans = max(ans, temp)
print(ans)

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

문제 해결을 위한 과정

이 문제의 경우 수학적 지식이 조금은 필요한 문제였습니다. 이항 계수 5 2는 5C2로 표현할 수 있고 이는 5 * 4 / 2 *1로 나타낼 수 있습니다. 추가적으로 이 문제의 경우 overflow를 방지하기 위해 10007 mod연산을 합니다. 따라서 이를 유의하며 해결하면 쉽게 해결할 수 있습니다.

소스코드

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

a, b = 1, 1

for i in range(k):
  a *= n
  a % 10007
  n -= 1

temp = k
for i in range(temp, 0, -1):
  b *= k
  b % 10007
  k -= 1
  
print((a // b) % 10007)

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

문제 해결을 위한 과정

이 문제의 경우 N의 범위가 30,000 이므로 투 포인터를 이용해서 풀어야 합니다. 초기 조건을 설정해 주고 해당하는 count배열에서 확인하면서 숫자가 있는지 없는지 확인하며 temp의 수를 구한 뒤 max(ans, temp)를 이용해서 풀어줍니다. 또한 회전 초밥 이므로 입력받은 배열을 2배로 늘려서 손쉽게 회전 초밥을 구현할 수 있습니다.

소스코드

n, d, k, c = map(int, input().split())
arr = []
ans = 0
count = [0] * 3001

for _ in range(n):
  arr.append(int(input()))

for i in range(n):
  arr.append(arr[i])

# 초기조건
for i in range(k):
  count[arr[i]] += 1
count[c] += 1
for i in range(3001):
  if count[i] != 0:
    ans += 1
count[c] -= 1

for i in range(k, n+k):
  count[arr[i-k]] -= 1
  count[arr[i]] += 1
  count[c] += 1
  temp = 0
  for j in range(3001):
    if count[j] != 0:
      temp += 1
  ans = max(ans, temp)
  count[c] -= 1
  
print(ans)

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

문제 해결을 위한 과정

이 문제의 경우 N이 100,000 이하기 때문에 이중 for문으로 풀면 시간초과가 나는 문제입니다. 따라서 투 포인터를 이용해서 풀어야 합니다. 즉 시작점과 끝 점을 각각 포인트로 잡고 하나씩 이동하면서 해결해야 합니다. 초기조건으로 K개만큼을 더한 후 단일 For문으로 조회하면서 해결합니다.

소스코드

n, k = map(int, input().split())
arr = list(map(int, input().split()))
answer = []

temp = 0
for i in range(k):
  temp += arr[i]
answer.append(temp)

for i in range(k, n):
  temp += arr[i]
  temp -= arr[i-k]
  answer.append(temp)

print(max(answer))

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

문제 해결을 위한 과정

이 문제의 경우 일반적인 이중 for문을 사용하여 문제를 해결하면 최악의 경우 N^2으로 20,000 * 20,000 즉 4억 번 연산을 해야 하므로 시간초과를 받게 됩니다. 따라서 두 배열을 내림차순 정렬한 뒤 A배열의 값, B배열을 비교하면 됩니다. 이렇게 하게 되면 매번 비교할 필요 없이 A 배열값 보다 항상 작은 B배열의 개수를 구할 수 있습니다.

소스코드

T = int(input())
for t in range(T):
  n, m = map(int, input().split())
  arr1 = list(map(int, input().split()))
  arr2 = list(map(int, input().split()))
  arr1.sort(reverse = True)
  arr2.sort(reverse = True)
  idx = 0
  ans = 0
  for i in range(len(arr1)):
    while idx < len(arr2):
      if arr1[i] > arr2[idx]:
        ans += len(arr2) - idx
        break
      else:
        idx += 1
  print(ans)