수리링의 데이터교실

한동안 코테를 잠시 안풀었더니

효율성 테스트를 통과하는데 조금 헤맸던 문제입니다..!

Stack 알고리즘을 활용하지 않고 문제를 풀었을 때 테스트 케이스 정확성은 통과하는 데 문제가 없으나, 효율성 테스트를 통과하기 어려우실 수 있습니다. 효율성 테스트까지 통과할 수 있는 문제 풀이 방법을 알려드릴게요 :)

https://school.programmers.co.kr/learn/courses/30/lessons/12909

문제 상황 : 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

1.

먼저 빠른 탈출을 위해 다음 4가지 경우에는 함수를 False로 얼리 리턴하도록 설정해주겠습니다.

• 주어진 문자열이 ")" 로 시작하는 경우
• 주어진 문자열이 "(" 로 끝나는 경우
• 주어진 문자열의 길이가 홀수인 경우
• 주어진 문자열이 ")" 또는 "(" 한 종류로만 이루어진 경우

def solution(s):
    if s[0] == ")" or s[-1] == "(" or len(s) % 2 == 1 or len(set(s)) == 1:
        return False

2.

다음으로 stack 리스트를 선언해주도록 하겠습니다.

    stack = []

우리는 stack 리스트에 "(" 열기 괄호만 넣어줄 것입니다.

왜 열기 괄호만 넣어줄까요? 예시를 통해 한번 확인해 봅시다.

문자열 s = "(((())"가 있다고 합시다. 딱 봐도 열기 괄호는 4개인데 닫기 괄호는 2개여서 짝이 맞지 않는다는 것을 알 수 있습니다. 우리는 for루프를 통해 0번째 자릿값부터 차례대로 돌면서 해당 자리의 값이 "("이면 stack에 넣어주고, ")"이면 stack에 있는 열기괄호를 하나 빼 줄 것입니다.

    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()

s = "(((())"

1. 첫 번째 자리 "(" -> stack = "(" 
2. 두 번째 자리 "(" -> stack = "(", "("
3. 세 번째 자리 "(" -> stack = "(", "(", "("
4. 네 번째 자리 "(" -> stack = "(", "(", "(", "("
5. 다섯 번째 자리 ")" -> stack이 비어있지 않으므로 stack.pop()
   -> stack = "(", "(", "("
6. 여섯 번째 자리 ")" -> stack이 비어있지 않으므로 stack.pop()
   -> stack = "(", "("

    if stack:
        return False
    else:
        return True

이터레이션을 다 돌고 났을 때

stack이 비어 있으면 짝이 맞으므로 True

stack에 남은 값이 있다면 짝이 맞지 않는 것이므로 False를 리턴합니다.

결국 "("의 갯수와 ")"의 갯수가 동일한지 확인하는 것과 다름 없습니다. 다른 방법으로도 정확성 문제는 통과하는 데 어려움이 없으나, 효율성에 문제가 생기는 관계로 stack 알고리즘을 통해 효율성을 높여준 것이라고 보시면 되겠습니다.

3.

마지막으로 한 번에 코드를 보겠습니다.

def solution(s):
    if s[0] == ")" or s[-1] == "(" or len(s) % 2 == 1 or len(set(s)) == 1:
        return False

    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()
    
    if stack:
        return False
    else:
        return True

감사합니다!

https://school.programmers.co.kr/learn/courses/30/lessons/12945

오랜만에 피보나치 수열 문제 풀이를 했습니다. 처음에 간단한 재귀함수를 적용해서 풀이를 했더니 테스트는 모두 통과하는데 효율성 테스트에서 시간 초과로 계속 실패를 하는 문제가 발생했습니다. 그래서 효율성을 올리기 위해 메모화를 적용해서 풀이를 했더니 효율성 테스트도 모두 통과할 수가 있었습니다 :-)

간단하게 풀이방법을 설명해 보겠습니다!

1. 메모화 없이 기본 피보나치 수열 함수 작성하기

def basic_fibonacci(n):
    if n in [1, 2]:
        return 1
    if n == 3:
        return 2

    return basic_fibonacci(n-2) + basic_fibonacci(n-1)

만약 주어진 정수가 1 또는 2라면 바로 1을 리턴,

주어진 정수가 3이라면 바로 2를 리턴하도록 초기 설정을 해 줍니다.

4 이상의 정수 n이 주어졌을 때 재귀함수 형식으로 n-2와 n-1에 basic_fibonacci 함수를 적용한 값을 구해 더한 값을 리턴합니다.

basic_fibonacci(8), basic_fibonacci(9), basic_fibonacci(10), basic_fibonacci(11)
# (21, 34, 55, 89)

위 함수는 제대로 작동하지만, n의 값이 커질수록 효율성이 급격하게 떨어진다는 단점이 있어요. 메모화를 이용해서 함수의 효율을 높여보겠습니다.

2. 메모화를 적용한 피보나치 수열 함수 작성하기

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
    if n in [2, 3, 4, 5, 6]:
        return memo[n]
    
    if n > 6:
        for i in range(7, n+1):
            if i in memo: pass
            else:
                memo[i] = memo[i-2] + memo[i-1]
    
    return memo[n]

하나씩 뜯어보겠습니다 :)

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):

가장 먼저 함수를 선언할 때 파라미터 값으로 memo라는 이름으로 딕셔너리를 포함해 주었습니다. 저는 간단하게 n이 1부터 6번째일때 피보나치 수열 값을 딕셔너리에 초기값으로 미리 메모를 해 두었습니다.

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
    if n in [2, 3, 4, 5, 6]:
        return memo[n]

내가 구하고자 하는 것은 피보나치 수열의 n번째 값입니다. 만약 n이 2, 3, 4, 5, 6인 경우 (문제 조건에서 n은 2 이상의 정수라고 했으므로 1은 제외합니다) memo 딕셔너리의 해당하는 value 값을 바로 리턴하고 함수를 종료하게 됩니다.

    if n > 6:
        for i in range(7, n+1):
            if i in memo: pass
            else:
                memo[i] = memo[i-2] + memo[i-1]
    
    return memo[n]

만약 n이 6보다 크면 어떻게 해야 할까요?

주어진 n의 값이 50일 때를 예시로 생각해 봅시다. 우리는 50번째 값을 구하기 위해 48, 49번째 값이 필요합니다.

49번째 값을 구하기 위해서는 47, 48번째가 필요하고

48번째 값을 구하기 위해서는 46, 47번째가 필요합니다.

결국 50번째 값을 구하기 위해서는 1부터 49번째까지 피보나치 수열 값을 모두 알아야 합니다.

그럼 메모화는 어떻게 작동할까요?

제가 만약 50번째 피보나치 수열 값을 구하기 전에,

40번째 피보나치 수열 값을 먼저 구했다고 생각해 보겠습니다.

fibonacci(40)
# 102334155

우리는 40번째 피보나치 수열 값을 구하기 위해 지금 1번째~39번째 피보나치 수열의 값을 열심히 구했습니다.

이제 다음으로 50번째 피보나치 수열 값을 구하려고 합니다.

먼저 메모화를 해놓지 않은 경우를 생각해 봅시다.

우리는 이미 1번부터 40번째까지의 값을 이전에 미리 구한 전적이 있지만

따로 기록을 해 두지 않았기 때문에 같은 계산을 또 반복해야 합니다.

1번째~49번째 피보나치 수열 값을 열심히 또 구하는 거죠.

하지만 제가 기록을(메모화를) 해 두었다면 얘기가 달라집니다.

즉 처음에 fibonacci(40)을 계산했을 때

memo 딕셔너리에 1번부터 40번까지 피보나치 수열 값을

key(n) : value(값) 형식으로 미리 저장을 해 두었다면,

우리는 fibonacci(50)을 구할 때 

1. 1번부터 40번까지는 간단히 딕셔너리에서 값을 찾아 가져올 수 있습니다.

2. 41번부터 49번째 값은 새로 구하고 딕셔너리에 값을 추가해주는 방식으로 계속해서 메모를 해나갈 수 있습니다.

+ 참고로 함수를 여러번 작동하면서 메모장에 추가하는 key와 value 값은 매번 초기화되지 않고 계속해서 누적 기록을 보관합니다.

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
    # 주어진 정수가 2-6중 하나일 경우 바로 메모장에서 수열값을 찾아 리턴, 함수종료
    if n in [2, 3, 4, 5, 6]:
        return memo[n]
    
    # 주어진 정수가 6보다 큰 경우(7 이상)
    if n > 6:
    	# 7부터 n까지의 정수 i에 대해서
        for i in range(7, n+1):
            # 만약 메모장에 i값이 이미 메모되어 있다면 그냥 넘어가고
            if i in memo: 
                pass
            # 만약 메모장에 i값이 없다면 피보나치 수를 구해서 추가해주세요
            else:
                memo[i] = memo[i-2] + memo[i-1]
    
    # 메모장에서 n번째 피보나치 수열 값을 찾아 리턴해주세요
    return memo[n]

최종 피보나치 함수입니다 :)

내가 구하고자 하는 n의 피보나치 값을 찾기 위해 7부터 n-1번째의 수열값을 계속해서 차례대로 메모장에 누적 메모해나가는 방식입니다. 재귀함수랑 약간 비슷한듯 다른 느낌이네요!

3. 최종 문제풀이

마지막으로 문제 해결을 위해 피보나치 수열을 활용해서 soluton()함수를 작성했습니다. 저는 코딩테스트 문제를 풀 때 이렇게 함수를 나누어 작성하는것을 좋아합니다. 함수 안에 함수 작성하는거 시러요.....(개취)

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
    if n in [2, 3, 4, 5, 6]:
        return memo[n]
    
    if n > 6:
        for i in range(7, n+1):
            if i in memo: 
                pass
            else:
                memo[i] = memo[i-2] + memo[i-1]
    
    return memo[n]

def solution(n):
    fibo_num = fibonacci(n)
    
    # fibonacci(30)< 1234567 < fibonacci(31)
    # 만약 n이 30 이하라면 바로 fibo_num을 리턴하고(몫이 0이므로 나머지와 동일)
    if n <= 30 : 
        return fibo_num
    # 만약 n이 30보다 크다면 fibo_num을 1234567으로 나눈 나머지를 리턴
    else :
        return fibo_num % 1234567

풀이나 설명에 오류가 있다면 댓글로 알려주세요!

감사합니다! :-)

프로그래머스에 비트 연산을 해야하는 MySQL문제가 종종 보이는데요. 정리해놓으면 좋을 것 같아서 문제 풀이를 한번 작성해 보겠습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/301646

문제 : 2번 형질을 보유하지 않으면서 1번이나 3번 형질을 보유하고 있는 대장균 개체의 수(COUNT)를 출력하는 SQL 문을 작성해주세요. 1번과 3번 형질을 모두 보유하고 있는 경우도 1번이나 3번 형질을 보유하고 있는 경우에 포함합니다.

[1] 2진법으로 계산해 보기

먼저 각 열의 GENOTYPE의 수를 2진법으로 바꾸어 출력해 보겠습니다. 주어진 정수 데이터에 BIN() 함수를 사용하면 정수를 2진법 수로 변환한 결과를 출력합니다.

SELECT BIN(GENOTYPE) AS GENOTYPE_BIN
FROM ECOLI_DATA

그럼 이제 출력된 결과를 CAST함수를 이용해서 CHAR 데이터타입으로 바꾼 뒤, WHERE문을 사용해서 필터링을 해 보겠습니다.

SELECT COUNT(*) AS `COUNT` 
FROM (SELECT ID,
             CAST(BIN(GENOTYPE) AS CHAR) AS GENOTYPE_BIN
             FROM ECOLI_DATA) A
WHERE A.GENOTYPE_BIN LIKE '1' OR
      A.GENOTYPE_BIN LIKE '%10_' OR
      A.GENOTYPE_BIN LIKE '%01'

WHERE문의 각 줄은 다음과 같은 결과를 필터링합니다.

1. 서브쿼리문의 수가 1인 경우
2. 서브쿼리가 101 또는 100인 경우
3. 서브쿼리가 01로 끝나는 경우

마지막으로 SELECT COUNT(*) AS `COUNT`를 통해 필터링된 데이터 열의 갯수를 COUNT라는 컬럼명으로 출력하도록 해 주었습니다. 정답 통과입니다.

[2] 비트 연산으로 풀어보기

MySQL에는 비트(Bit) 단위로 논리 연산을 수행하는 연산자가 있습니다. 챗지피티한테 비트 연산자의 종류에 뭐가 있는지 테이블을 만들어 달라고 했는데요.

네. 이런게 있다네요. (^_^;;) 저는 여기서 &연산자와 NOT 연산자를 사용해서 위의 문제를 풀어보겠습니다.

SELECT * FROM ECOLI_DATA
WHERE
    GENOTYPE & 5
    AND NOT GENOTYPE & 2

GENOTYPE & 5

• 정수 5를 2진법 비트로 변환하면 101입니다. 따라서 &5는 값의 첫 번째, 세 번째 비트가 1인지 여부를 확인합니다.

NOT GENOTYPE & 2

• 비트 NOT 연산은 비트를 반전시키는 역할을 합니다. 여기서 2의 이진 표현은 10입니다. 따라서 이 비트 연산은 GENOTYPE 열의 값에서 2번째 비트를 확인하고, 그 값을 반전시키므로, 2번째 비트가 0인지 여부를 확인합니다.

SELECT COUNT(ID) AS `COUNT`
FROM ECOLI_DATA
WHERE
    GENOTYPE & 5
    AND NOT GENOTYPE & 2

마지막으로 카운트한 값을 출력해 주면 정답 통과입니다.

비트 연산자는 간단하게 풀 수 있지만 까먹기 쉽다는 단점이 있는 것 같습니다.

그래도 이런 게 있다는 걸 알아두고 필요할 때마다 열심히 꺼내 보면서 익숙해 져야겠습니다.

<문제 설명>
어느 한 게임에서 사용되는 아이템들은 업그레이드가 가능합니다.
'ITEM_A'->'ITEM_B'와 같이 업그레이드가 가능할 때
'ITEM_A'를 'ITEM_B' 의 PARENT 아이템,
PARENT 아이템이 없는 아이템을 ROOT 아이템이라고 합니다.

(중략)....

<문제>
아이템의 희귀도가 'RARE'인 아이템들의 모든 다음 업그레이드 아이템의 아이템 ID(ITEM_ID), 아이템 명(ITEM_NAME), 아이템의 희귀도(RARITY)를 출력하는 SQL 문을 작성해 주세요. 이때 결과는 아이템 ID를 기준으로 내림차순 정렬해 주세요.

처음에 대충 생각하고 접근했더니 원하는 정답을 얻어내기 어려웠던 문제입니다!

다시 정신을 집중하고, RIGHT 조인과 서브쿼리를 이용해서 문제를 바로 해결했어요.

제가 풀이한 방법을 설명해 보겠습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/273711

먼저 아이템의 희귀도가 'RARE'인 아이템들을 뽑아내서 시각화해 봅니다.

SELECT * FROM ITEM_INFO WHERE RARITY = 'RARE'

우리는 이 4개의 아이템들의 다음 업그레이드 아이템을 찾아야 합니다. 이를 위해서는 ITEM_TREE 테이블을 확인해 보아야 해요.

전 ITEM_TREE 테이블을 보고 직관적으로 이해하기가 어려웠어요. 딱 봤을 때 구조가 한눈에 들어오지 않았습니다. (쉽게 보이시는 분이 계시다면.... 멋지십니다! 따봉!)

그래서 이렇게 간단히 그래프를 그려 봤더니 쉽게 이해가 되었습니다. 우리가 구한 RARE 아이템은 0, 1, 3, 4였어요. 이 아이템들의 다음 업그레이드 아이템은 (0으로부터) 1, 2번 아이템 + (2로부터) 3, 4번 아이템 => 총 1, 2, 3, 4번 아이템이 해당됩니다. 이해가 되셨을까요?

그렇다면 일반화된 쿼리문으로 작성하려면 어떻게 해볼 수 있을까요? 우선 우리가 구한 RARE 아이템 0, 1, 3, 4가 부모가 되는 아이템, 즉 0, 1, 3, 4의 자식 아이템을 찾아야 해요. 이를 위해서 ITEM_TREE 테이블의 PARENT_ITEM_ID와, ITEM_INFO 테이블의 ITEM_ID가 동일한 부분을 연결해 주면 됩니다.

SELECT * FROM ITEM_INFO I
	RIGHT JOIN ITEM_TREE T
	ON I.ITEM_ID = T.PARENT_ITEM_ID
WHERE RARITY = 'RARE'

1) ITEM_INFO 테이블에서 RARITY가 'RARE'에 해당하는 아이템 중에서,

2) 그 아이템이 ITEM_TREE 테이블에 있는 어떤 놈의 PARENT_ITEM_ID에 해당한다면,

3) 그 놈들을 모두 뽑아내봐요.

라고 명령한 것과 같습니다. 그럼 위와 같이 결과를 시각화할 수 있는데요. 여기서 우리에게 필요한 것은 무엇일까요?

우리한테 필요한 것은 저기 저 1, 2, 3, 4번 아이템 번호밖에 없어요. T 테이블(ITEM_TREE)의 ITEM_ID만 뽑아내 주면 됩니다. SELECT 뒤에만 간단하게 바꾸어 줘 봅시다.

SELECT T.ITEM_ID FROM ITEM_INFO I
        RIGHT JOIN ITEM_TREE T
        ON I.ITEM_ID = T.PARENT_ITEM_ID
WHERE RARITY = 'RARE'

이제 우리가 원하는 아이디를 뽑아냈으니, 이 테이블을 서브쿼리로 기존의 ITEM_INFO 테이블과 조인해 주면 끝입니다!

SELECT X.ITEM_ID, I.ITEM_NAME, I.RARITY
FROM (SELECT T.ITEM_ID
      FROM ITEM_INFO I
      RIGHT JOIN ITEM_TREE T
      ON I.ITEM_ID = T.PARENT_ITEM_ID
      WHERE RARITY = 'RARE') X
JOIN ITEM_INFO I ON X.ITEM_ID = I.ITEM_ID
ORDER BY ITEM_ID DESC

서브쿼리는 X로 이름을 지정해 주었습니다. X의 아이템 아이디와 ITEM_INFO 테이블(I)의 아이템 아이디가 같다면 아이디/이름/레어리티를 셀렉하여 프린트하고, 아이템 아이디를 기준으로 내림차순 하여 정렬하도록 지정했습니다.

코드 통과, 정답입니다 :)

이해가 안 되는 부분이 있으시다면 댓글 달아주세요!

서브쿼리와 RIGHT JOIN 연습을 할 수 있었던 좋은 문제였습니다.

프로그래머스의 MySQL 코딩테스트 연습문제 '노선별 평균 역 사이 거리 조회하기' 를 풀었습니다. 서브쿼리와 ORDER BY에 대해 정리해두기 좋은 문제인 것 같아 블로그 포스팅을 해 보도록 하겠습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/284531

먼저, 1차로 제출한 정답코드입니다. (오답)

SELECT ROUTE, 
        CONCAT(ROUND(SUM(D_BETWEEN_DIST), 1), "km") AS TOTAL_DISTANCE,
        CONCAT(ROUND(AVG(D_BETWEEN_DIST), 2), "km") AS AVERAGE_DISTANCE
FROM SUBWAY_DISTANCE
GROUP BY ROUTE
ORDER BY TOTAL_DISTANCE DESC

테스트 케이스는 통과했으나 정답으로 제출하면 결과가 틀리다고 나와 저를 당황스럽게 하였습니다. 무엇이 문제였을까요? 문제 조건을 다시 한 번 살펴보겠습니다.

1) 총 누계 거리와 평균 역 사이 거리의 컬럼명은 각각 TOTAL_DISTANCE, AVERAGE_DISTANCE 
2) 총 누계거리는 소수 둘째자리에서, 평균 역 사이 거리는 소수 셋째 자리에서 반올림 한 뒤 단위(km)를 함께 출력
3) 결과는 총 누계 거리를 기준으로 내림차순 정렬

왠지 CONCAT으로 스트링으로 만들어버린 값을 정렬하면서 3번에서 문제가 생기지 않을까 싶었어요. 그래서 1차로 제출했던 코드에서 CONCAT 함수를 제외한 전체를 서브쿼리로 사용해 보기로 했습니다. 

(SELECT ROUTE, 
        ROUND(SUM(D_BETWEEN_DIST), 1) AS TOTAL_DISTANCE,
        ROUND(AVG(D_BETWEEN_DIST), 2) AS AVERAGE_DISTANCE
FROM SUBWAY_DISTANCE
GROUP BY ROUTE
ORDER BY TOTAL_DISTANCE DESC) BF

먼저 CONCAT을 빼버린 부분을 전체 ( ) 괄호로 묶어서 임시 테이블 BF로 만들어 자기참조합니다.

그럼 2차로 제출한 정답코드를 보여드리겠습니다.

SELECT BF.ROUTE,
       CONCAT(BF.TOTAL_DISTANCE, "km") AS TOTAL_DISTANCE,
       CONCAT(BF.AVERAGE_DISTANCE, "km") AS AVERAGE_DISTANCE
       
FROM (SELECT ROUTE, 
        ROUND(SUM(D_BETWEEN_DIST), 1) AS TOTAL_DISTANCE,
        ROUND(AVG(D_BETWEEN_DIST), 2) AS AVERAGE_DISTANCE
FROM SUBWAY_DISTANCE
GROUP BY ROUTE
ORDER BY TOTAL_DISTANCE DESC) BF

합계: 100.0 / 100.0 (정답)

FROM 뒤에 임시 테이블(이너 테이블) BF를 넣어 줍니다. TOTAL_DISTANCE를 기준으로 내림차순 정렬은 이미 임시 테이블 BF에서 숫자형태로 완료가 된 상태입니다. 이렇게 정렬이 완료된 임시 테이블에서 CONCAT을 이용해 "km"을 붙이고 스트링화 해주었더니 정답으로 인정이 되었습니다.

서브쿼리와 정렬에 대해 생각해볼 수 있는 좋은 문제였습니다.

프로그래머스 코딩테스트 1단계에 수록되어있는 카카오 인턴십 '키패드 누르기' 문제를 풀었습니다. 풀고 나서 코드가 좀 길다고 생각했는데 다른 사람들의 풀이를 보니 다들 비슷한 길이라서 안심이 되었습니다. (한심...ㅎ) 길다고 무조건 나쁜 코드, 짧다고 무조건 좋은 코드는 아니긴 합니다. 그래도 최대한 니트하고 간결하게 작성하고싶은 욕심이 드는 건 어쩔 수가 없네요 ㅎ_ㅎ (그럼에도 불구하고 제 코드는 항상 긴 편인거 같아요.)

저는 키패드에 좌표 개념을 도입하여 간단하게 문제를 풀어보았습니다. 문제 풀이 시간은 5분-10분정도로 그래도 최근에 연습했던 알고리즘 문제들에 비교하면 비교적 수월했던 문제였던 것 같습니다. 그럼 풀어보겠습니다!

문제 상황 : 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다. 1. 엄지손가락은 상하좌우 4가지 방향... (중략....) 자세한 문제 상황과 조건, 입출력, 테스트 케이스 등은 꼭 프로그래머스에서 확인해 보세요! https://school.programmers.co.kr/learn/courses/30/lessons/67256

1. 문제의 이해

먼저 정수로 이루어진 리스트 numbers가 인풋으로 주어집니다. 문제 조건을 보면, 정수가 1, 4, 7일 때에는 바로 왼손을, 3, 6, 9일때는 바로 오른손을 쓰면 되기 때문에 아무런 제약이 없어서 굉장히 쉽습니다. 우리가 고민해야 할 부분은 정수가 2, 5, 8, 0일 때입니다.

2, 5, 8, 0이 주어졌을 때 조건에 맞게 손가락을 움직이기 위해서는

 1)  그 전의 손가락 위치를 알고 있어야 합니다.

 2)  그 전의 손가락 위치와 2/5/8/0 사이의 거리를 숫자로 나타낼 수 있어야 합니다.

 3)  왼손, 오른손과 2/5/8/0 사이의 거리를 비교할 수 있어야 합니다.

그럼 위 세 가지를 고민하면서 문제를 풀어보겠습니다.

2. 풀이

[1] 변수와 좌표 설정

def solution(numbers, hand):
    answer = ""
    current_left_thumb = (4, 1)
    current_right_thumb = (4, 3)

저는 키패드 1이 있는 곳을 좌표 (1, 1)으로, 

키패드 3이 있는 곳을 좌표 (1, 3)으로,

키패드 *이 있는 곳을 좌표 (4, 1)으로,

키패드 #이 있는 곳을 좌표 (4, 3)으로 놓았습니다.

첫줄을 파이썬 인덱싱과 같이 0부터 시작할까 하다가 보다 직관적으로 하기 위해 1부터 시작해줬는데, 0부터 시작해도 큰 상관은 없습니다.

current_left_thumb, current_right_thumb라는 변수명을 사용하여 왼손/오른손을 구분하여 현재 손가락이 어디 있는지를 좌표값으로 표현했습니다. 변수명이 조금 길고 번잡하긴 하지만 직관적으로 이해할 수 있어서 스스로 코드 이해하기가 편했습니다. 이 두 가지 변수는 앞으로 numbers에 주어진 정수값에 따라 손가락이 움직일 때 함께 업데이트가 되어 갈 예정입니다!

[2] 1/4/7, 3/6/9 처리

    for number in numbers:
        if number == 1:
            answer += "L"
            current_left_thumb = (1, 1)
        elif number == 4:
            answer += "L"
            current_left_thumb = (2, 1)
        elif number == 7:
            answer += "L"
            current_left_thumb = (3, 1)
        elif number == 3:
            answer += "R"
            current_right_thumb = (1, 3)
        elif number == 6:
            answer += "R"
            current_right_thumb = (2, 3)
        elif number == 9:
            answer += "R"
            current_right_thumb = (3, 3)

다음으로 numbers 리스트의 값(value)를 가지고 하나씩 살펴보면서 이터레이션을 돌려줍니다. 리스트 이터레이션은 습관적으로 인덱스로 하게 되는데, 이번 문제에서는 굳이 인덱스로 조회할 필요가 없어서 편했습니다.

만약 number가 1/4/7중에 하나라면 answer 스트링에 L을 추가하고 해당 좌표값으로 왼손을 움직입니다(current_left_thumb 변수의 좌표를 업데이트합니다.). 만약 number 3/6/9중에 하나라면 answer 스트링에 R을 추가하고 해당 좌표값으로 오른손을 움직입니다(current_right_thumb 변수의 좌표를 업데이트합니다.). 

이 부분의 문법이 어쩔수없이 위처럼 길어지게 되었는데, 어떻게 하면 더 짧게 쓸 수 있을까 잠깐 고민했어요. 하지만 지금 이대로도 아주 직관적이고 이해하기 편하기 때문에 굳이 줄이지 않아도 되겠다고 판단하고 다음 단계로 넘어갔습니다.

[3] 2/5/8/0 처리

        elif number in [2, 5, 8, 0]:
            if number == 2: x = 1
            if number == 5: x = 2
            if number == 8: x = 3
            if number == 0: x = 4

다음으로 가장 중요한 2, 5, 8, 0입니다. 저는 2, 5, 8, 0이 모두 같은 세로줄에 있다는 점에 착안하여 아이디어를 얻어서 2/5/8/0의 열(y)을 2로 고정하고 행(x)만 변수로 각각 1/2/3/4를 할당해 주었습니다. 더 자세히 설명해보겠습니다.

숫자 2의 좌표값은 (1, 2)입니다.

숫자 5의 좌표값은 (2, 2)입니다.

숫자 8의 좌표값은 (3, 2)입니다.

숫자 0의 좌표값은 (4, 2)입니다.

따라서 숫자 2, 5, 8, 0의 좌표를 (x, 2)와 같이 표현하고 x에만 각각 1/2/3/4를 할당해 주어 반복을 줄이겠다는 의미입니다.

distance_r = abs(current_right_thumb[0] - x) + abs(current_right_thumb[1] - 2)
distance_l = abs(current_left_thumb[0] - x) + abs(current_left_thumb[1] - 2)

# 가독성을 위해 인덴트를 없앴습니다

이제 거리 구하기로 넘어갑니다. 우리는 current_left_thumb와 current_right_thumb 라는 변수에 각각 왼손과 오른손 엄지의 직전 좌표값을 저장해 두고 있어요. 우리가 가고자 하는 2/5/8/0의 좌표값과 왼손, 오른손 사이의 거리를 각각 구해보도록 하겠습니다.

일반화된 식을 쓰기 전에 예시를 가지고 생각을 열어 볼게요. 키패드 2와 6 사이의 거리는 2입니다. 좌표로 어떻게 구할 수 있을까요? 키패드 2의 좌표는 (1, 2), 키패드 6의 좌표는 (2, 3)입니다. x값의 차이 1과 y값의 차이 1을 더해 주면 간단히 2가 나오는 것을 알 수 있어요. 키패드 8과 키패드 1의 경우는 어떨까요? 우선 거리는 3입니다. 좌표로 확인해 봅니다. 키패드 8의 좌표는 (3, 2)입니다. 키패드 1의 좌표는 (1, 1)입니다. x값의 차이 2와 y값의 차이는 1이며 둘을 더해 주면 3이 됩니다. 이제 일반화가 되었습니다.

abs(current_right_thumb[0] - x) : 오른손 엄지손가락의 행좌표와 2/5/8/0의 행좌표(x)의 차(절댓값)

abs(current_right_thumb[1] - 2) : 오른손 엄지손가락의 행좌표와 2/5/8/0의 열좌표(2)의 차(절댓값)

이 두개를 더해 주면 오른손이 움직이는 거리(distance_r)가 되고,

같은 방법으로 왼손이 움직이는 거리(distance_l)도 구해준 거예요.

            if distance_r < distance_l:
            # 오른손이 가야 하는 거리가 더 짧을 때
                answer += "R"
                current_right_thumb = (x, 2)
            elif distance_r > distance_l:
            # 왼손이 가야 하는 거리가 더 짧을 때
                answer += "L"
                current_left_thumb = (x, 2)
            else:
            # 왼손 = 오른손 거리가 같을 때
                if hand == 'right':
                # 오른손잡이라면
                    answer += "R"
                    current_right_thumb = (x, 2)
                else:
                # 왼손잡이라면
                    answer += "L"
                    current_left_thumb = (x, 2)

이제 거리를 비교합니다. 오른손이 가야 하는 거리가 더 짧을 때, 왼손이 가야 하는 거리가 짧을 때, 왼손과 오른손이 가야할 거리가 같을 때로 크게 셋으로 나누어 생각합니다. 특히 왼손, 오른손 거리가 같다면 왼손잡이인지 오른손잡이인지를 판단하는 것이 중요합니다.

이제 제가 작성한 함수를 한 번에 보겠습니다.

def solution(numbers, hand):
    answer = ""
    current_left_thumb = (4, 1)
    current_right_thumb = (4, 3)

    for number in numbers:
        if number == 1:
            answer += "L"
            current_left_thumb = (1, 1)
        elif number == 4:
            answer += "L"
            current_left_thumb = (2, 1)
        elif number == 7:
            answer += "L"
            current_left_thumb = (3, 1)
        elif number == 3:
            answer += "R"
            current_right_thumb = (1, 3)
        elif number == 6:
            answer += "R"
            current_right_thumb = (2, 3)
        elif number == 9:
            answer += "R"
            current_right_thumb = (3, 3)
        elif number in [2, 5, 8, 0]:
            if number == 2: x = 1
            if number == 5: x = 2
            if number == 8: x = 3
            if number == 0: x = 4

            distance_r = abs(current_right_thumb[0] - x) + abs(current_right_thumb[1] - 2)
            distance_l = abs(current_left_thumb[0] - x) + abs(current_left_thumb[1] - 2)
            if distance_r < distance_l:
                answer += "R"
                current_right_thumb = (x, 2)
            elif distance_r > distance_l:
                answer += "L"
                current_left_thumb = (x, 2)
            else:
                if hand == 'right':
                    answer += "R"
                    current_right_thumb = (x, 2)
                else:
                    answer += "L"
                    current_left_thumb = (x, 2)
    return answer

숫자가 2, 5, 8, 0일 때 열 좌표가 2로 모두 동일하다는 점에 착안하여 행 좌표만 x로 변수 할당을 해줌으로써 반복을 줄일 수 있었습니다. 비록 엄청 짧은 코드는 아니지만 깔끔하고 직관적으로 풀이할 수 있어서 좋았습니다!

부족한 풀이었지만 도움이 되었으면 좋겠네요~ 감사합니다.

https://school.programmers.co.kr/learn/courses/30/lessons/159994

프로그래머스 코딩테스트 1단계에 수록되어 있는 '카드 뭉치' 문제를 풀었습니다. 다른 사람의 풀이와 비교해보니 제가 조금 독특하게 풀었더라구요. 제 코드가 좀 지저분하긴 하지만 남들과 다른 아이디어로 푼 게 마음에 들어 sorted 문법 정리할 겸 풀이과정을 작성해보고자 합니다.

우선 제출한 답안은 다음과 같습니다.

def solution(cards1, cards2, goal):
    cards1_sorted = sorted(enumerate(cards1), 
    	key = lambda x: (goal.index(x[1]) if x[1] in goal else len(goal) + 1))
    cards2_sorted = sorted(enumerate(cards2), 
    	key = lambda x: (goal.index(x[1]) if x[1] in goal else len(goal) + 1))
                           
    index_1 = [index for index, value in cards1_sorted]
    index_2 = [index for index, value in cards2_sorted]
    
    if index_1 != sorted(index_1) or index_2 != sorted(index_2):
        return "No"
    else:
        return "Yes"

하나씩 쪼개어 정리해 보겠습니다.

테스트케이스의 2번째 예시로 설명해 보겠습니다.

1. 먼저, cards1과 cards2에 enumerate() 함수를 이용해서 (인덱스, 카드)값이 되도록 만들어 줍니다. list()함수를 씌워 결과값을 눈으로 확인하면 다음과 같습니다.

cards1 = ["i", "water", "drink"]
cards2 = ["want", "to"]	
goal = ["i", "want", "to", "drink", "water"]	

list(enumerate(cards1))
# [(0, 'i'), (1, 'water'), (2, 'drink')]

list(enumerate(cards2))
# [(0, 'want'), (1, 'to')]

2. 저는 이렇게 추출한 이뉴머레이트 결과값을, sorted()를 이용해서 정렬을 해줄 거에요. 이 때 정렬을 해 주는 기준으로 goal을 넣어 주어서, goal에 있는 순서대로 정렬되도록 하겠습니다.

cards1_sorted = sorted(enumerate(cards1), key = lambda x: goal.index(x[1])
cards2_sorted = sorted(enumerate(cards2), key = lambda x: goal.index(x[1])

cards1_sorted
# [(0, 'i'), (2, 'drink'), (1, 'water')]

cards2_sorted
# [(0, 'want'), (1, 'to')]

key = lambda x: goal.index(x[1]) 와 같이 정렬 조건을 걸어줌으로써, cards1의 이뉴머레이트 결과값의 인덱스 1번 벨류가 goal에 어떤 순서대로 있느냐?를 기준으로 정렬한 값을 반환하도록 하였습니다. 결과값을 확인해보니 cards2는 그대로이지만 cards1은 drink가 앞으로 온 것을 확인할 수 있습니다. 그런데 이 문법에는 문제가 있습니다. 만약 cards1에 있는 단어가 goal에 없다면 어떻게 될까요?

2 - (1)

cards1 = ["i", "water", "drink", "apple"]
cards1_sorted = sorted(list(enumerate(cards1)), key = lambda x: goal.index(x[1]))

# ValueError: 'apple' is not in list

cards1에 'apple'을 추가해 보니, 벨류 에러가 발생합니다. 따라서 이렇게 없는 값이 있을 경우에는 cards1_sorted의 맨 뒤에다가 값을 추가해주도록 조건을 걸어주겠습니다.

cards1_sorted = sorted(list(enumerate(cards1)), 
             	   key = lambda x: (goal.index(x[1]) if x[1] in goal else len(goal) + 1))
cards2_sorted = sorted(list(enumerate(cards2)), 
            	   key = lambda x: (goal.index(x[1]) if x[1] in goal else len(goal) + 1))

만약 x[1]이 goal에 있다면 기존대로 정렬을 하고, 없다면 뒤에 추가하도록 if else 구문을 사용하여 조건을 걸어줬습니다. 이 부분은 챗지피티의 도움으로 완성할 수 있었습니다^_ㅠ 엄청 직관적인 문법이 아닌것 같긴 합니다만 그래도 자주 사용해서 자유자재로 구사할 수 있도록 하려고 합니다.

다시 apple이 없었던 원래의 예시문제로 돌아가서 계속해서 설명해보겠습니다.

3.

index_1 = [index for index, value in cards1_sorted]
index_2 = [index for index, value in cards2_sorted]


index_1
# [0, 2, 1]
index_2
# [0, 1]

이제 cards1_sorted와 cards_2sorted에서 인덱스만 뽑아서 깔끔한 리스트 index_1, index_2로 뽑아냅니다. 저는 이 index 리스트의 결과값이 0-2-1처럼 순서에 맞지 않을 경우 카드를 앞에서부터 차례로 사용하는 조건에 어긋난다는 점을 발견했습니다. 

따라서 index_1, index_2가 오름차순으로 정렬되어 있다면 "Yes"를, 그렇지 않다면(순서가 뒤죽박죽이라면) "No"를 리턴하도록 함수를 작성했습니다.

def solution(cards1, cards2, goal):
    cards1_sorted = sorted(enumerate(cards1), key = lambda x: (goal.index(x[1]) if x[1] in goal else len(goal) + 1))
    cards2_sorted = sorted(enumerate(cards2), key = lambda x: (goal.index(x[1]) if x[1] in goal else len(goal) + 1))

    index_1 = [index for index, value in cards1_sorted]
    index_2 = [index for index, value in cards2_sorted]
    
    if index_1 != sorted(index_1) or index_2 != sorted(index_2):
        return "No"
    else:
        return "Yes"

최근에 sorted() 함수에 대해서 리뷰를 했으며 특히 key 뒤에 lambda 함수를 어떻게 활용할 수 있는 지 여러번 살펴보았기 때문에 위와 같은 아이디어로 문제를 풀 수 있었습니다. 다른 사람의 풀이를 확인해보니 이런 방식으로 풀이를 하신 분은 찾아보기 어려웠고 더 짧고 깔끔하고 반듯하게 푸신 분이 많아서 존경스러웠습니다! 아주 깔끔한 코드는 아니지만 그래도 재밌는 아이디어로 풀어낸 점을 스스로 높게 평가하고자 합니다 ^_^!

감사합니다.

탐색으로 풀어보려고 했으나 경우의 수를 모두 나누기가 어려웠습니다. 다른사람들의 풀이를 참고해 보니 direction 값을 right부터 시작하여 순차적으로 바꾸어나가는 이터레이션을 돌리면 간단하게 해결이 가능했습니다.

문제 설명 : 양의 정수 n이 매개변수로 주어집니다. n × n 배열에 1부터 n2 까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열을 return 하는 solution 함수를 작성해 주세요.

코드로 작성해 봅시다.

# 예시 (n=3일 때)

n = 3
graph = [[0] * n for _ in range(n)]

graph
# [[0, 0, 0],
#  [0, 0, 0],
#  [0, 0, 0]]

먼저 함수 초반에 그래프의 초기값은 다음과같이 세팅해줍니다. 확실히 리스트 컴프리핸션은 자유자재로 쓸 수 있어야 합니다.

# 기본 뼈대

for i in range(1, n**2+1):
    if dir == 'r':
        y += 1
    elif dir == 'd':
        x += 1
    elif dir == 'l':
        y -= 1
    elif dir == 'u'
        x -= 1

방향의 값은 오른쪽부터 시작해서 나선형으로 오른쪽 -> 아래 -> 왼쪽 -> 위 -> 오른쪽 ...(반복) 순서로 뱅글뱅글 돌아가게 해줄 겁니다. 그럼 완성된 함수로 작성해 보겠습니다.

def solution(n):
	# 만약 n이 1인 경우 빠르게 종료
    if n == 1:
    	return [[1]]
        
    # 초기값 세팅 : (0, 0)으로부터 오른쪽 이동부터 시작한다.
    graph = [[0] * n for _ in range(n)]
    x = 0
    y = 0
    direction = 'R'
	
    # n의 제곱번 이터레이션을 돌려 준다.
    for i in range(1, n**2 + 1):
    	graph[x][y] = i
        
        # right : x값 고정, y값만 1 증가
        if direction == 'R':
            y += 1
            # 만약 끝까지 갔거나 그 다음 값이 0이 아니라면 방향 변경
            if y == n-1 or graph[x][y+1] != 0:
            	direction = 'D'

        # down : y값 고정, x값만 1 증가
        elif direction == 'D':
        	x += 1
            # 만약 끝까지 갔거나 그 다음 값이 0이 아니라면 방향 변경
            if x == n-1 or graph[x+1][y] != 0:
            	direction = 'L'

        # left : x값 고정, y값만 1 감소
        elif direction == 'L':
        	y -= 1
            # 만약 끝까지 갔거나(y값이 0) 그 다음 값이 0이 아니라면 방향 변경
            if y == 0 or graph[x][y-1] != 0:
            	direction = 'U'
                
        # up : y값 고정, x값만 1 감소
        elif direction == 'L':
        	x -= 1
            # 만약 끝까지 갔거나 그 다음 값이 0이 아니라면 방향 변경
            if x == n-1 or graph[x-1][y] != 0:
            	direction = 'R'
                
        return graph

완성된 함수에는 더이상 갈 곳이 없거나 가야할 곳에 0이 아닌 숫자가 있는 경우 방향을 변경해주는 기능이 추가되었습니다. 25번 이터레이션을 돌면서 각각의 순서에 맞게 번호가 부여됩니다.

아휴 재밌다