프로그래머스 코딩테스트 연습문제 카펫을 풀어봤다

카펫

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고 모서리는 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
빨간색 격자의 수 red는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

문제는 완전탐색으로 풀라고 하는 것 같았지만, 이 문제는 수학적으로 풀 수 있을 것 같았다.
Brown과 Red를 이루는 수를 Red의 m과 n으로 표현해보고 (Red = (m x n)꼴, m>n) 나온 (m,n)꼴에 +2를 해주면,
return값이 (m+2,n+2) 나오게 된다는 것을 깨달았다.

하지만 문제가 있었다. 이 경우는 Red가 Square꼴이 아닐 때만 해당했던 것이었다.
Red가 Square꼴일 경우, m과 n으로 문제를 풀 수 없다.

이 경우는 다른 케이스를 생각해 봐야 한다.
R을 (nxn)꼴이면 Brown이 4(n+1)로 나온 다는 것을 알아야 한다.
return은 처음의 케이스와 같이 2만 더해주면 된다.

첫번째 케이스의 경우를 n에 대해서 쭉 풀어주면 이차방정식 꼴이 나온다.
아마도 테스트 케이스는 근이 정수로 나올 것 같아서 중근이나 허근이 나올 경우를 제외한, 근의 공식을 코딩해서 함수화 하였다.

1
2
3
4
5
6
7
8
9
10

def fun(a,b,c):
    D=b*b-4*a*c
    if D>0:
        x1=round((-b-D**0.5)/2*a)
        x2=round((-b+D**0.5)/2*a)

    if x1>x2:
        return [x1+2,x2+2]
    else :
        return [x2+2,x1+2]

그 다음 두번째 케이스로 넘어가는 것이 중요했는데, Brown과 Red를 받았을 때, 특히 Red를 가지고 제곱수인지 판별하는 함수가 필요했다. 만약 Red가 제곱수라면 Red에 루트를 씌워서 값을 받아 2만 더해주면 될 것이고, 제곱수가 아니라면 위의 함수를 이용해서 return을 받으면 된다.
그래서 제곱수 판별하는 함수를 다음과 같이 작성했다.

1
2
3
4

import numpy as np
def issquare(n):
    if int(n ** 0.5) ** 2 == n :
        return int(np.sqrt(n))

마지막으로 solution 함수에서는 이 함수들을 모두 합쳐주고 조건문을 통해서 return값을 다르게 받아준다.

1
2
3
4
5
6
7
8
9

def solution(brown, red):
# return이 제곱 수 아닐 때
    if issquare(red) :
        return [issquare(red) + 2,issquare(red) + 2]
    else:
        a = 1
        b = (4-brown)/2
        c = red
        return fun(a,b,c)

정리 : 코딩 연습을 꾸준히 해야하는 것이 느껴진 문제였다. 제곱수를 판별하는 문제나, 이차방정식의 해를 구하는 문제는 연습문제로 간간히 나오던 것이었다. 기초적인 문제가 제대로 학습이 되어있지 않으면, 문제 푸는데 굉장히 오랜 시간이 걸리지 않을까 생각했다. 기본적인 문제도 중요하다!

프로그래머스 코딩테스트 연습문제 가장 큰 수를 풀어봤다

가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

처음 이 문제를 봤을 때, ‘어 permutation 쓰면 끝이네 개꿀ㅎㅎ’ 이런 생각이 들었다.
바로 itertool을 import 해서

1
2
3
4
5
6
7
8
9
10
11

from itertools import permutations
def solution(numbers):
    str_list = []
    for i in numbers:
        str_list.append(str(i))
    first=list(map(''.join, permutations(str_list)))
    int_list = []
    for li in first:
        int_list.append(int(li))
    answer = sorted(int_list, reverse=True)[0]
    return str(answer)

이런 코드를 작성해서 제출했다.

결과는!!

시간초과가 떠 버렸다. 효율성이 제로라는 말이다.
검색해보니 permutation은 필요하지 않은 부분까지 순열 조합을 만들어 내기 때문에
굉장히 비효율적인 코드라는 것을 알아냈다.

‘그렇다면 순열같이 코드를 짜되 효율적으로 작성해야 한다는 것인가?’ 라는 고찰과 함께
코딩을 시작했고 하루를 날렸다.

당연했다. 문제푸는 방향이 완전히 잘못되었었다. 효율적으로 순열조합 만드는 코드를 짠다면 내가 라이브러리를 새로 만드는 수준인 것이었다.

방향을 다시 생각해봤다.
사실 이 문제를 풀다보면 list에 있는 원소를 편하게 처리하기 위해 str으로 바꿔야 하고 비교하기 위해
int로 다시 바꿔줘야 하는 번거로움이 있다.

그런데 굳이 int–>str 이런식으로 바꿔줄 필요가 없다.

왜냐하면 정수모양의 str도 정수 값이 증가함에 따라 메모리 값도 증가하기 때문이다.

이를 id()를 통해 확인해 볼 수 있다.

1
2
3
4
5

print(id('1'))
print(id('2'))
print(id('3'))
print(id('4'))
print(id('5'))

1
2
3
4
5
6

Out:
4380097928
4380098040
4380111232
4380111288
4379241192

이를 이용해서 문제를 푼다면 다음과 같은 코드를 작성할 수 있다.

1
2
3
4
5

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x : x*3, reverse = True)
    answer = str(int(''.join(numbers)))
    return answer

결론 : 메모리 값에 대한 지식이 있다면, 훨씬 간단하게 문제를 해결할 수 있다!

프로그래머스 코딩테스트 연습문제 124 나라를 풀어봤다

124 나라

참고[https://thisisablog.tistory.com/14]
124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

124 나라에는 자연수만 존재합니다.
124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.
예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

문제를 보고 패턴을 찾아야겠다는 생각부터 했다.
3의 배수로 끊어지고, 끝자리가 1, 2, 4로 반복된다는 것을 파악했다.

끝자리는 그럼 1,2,4를 돌려주는 것으로 끝낼 수 있는데, 이제 앞자리가 문제가 된다.
앞자리 패턴을 찾기 위해서 문제 표에는 10까지만 나와있지만, 21까지 구해봤다.
21까지 쭉 따라 쓰다보니, 앞자리 역시 1,2,4가 반복되고 있다는 것을 파악했다.
맨 뒷자리 1,2,4가 끝나면 그 다음 자리 index가 하나 올라가고 그 앞의자리도 마찬가지였다.

그렇다면, 뒤에서부터 자리 수를 채워주는 게 낫다고 생각했고
다 채워준 다음에 뒤집어 버리는 방식을 택했다.
그래서

1

[::-1]

을 이용해 줬고 코드는 다음과 같이 작성했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def solution(n):
    if n<3:
    	return n
    elif n==3:
    	return 4
    result=''
    index=['4','1','2']
    rem=0
    quo=0
    
    while n>3:
        rem=n%3
        quo=n//3
        print(rem,quo)
        result+=index[rem]
        print('res = ',result)
        if rem==0: quo-=1
        n=quo
        print('n={}, rem={}, result={}'.format(n, rem, result))
    
    result+=str(n)
    result=result.replace('3','4')
    return result[::-1]