[프로그래머스 Lv.1] - 카드뭉치 (리스트 정렬여부를 체크하는 효율적인 방법)

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

프로그래머스

 

문제

 

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

- 원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
- 한 번 사용한 카드는 다시 사용할 수 없습니다.
- ★ 카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다. (이 부분을 놓쳐서 마지막 테스트케이스를 실패했었다..)
- 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.

예를 들어 첫 번째 카드 뭉치에 순서대로 ["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):
    Alist = []
    Blist = []
    dic1 = dict([(cards1[i], i) for i in range(len(cards1))])
    dic2 = dict([(cards2[i], i) for i in range(len(cards2))])
    for word in goal:
        if word in dic1:
            Alist.append(dic1[word])
        else:
            Blist.append(dic2[word])

    return "Yes" if all(x<y and x+1==y for x, y in zip(Alist[:-1], Alist[1:])) 
    		and all(x<y and x+1==y for x, y in zip(Blist[:-1], Blist[1:])) else "No"

 

 

cards1,  cards2는 고정되어 있는 카드의 순서이기 때문에 각 카드뭉치별로 순서를 관리할 수 있는 dictionary를 만들고, 해해당 dictionary를 통하여 goal이 어떤 순서로 되어있는지는 두개 리스트로 구분하여 따로 체크할 수 있도록 구현하였다. 

 

goal의 순서를 관리하고있는 두개의 리스트가 각각 오름차순 정렬이고 +1 만큼 증감되는 리스트가 맞다면 Yes이고 아니라면 No로 반환되게 하였다. 이때, 문제에 나온 4개의 조건 중 3번째 조건을 인지하지 못하여 +1증감 체크조건을 빠트려서 마지막 테스트케이스를 실패하였다. 따라서 문제의 조건을 놓치지 않고 잘 보는 것도 중요하다. 

 

(메모리를 더 차지하는 행위이기에 효율적인 방법은 아닌 것 같아 효율적인 방법을 찾아보니 dictionary나 리스트를 따로 만들지 않고 인자값에서 pop(0) 하는 방법도 있다.) 

 

 

 

리스트의 정렬 여부를 체크하는 효율적인 방법

 

어쨌든 내가 풀고자 하는 로직에서 가장 중요했던 부분은 리스트가 정렬되어있는지 체크하는 부분이었다. Alist와 Blist를 체크하는 부분은 동일하니 Alist로 예를 들어 설명해보겠다. 

 

Alist = [0,1,2] 라고 가정하자.

 

값들의 오름차순 정렬 여부를 확인하기 위해 다음과 같이 sorted 함수를 이용할 수 있다. 순서대로 정렬한 리스트가 원래 리스트와 같은지를 확인하는 방식이다. 직관적으로 생각했던 방법이다. 

 

isSorted = (sorted(Alist) == Alist)

 

 

여기서 내림차순 정렬 여부를 확인하기 위해서는 sorted함수의 결과리스트를 인덱싱하거나 sorted함수에 reverse=True라는 인자를 넣어주는 방법이 있다.

 

isSorted = (sorted(Alist)[::-1]         == Alist)
isSorted = (sorted(Alist, reverse=True) == Alist)

 

 

But, 위에 방법은 정렬이라는 작업이 한번 수행되어야하기 떄문에 리스트의 길이가 길어진다면 시간이 많이 걸릴 수 있다. 리스트를 그대로 둔 상태에서 체크할 수 있는 방법이 있을까? 하고 찾아보니 all 함수를 이용하거나 zip 함수를 이용한 방법이었다. 

 

All 이용

 

all 은 인자로 주어진 리스트의 모든 요소가 True일 때 True를 반환해주는 함수이다. 

 

isSorted = all(Alist[i] < Alist[i+1] for i in range(len(Alist)-1))

 

 

=> 반복할 때 range대신 zip이용하기 

 

zip은 길이가 같은 반복가능한 개체들을 인자로 여러개 받아들여 순서대로 각 객체들에 있는 요소들을 앞에서부터 각각 하나씩 순서대로 반환하는 함수이다.

 

AlistX = Alist[:-1]  # [0,1,2]
AlistY = Alist[1:]   # [1,2,3]

for x, y in zip(AlistX, AlistY):
    print(x, y)
    # 0, 1
    # 1, 2
    # 2, 3

 

 

이렇듯 Alist라는 리스트에서 인접한 두쌍을 계속 리턴하는 방법을 생각할 수 있다. 따라서 인접한 두 숫자를 비교하는 데에도 사용할 수 있다.

 

# 오름차순 정렬 여부 체크 
isSorted = all(x<y for x, y in zip(Alist[:-1], Alist[1:]))

# 내림차순 정렬 여부 체크
isSorted = all(x>y for x, y in zip(Alist[:-1], Alist[1:]))

 

 

※ 그렇다면 all이나 zip함수는 sorted함수를 사용하는 방법보다 얼마나 더 빠를까?

 

Alist = [random.randint(0,100) for i in range(10**6)]

t1 = time.time()
isSorted = (Alist == sorted(Alist))
t2 = time.time()

print('isSorted={}'.format(isSorted), '{:.6f} secs'.format(t2-t1))

t1 = time.time()
isSorted = all(x<=y for x, y in zip(Alist[:-1], Alist[1:]))
t2 = time.time()

print('isSorted={}'.format(isSorted), '{:.6f} secs'.format(t2-t1))


# isSorted=False 0.283676 secs
# isSorted=False 0.013229 secs

 

sorted 함수를 이용하였을 때에는 약 0.284초, all과 zip을 이용하였을 때에는 0.013초가 걸렸다. all 과 zip 만을 이용하여 정렬 여부를 확인하는 것이 약 20배 빠른 성능을 보여주었다.