엘리스 코딩 단어 패턴을 풀어봤다

단어 패턴

문자열(패턴) 하나와 문자열의 배열 하나가 주어집니다.
패턴 문자열의 각각의 문자 하나는, 두번째 문자열 배열의 각각의 문자열 하나에 대응 될 수 있습니다.
해당 배열이 해당 패턴으로 표현 되는지 아닌지의 여부를 확인하는 함수를 만들어 보세요.

예를 들어서, aabb 와 [‘elice’, ‘elice’, ‘alice’, ‘alice’] 가 주어졌을 경우에는 함수가 True를 반환해야 합니다. 이 경우에는 a가 elice에, b가 alice에 대응되도록 하면 배열을 해당 패턴으로 표현 하는 것이 가능하기 때문이죠.

반면, aabb 와 [‘elice’, ‘alice’, ‘elice’, ‘alice’] 가 주어졌을 경우에는 함수가 False를 반환해야 합니다.
모든 문자는 영어 소문자라고 가정합니다.

문제를 보고 쉬울거라고 생각했다. 패턴을 쪼개서 각 단어에 매칭을 시켜주면 간단히 해결될 것 같았다.
하지만 패턴을 쪼개서 단어에 매칭 시키는 게 간단한 문제가 아니었다.

지금은 a와 b뿐이지만 만약에 단어리스트가 주어지는개 100개라면 abcd…로 매칭시키는게 힘들다.
물론 그 정도까지로 테스트 케이스가 나올 것 같지는 않지만…

따라서, 일일이 패턴을 매칭시켜서 판단하는 건 힘들다고 판단해서 이렇게 가는 건 아니라고 생각했고
다른 방향을 모색했다.

그러던 중에 불현듯 패턴과 단어리스트를 zip해보고 싶어졌다. 일단 길이는 서로 무조건 같을 거니까.
그리고 패턴이 일치하는 것을 찾는 거니까 set을 하면 의미있는 결과가 나올 듯 싶었다.
코드와 결과는 다음과 같다.

1
2
3

pattern = "aabb"

strList = ["elice", "elice", "alice", "alice"]

1

set(zip(pattern, strList))

1

Out : {('a', 'elice'), ('b', 'alice')}

잘 생각해보니, set을 한 pattern하고 길이가 똑같을 것 같았다. 직관적으로 그런 생각이 들었다.
일단 테스트로 다음과 같은 코드를 작성해봤다.

1
2

pattern1 = "abab"
strList1 = "elice", "elice", "alice", "alice"

1

set(zip(pattern1, strList1))

1

Out : {('a', 'alice'), ('a', 'elice'), ('b', 'alice'), ('b', 'elice')}

역시 단어리스트의 패턴이 다르면 주어진 패턴의 set과는 길이가 달랐다.

그래서 전체코드로는 다음과 같이 작성했다.

1
2
3
4
5
6
7
8
9
10
11

def wordPattern(pattern, strList):
    return len(set(pattern)) == len(set(zip(pattern, strList)))


def main():
    print(wordPattern("aabb", ["elice", "elice", "alice", "alice"])) # should return True
    print(wordPattern("abab", ["elice", "elice", "alice", "alice"])) # should return False
    

if __name__ == "__main__":
    main()

제출결과 빵끗 웃는 토끼가 나왔고, 테스트 점수 100점이 나왔다.

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

카펫

문제 설명

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]

Reference : https://aisolab.github.io/computer%20science/2018/08/09/CS_Object-oriented-programming/ [김보섭님 블로그]