알고리즘 문제 풀기 - 3

문제 번호	문제 힌트	문제 제목	링크
10869	사칙연산	사칙연산	https://www.acmicpc.net/problem/10869
2588	사칙연산	곱셈	https://www.acmicpc.net/problem/2588
2884	if 문	알람 시계	https://www.acmicpc.net/problem/2884
1110	while 문	더하기 사이클	https://www.acmicpc.net/problem/1110
4344	1차원 배열	평균은 넘겠지	https://www.acmicpc.net/problem/4344
4673	함수	셀프 넘버	https://www.acmicpc.net/problem/4673
1157	문자열	단어 공부	https://www.acmicpc.net/problem/1157
2941	문자열	크로아티아 알파벳	https://www.acmicpc.net/problem/2941
2869	기본수학 1	달팽이는 올라가고 싶다	https://www.acmicpc.net/problem/2869
1929	기본수학 2	소수 구하기	https://www.acmicpc.net/problem/1929
11729	재귀	하노이 탑 이동 순서	https://www.acmicpc.net/problem/11729
11651	정렬	좌표 정렬하기	https://www.acmicpc.net/problem/11651
2805	이분탐색	나무 자르기	https://www.acmicpc.net/problem/2805
4949	스택	균형잡힌 세상	https://www.acmicpc.net/problem/4949
1874	스택	스택 수열	https://www.acmicpc.net/problem/1874
1021	큐	회전하는 큐	https://www.acmicpc.net/problem/1021
2606	DFS와 BFS	바이러스	https://www.acmicpc.net/problem/2606
7576	DFS와 BFS	토마토	https://www.acmicpc.net/problem/7576
1003	동적계획법	피보나치 함수	https://www.acmicpc.net/problem/1003
11053	동적계획법	가장 긴 증가하는 부분 수열	https://www.acmicpc.net/problem/11053

 

1. 크로아티아 알파뱃

이 문제는 결과적으로 엄청 짧은 코드로 해결했지만, 어떻게 접근해야 할지 몰라서 꽤 오랜 시간을 잡아먹었다.

처음에는 그냥 1글자씩 반복을 돌려서 1,2 글자를 비교해서 배열에서 찾으면 되겠다 싶어서 코드를 짯다.

 

<실패코드>

croatia = ["c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="]

text = input()
count = 0

while(True):
    if (len(text) == 0):
        break
    if (len(text) > 1):
        word = text[0] + text[1]
    else:
        word = text[0]
    if word in croatia:
        count += 1
        text = text.replace(word, "", 1)
    else:
        count += 1
        text = text.replace(text[0], "", 1)

print(count)

그러나 이렇게 짜고 보니 3글자에 대한 처리는 전혀 안되어 있어서 3글자까지 고려하면 코드가 괜히 골때려지겠다 싶어서 코드를 한번 엎었다.

이게 막히자 도저히 생각이 안나서 어떻게 해야할지 10분넘게 고민해봤는데, 코드를 두 번정도 틀린 뒤 답을 맞추는데 성공했다.

 

<정답코드>

croatia = ["dz=", "c=", "c-", "d-", "lj", "nj", "s=", "z="]

text = input()

for x in croatia:
    if x in text:
        text = text.replace(x, "?")

count = len(text)

print(count)

 

풀고 나니 너무 짧게 풀리는 코드였다...

 

2. 달팽이는 올라가고 싶다.

이 문제는 접근이 아주 쉬웠다.

그래서 엄청 쉬운줄 알았는데, 실행 시간이 0.25초로 러닝타임을 신경 써야 하는 문제였다.

 

<틀린 코드>

#a,b,v = map(int, input().split())
# a = 낮에 올라가는 높이
# b = 밤에 미끄러지는 높이
# v = 올라갈 높이


a = 100
b = 99
v = 100000

meter = 0
count = 0

while(True):
    count += 1
    meter += a
    if (meter >= v):
        break
    meter -= b

print(count)

 

그래서 시간을 어떻게 단축시킬까 고민이 필요했다.

이 연산을 줄이기 위해 나눗셈과 나머지를 활용해보자고 생각했다.

 

<정답코드>

a,b,v = map(int, input().split())
# a = 낮에 올라가는 높이
# b = 밤에 미끄러지는 높이
# v = 올라갈 높이

meter = 0
count = 0
after_v = v - a

count = after_v / (a-b)
rest = (after_v % (a-b)) + a

while(True):
    count += 1
    meter += a
    if (meter >= rest):
        break
    meter -= b

print(int(count))

 

위와 같이 코드를 짜서 정답을 맞추긴 했는데 영 찜찜해서 더 짧게 할 방법이 있을까 생각해보았다.

 

<정답코드2>

import math

a,b,v = map(int, input().split())
# a = 낮에 올라가는 높이
# b = 밤에 미끄러지는 높이
# v = 올라갈 높이

print(math.ceil((v-b) / (a-b)))

 

단순히 완전히 내가 푼 것은 아니고, 인터넷 검색을 통해 좀 알아보았다. (백준에서도 정답자 코드를 볼 수 있지만, 이유는 안 써있어서 해설까지 포함된 설명을 보았다)

https://yoonsang-it.tistory.com/9

백준 2869번 파이썬 풀이: 달팽이는 올라가고 싶다

 

이렇게 간단한 문제를 저렇게 복잡하게 짯었다니 ㅠㅠ...

알고리즘 오늘부터 조금씩 공부해서 올리려고 했는데 귀찮아서 못하고 있다.

문제를 일단 다 풀어보고 막히는 시점에서 공부해도 되지 않을까..?

어차피 항해2주차에도 공부해야 하고 말이다.

 

그리고 위 블로그 글을 보면서 sys.stdin.readline()을 왜 쓰나 해서 좀 알아보았는데,

파이썬으로 알고리즘 문제를 풀 때에는 input()이 아닌 sys.stdin.readline()으로 하는게 좋다고 한다.

아래글 참고!

https://velog.io/@yeseolee/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%85%EB%A0%A5-%EC%A0%95%EB%A6%ACsys.stdin.readline

[Python 문법] 파이썬 입력 받기(sys.stdin.readline)