99클럽 코테 스터디 11일차 TIL + 정렬

오늘의 문제 - 정렬

문제 설명

코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.

원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
한 번 사용한 카드는 다시 사용할 수 없습니다.
카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.
예를 들어 첫 번째 카드 뭉치에 순서대로 ["i", "drink", "water"], 두 번째 카드 뭉치에 순서대로 ["want", "to"]가 적혀있을 때 ["i", "want", "to", "drink", "water"] 순서의 단어 배열을 만들려고 한다면 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want"와 "to"를 사용하고 첫 번째 카드뭉치에 "drink"와 "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다.

문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때, cards1과 cards2에 적힌 단어들로 goal를 만들 있다면 "Yes"를, 만들 수 없다면 "No"를 return하는 solution 함수를 완성해주세요.

 

제한 사항

• 1 ≤ cards1의 길이, cards2의 길이 ≤ 10
• 1 ≤ cards1[i]의 길이, cards2[i]의 길이 ≤ 10
• cards1과 cards2에는 서로 다른 단어만 존재합니다.
• 2 ≤ goal의 길이 ≤ cards1의 길이 + cards2의 길이
• 1 ≤ goal[i]의 길이 ≤ 10
• goal의 원소는 cards1과 cards2의 원소들로만 이루어져 있습니다.
• cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 이루어져 있습니다.

입출력 예

---

내 풀이 및 접근 방식

def solution(cards1, cards2, goal):
    answer = 'Yes'
    for g in goal:
        if cards1 and g == cards1[0]:
            cards1.pop(0)
        elif cards2 and g == cards2[0]:
            cards2.pop(0)
        else:
            answer ='No'
            break
        
    return answer

 

풀이 방식

for문으로 goal의 단어들을 순회하며 아래 과정을 반복한다.

1. cards1의 첫번째 원소와 비교하고 같다면, cards1의 첫번째 원소 제거
2. cards2의 첫번째 원소와 비교하고 같다면 cards2의 첫번째 원소 제거
3. 위 2개의 조건을 충족하지 않는다면, 순서대로 단어를 만들 수 없으므로 answer를 No로 하고 break

페어프로그래밍 하면서 list의 pop을 사용하는 방식보다 deque의 popleft를 사용하는 방식이 더 효율적이라는 것을 알게 됐다. pop(0)의 경우 첫 번째 요소가 제거된 후, 나머지 요소들이 한 칸씩 앞으로 이동하는 동작이 발생하며 이때 시간복잡도는 O(n)이다. 그러나 deque는 양쪽 끝에서의 삽입과 삭제가 O(1) 시간 복잡도를 가지기 때문에 더 효율적이라 할 수 있다.

그래서 deque를 이용한 풀이는 아래와 같음

from collections import deque

def solution(cards1, cards2, goal):
    
    cards1 = deque(cards1)	# deque화
    cards2 = deque(cards2)	# deque화

    for g in goal:
        if cards1 and g == cards1[0]:
            cards1.popleft()
        elif cards2 and g == cards2[0]:
            cards2.popleft()
        else:
            return 'No'
    return 'Yes'

---

다른 풀이

인덱스를 이용한 풀이

from collections import deque

def solution(cards1, cards2, goal):
    
    idx1 = 0
    idx2 = 0
    len1 = len(cards1)
    len2 = len(cards2)
    
    for g in goal:
        if idx1 < len1 and g == cards1[idx1]:
            idx1 += 1
        elif idx2 < len2 and g == cards2[idx2]:
            idx2 += 1
        else:
            return 'No'
        
    return 'Yes'

 

풀이 방식

goal의 단어를 순회하며, 각 단어와 맞는 단어가 있을 때마다 카드의 인덱스를 증가시키는 방식이다.

카드의 인덱스 오류를 방지하기 위해, 카드 길이를 구하고 인덱스가 카드 길이보다 작은 경우를 조건으로 추가하였다.

---

회고

페어프로그래밍하면서 시간이 남아서 챌린저 문제까지 풀어봤다.

앞으로도 챌린저 문제까지 도전해보면 좋을 듯하다.

 

문제: 프로그래머스 - 가장 큰 수 https://school.programmers.co.kr/learn/courses/30/lessons/42746#

from itertools import permutations

def solution(numbers):
    answer = ''
    
    numbers = list(map(str, numbers))	# 숫자 => 문자
    numbers.sort(key=lambda x: x*3, reverse=True)	# 각 숫자는 1000이하이므로, 문자*3을 비교하여 정렬

    if numbers[0] == '0':	# 가장 최댓값이 0인 경우 000이 될 수 없으니, '0'만 출력한다
        answer = '0'
    else:	# 나머지 공백없이 이어붙이기
        answer = ''.join(numbers)
    
    return answer

 

핵심은 문자*3 비교하면 제대로 정렬되는 것이다.

[3, 30, 34, 5, 9] 는 [9, 5, 34, 3, 30] 이런식으로 정렬되어야하는데, 나같은 경우, x 자체 값으로 비교하여 출력하다보니 [9, 5, 34, 30, 3] 값으로 정렬됐다. 제대로 정렬하기 위해서는 문자를 3번 곱하면 343434, 303030, 333 을 비교하여 정렬하므로, [34, 3, 30]으로 제대로 정렬된다는 것을 잘 캐치해야했던 것 같다.

그리고 최댓값이 0인 경우에도 잘 고려하여 처리해줘야 해결 가능했던 문제인 것 같다.