[CLASS 2]백준 1181번, 1436번, 2609번

1181번 : 단어 정렬

 

문제를 보자마자 든 생각 : sort()

 

내 코드(날먹):

wordsSet = set()
for _ in range(int(input())):
    wordsSet.add(input())
words = list(wordsSet)
words.sort()
words.sort(key=lambda x:len(x))
for word in words:
    print(word)

 

파이썬! 파이썬! 파이썬! 파이썬!

 

이 때를 위해 파이썬을 하는게 아닌가! 아주 간단하다.

 

중복제거 -> set 정렬 -> sort

 

약간 아쉬운 점은 stdin을 사용했다면 속도가 훨씬 빨려졌을 것이다.

 

1436번 : 영화감독 숌

 

666이 포함된 수를 찾아내어 넘버링하는 문제이다. 나는 가장 직관적으로 이렇게 코드를 작성했다.

 

내 코드:

n = int(input())
temp = 666
while True:
    strTemp = str(temp)
    for i in range(len(strTemp)-2):
        if strTemp [i]== '6':
            if strTemp[i+1] == '6':
                if strTemp[i+2] == '6':
                    n -= 1
                    if n == 0:
                        print(temp)
                        exit()
                    break
    
    temp += 1

 

temp를 666에서 시작하여 1씩 증가시키면서, 해당 숫자에 666이 있을 경우 n 을 하나씩 줄인다. n이 0 이 되는 순간 print하고 종료.

 

이 코드는 쉽지만, 느리다. 모든 수에서 모든 자릿수를 다 검사하기 때문이다. 속도를 중요시한다면 이런 방식을 사용해서는 안된다. 어떤 방식을 사용해야 할까?

 

 

seoll77님의 코드:

s = int(input())
nlist = []
n = 0
while len(nlist) <= 10000:
    if not n%10 == 6:
        nlist.append(n*1000+666)

    elif (n//10)%100 == 66:
        for k in range (1000):
            nlist.append(n*1000+k)

    elif (n//10)%10 == 6:
        for j in range (100):
            nlist.append(n*1000+600+j)

    elif n%10 == 6:
        for i in range (10):
            nlist.append(n*1000+660+i)

    n += 1

print (nlist[s-1])

 

이 코드도 직관적이어서 좋은 것 같다. n 이 최대 10000까지만 입력된다는 것을 알고 있기 때문에 10000개의 요소를 만들어서 배열에 집어넣은 뒤 요청하는 n 이 있으면 꺼내주기만 하면 된다. 대신 코드를 수정하지 않는다면 10000 이후의 값을 얻지는 못한다는 단점이 있다

 

2609번 : 최대공약수와 최소공배수

 

간단하게 최대공약수와 최소공배수를 구하는 문제이다.

 

내 코드(날먹):

from math import gcd
n,m = map(int,input().split())
print(gcd(n,m))
print(n * m // gcd(n,m))

이렇게 math 라이브러리에서 gcd함수를 가져온다면 그냥 풀 수 있다. 최소공배수는 그 성질에 의해 n * m / 최대공약수를  하면 된다.

 

이렇게 말고 실제로 구현하고 싶다면 유클리드 호제법을 사용하면 된다.

 

 

유클리드 호제법을 간단하게 직사각형의 길이로 비유하자면, 길이가 x , y 인 직사각형에서, 크지 않은 변의 길이로 정사각형을 만들어 집어넣고, 남은 영역에서 이를 반복해서 처음의 직사각형이 정사각형으로만 모두 채워졌을 때, 가장 작은 크기의 정사각형의 한 변의 길이가 x와 y의 최대공약수가 된다.

 

이를 알고리즘에 적용하면, x와 y를 받아서 y(남은 직사각형의 긴 변)를 x에 대입하고, y에는 x 를 y로 나눈 나머지(남은 직사각형의 짧은 변)를 대입하는 것을 반복하여 y가 0이 될 때 까지 수행하면 된다.

 

내 코드(유클리드 호제법):

def gcd(x,y):
    while y:
        x,y = y, x%y
    return x
n,m = map(int,input().split())
print(gcd(n,m))
print(n * m // gcd(n,m))

 

재귀를 사용할 수도 있겠지만 굳이 재귀를 사용할 필요는 없다.