[COSE403] 2주차 연습 풀이와 설명 모음

5648. [S5] 역원소 정렬

# 5648**

import sys

nums = "".join(list(map(str, sys.stdin.readlines()))).split() # 입력 문제: re.split은 구분자 사이에 아무것도 없을 경우 빈 문자열이 들어감..
reverses = []

for i in range(1, int(nums[0])+1):
    reverses.append(int(nums[i][::-1])) #문자열 뒤집기: str[::-1]
  
for j in sorted(reverses):
    print(j)

# cnt, *nums = sys.stdin.read().split()
# for i in range(int(cnt)):
#     nums[i] = nums[i][::-1]
# nums = list(map(int, nums))
# print(*sorted(nums), sep="\n")

아무 생각 없이 정규표현식 썼다가 낭패를 본 문제...!  re.split("구분자")는 구분자 사이에 아무것도 없을 경우 빈 문자열이 들어가기 때문에, 의도한 것과 다르게 nums에 입력값이 들어갔다. 정규식에 익숙하기는 하지만, 아직 능숙하게 사용하지는 못하기 때문에 더더욱 연습하고 공부해야겠다는 생각이 들었다.

그래도 파이썬에서 문자열을 뒤집으려면 str[::-1]을 사용하면 된다는 사실을 알았다! 그동안 for문을 마구 돌렸는데 이제는 좀더 간편하게 쓸 수 있을 것 같다.

또 아래 코드는 다른 풀이를 검색하다가 알게 된 풀이인데 정말 파이썬 같다는 생각이 들어 주석에 적어놨다...! unpacking을 하기 위해 저런 코드를 작성하신 것 같은데 나도 저런 풀이를 자연스럽게 써내고 싶었다. 파이썬은 파면 팔수록 매력이 넘치는 것 같다...!

(asterisk 관련하여 참고한 블로그)

파이썬 별표(*), Asterisk의 역할

1064. [S4] 평행사변형

# 1064** -> 평행사변형의 성립 조건, 기하학 공식 필요

import math

x1, y1, x2, y2, x3, y3 = map(int, input().split(" "))

AB = math.dist([x1, y1], [x2, y2])
BC = math.dist([x2, y2], [x3, y3])
CA = math.dist([x3, y3], [x1, y1])

if (x3 - x2)*(y2 - y1) == (x2 - x1) * (y3 - y2):
    print('-1.0')
else:
    lengths = [AB + BC, BC + CA, CA + AB]
    print(2 * (max(lengths) - min(lengths)))

[백준] 1064번 평행사변형, 파이썬 문제 풀이

이틀을 봐도 어떻게 풀어야 하는지 전혀 안 떠올라서 다른 풀이를 참고했다.. 기하학을 안 좋아하는데 그걸 탁 찌른 문제 같아서 많이 반성하게 됐다. 

처음에는 문제가 잘 이해되지 않기도 했고, 좌표평면만 너무 생각해서 좌표에 따라서 경우의 수를 확인해야 하나 했는데, 그건 아니었고 평행사변형의 특징상 점 D의 경우의 수는 항상 3개였고, A,B,C 세 개의 점이 한 직선 위에 있는 경우에만 평행사변형을 만들 수 없다는 사실을 그대로 구현해주면 되었다.

또 한 직선인 경우를 체크하기 위해 기울기 연산을 할 때 나눗셈을 해버려서 DivisionByZero 에러를 한 번 마주했다. 나누기를 할 때는 항상 0으로 나눠질 가능성을 염두에 두고 확인해야겠다...!

 

1904. [S3] 01타일

# 1904
# 1 2 3 5 8 -> 피보나치 수열..?

N = int(input())

cnt = [0] * (N+1)
if N == 1:
  cnt[1] = 1
else:
  cnt[1] = 1
  cnt[2] = 2


if N >= 3:
  for i in range(3, N+1):
    cnt[i] = (cnt[i-1] + cnt[i-2]) % 15746
  print(cnt[N])
else:
  print(cnt[N])

처음 읽었을 때는 어떻게 풀어야 하지...? 했는데 예시를 몇 개 나열해보니 피보나치 수열과 동일한 것이 나와서 그냥 그대로 풀었다. DP에 대해 처음 접한 문제지만, 피보나치라는 점이 더 눈에 띄어서 DP는 그닥 눈여겨보지 않고 지나쳤다. (업보 스택...)

 

4949. [S4] 균형잡힌 세상

#4949

import re
import sys

def isBalanced(line):
    stack = "".join(re.findall(r"[()[\]]", line))
    if len(stack) == 0:
        print("yes")
    else:
        while (True):
            latest_stack = stack
            stack = re.sub(r"\(\)|\[\]", "", stack)
            if len(stack) == 0:
                print("yes")
                break
            elif latest_stack == stack:
                print("no")
                break
            else: continue

while (True):
    line = sys.stdin.readline().strip('\n')
    if line == ".": 
        break
    else:
        isBalanced(line)

정규식 배운 이득을 톡톡히 본 문제. 다른 친구들 코드 보니 스택 구현하고 그러던데 난 그냥 변수 이름만 스택이지 정규식으로 풀었다...

 

처음에는 "[]"에 해당하는 부분이 없을 때 re.sub문이 계속 while문 안에서 돌아서 런타임에러가 발생했는데, 이는 직전 문자열과 re.sub 후 문자열을 비교하는 분기를 추가해서 해결하였다.

 

또 입력값을 받을 때 개행 문자를 지우기 위해 아무 생각 없이 sys.stdin.readline().strip()을 쳤는데, 이러면 공백도 제거되어서 의도와 다른 입력값이 나타났다. strip에 '\n'을 추가해주니 해결되었다!

 

14501. [S3] 퇴사

# 14501** - 그리디 아님... DP임

catalog = []

N = int(input())
for i in range(N):
    a, b = map(int, input().split(" "))
    catalog.append([a, b])

revenue = [0] * (N+1)

for i in range(N):
    for j in range(i+catalog[i][0], N+1):
        if revenue[j] < revenue[i] + catalog[i][1]:
            revenue[j] = revenue[i] + catalog[i][1]
    
print(max(revenue))

01타일에서 DP를 확인하지 않고 대강 푼 업보를 여기서 다 맞았다...^^ㅠ 처음에는 그리디로 풀려고 했는데 예제4가 어떤 식으로 해도 값이 이상했다. 다시 확인해보니 예제4는 그리디로 풀었을 때 정답이 나올 수 없는 예시였다... 그래서 머리를 싸매다가 다른 풀이를 참고하였다.

[BOJ/백준] 14501번 퇴사 (Python 파이썬)

DP 방식으로 접근해야 하는 문제로, bottom-up 방식으로 접근하였다. 상담 예약의 이익을 더해가면서, 현재의 이익보다 더 큰 이익을 얻을 수 있을 경우 revenue[j] 값을 갱신하는 방식이다. 즉 하루 걸리는 1일차 상담을 한 후, 2일차 상담을 하는 게 더 이득인지, 하루 쉬고 3일차 상담을 하는 게 더 이득인지를 모두 체크할 수 있게 된다.

 

아래는 내가 풀었던 그리디 방식의 틀린 코드이다. 예제 1~3은 정답 출력값이 나오지만, 예제4는 1, 6, 8번째 상담을 하는 경우가 90으로 가장 이득이 크기 때문에 틀린 출력값이 나온다...!

# 14501 - 그리디로 푼 틀린 코드

catalog = [[0, 0]]

N = int(input())
for i in range(N):
    a, b = map(int, input().split(" "))
    catalog.append([a, b])

revenue = []

for i in range(1, N+1):
    result = 0
    k = i
    while k <= N:
        if k + catalog[k][0] > N:
            break
        else:
            result += catalog[k][1]
            k += catalog[k][0]
    revenue.append(result)
    
print(max(revenue))

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

아래 두 문제는 시간이 없기도 했고 감을 못 잡아서 아직 풀지 못했다. 푸는대로 풀이는 추가하려고 한다...!

4963. [S2] 섬의 개수

 

1080. [S1] 행렬