[프로그래머스/Level2] 튜플 (2019 카카오 개발자 겨울 인턴십)

문제 설명

셀 수 있는 수량의 순서 있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

• (a1, a2, a3, ..., an)

 

튜플은 다음과 같은 성질을 가지고 있습니다.

1. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
2. 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
3. 튜플의 원소 개수는 유한합니다.

 

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

• {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

 

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

와 같이 표현할 수 있습니다. 이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
• {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

 

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

• s의 길이는 5 이상 1,000,000 이하입니다.
• s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.
• 숫자가 0으로 시작하는 경우는 없습니다.
• s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
• s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
• return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

---

[입출력 예]

s	result
"{{2},{2,1},{2,1,3},{2,1,3,4}}"	[2, 1, 3, 4]
"{{1,2,3},{2,1},{1,2,4,3},{2}}"	[2, 1, 3, 4]
"{{20,111},{111}}"	[111, 20]
"{{123}}"	[123]
"{{4,2,3},{3},{2,3,4,1},{2,3}}"	[3, 2, 4, 1]

 

입출력 예에 대한 설명

 

입출력 예 #1

문제 예시와 같습니다.

 

입출력 예 #2

문제 예시와 같습니다.

 

입출력 예 #3

(111, 20)을 집합 기호를 이용해 표현하면 {{111}, {111,20}}이 되며, 이는 {{20,111},{111}}과 같습니다.

 

입출력 예 #4

(123)을 집합 기호를 이용해 표현하면 {{123}} 입니다.

 

입출력 예 #5

(3, 2, 4, 1)을 집합 기호를 이용해 표현하면 {{3},{3,2},{3,2,4},{3,2,4,1}}이 되며, 이는 {{4,2,3},{3},{2,3,4,1},{2,3}}과 같습니다.

---

나의 풀이

[Python(파이썬)]

def solution(s):
    answer, temp, numtemp, digittemp = [], [], [], []

    for i in s:
        if i == '{':
            continue
        if i.isdigit():
            digittemp.append(i)
        else:
            if len(digittemp) != 0:
                numtemp.append(int(''.join(digittemp)))
                digittemp = []
            if i == '}':
                if len(numtemp) != 0:
                    temp += [numtemp]
                    numtemp = []

    temp.sort(key=len)

    for j in range(len(temp)):
        answer.append(temp[j][0])
        for k in range(j+1, len(temp)):
            temp[k].remove(temp[j][0])

    return answer

 

---

학습한 내용

※ 풀기 전 문제에서 체크할 내용

- 숫자가 0으로 시작하는 경우는 없다. 
- s는 항상 중복되는 원소가 없는 튜플을 표현
- 배열 형태로 return

 

풀이과정
1. {{a1}, {a1, a2}, {a1, a2, a3}, ... {a1, a2, a3,..., an}}로 이루어진 s를 리스트로 바꾸기
2. 집합을 길이 순으로 정렬하기
3. s가 표현하는 튜플 구하기

 

1. {{a1}, {a1, a2}, {a1, a2, a3}, ... {a1, a2, a3,..., an}}로 이루어진 s를 리스트로 바꾸기

 

길이 순으로 정렬을 하려면 리스트 형태여야 해서 {{,}} 이루어진 형태를 리스트로 바꿔줬다. 

    for i in s:
        if i == '}':
            if len(numtemp) != 0:
                temp += [numtemp]
                numtemp = []
        if i.isdigit():
            numtemp.append(i)

 

처음에는 위와 같이 '}'를 만나기 전까지 숫자들을 numtemp 리스트에 저장한 후 '}'를 만나면 temp에 넣어줬다. 

그랬더니 "{{1,2,3},{2,1},{1,2,4,3},{2}}"와 같은 한자리 숫자들은 가능한데 두 자리 이상의 숫자가 오면 성립이 되지 않았다. 

 

숫자가 두자리 이상일 때는 어떻게 해야 하는가?

    for i in s:
        if i == '{':
            continue
        if i.isdigit():
            digittemp.append(i)
        else:
            if len(digittemp) != 0:
                numtemp.append(int(''.join(digittemp)))
                digittemp = []
            if i == '}':
                if len(numtemp) != 0:
                    temp += [numtemp]
                    numtemp = []

digittemp 리스트에 숫자가 아닐 때까지 append 하고 숫자가 아닌 형태가 들어오면 numtemp에 append

 

ex) {123,23}인 경우 

1. ','가 오기 전까지 digittemp에 [1,2,3]으로 담아둔다. 

2. ','이기 때문에 numtemp에 [123]으로 담고 digittmep = []

3. '}'가 오기 전까지 digittmep에 [2,3]으로 담아둔다. 

4. '}'이기 때문에 numtemp에 [123, 23]으로 담고 digittmep = []

 

 

2. 리스트를 길이 순으로 정렬하기

 

temp.sort(key=len) : 리스트의 길이대로 정렬

# sort() : 첫번째 숫자의 크기대로 정렬(단, 숫자가 같다면 뒤의 숫자의 크기대로 정렬)
>>> test = [[1, 2, 3, 4], [2], [2, 1, 3], [1, 2]]
>>> test.sort()
>>> test
[[1, 2], [1, 2, 3, 4], [2], [2, 1, 3]]

# sort(key = len) : 길이 순으로 정렬 
>>> test = [[1, 2, 3, 4], [2], [2, 1, 3], [1, 2]]
>>> test.sort(key=len)
>>> test
[[2], [1, 2], [2, 1, 3], [1, 2, 3, 4]]

 

 

3. s가 표현하는 튜플 구하기

for j in range(len(temp)):
    answer.append(temp[j][0])
    for k in range(j+1, len(temp)):
        temp[k].remove(temp[j][0])

 

ex) [[2], [1, 2], [2, 1, 3], [1, 2, 3, 4]]인 경우

[2]의 원소를 answer.append 하고 for문을 돌면서 [1, 2], [2, 1, 3], [1, 2, 3, 4]에서 2를 삭제해 나갔다. -> [1], [1, 3], [1, 3, 4]

이중 for문을 사용하다 보니 왠지 시간이 많이 걸릴 것 같았는데 역시나 값이 많을수록 시간이 많이 걸렸다. 

이중 for문 이용

 

 

    for j in range(len(temp)):
        temp[j] = set(temp[j])
        if j == 0:
            answer.append(list(temp[j])[0])
        else:
            answer.append(list(temp[j]-temp[j-1])[0])

 

시간을 줄일 수 있는 방법을 찾다가 set의 차집합을 이용해보았다. 

그랬더니 시간이 반 정도 줄어든 모습을 볼 수 있었다. 

set의 차집합 이용

 

---

다른 사람 코드 학습

def solution(s):
    from collections import Counter

    temps = [i.replace('{', '').replace('}', '') for i in s.split(',')]
    return [int(temp[0]) for temp in sorted(Counter(temps).items(), key=lambda x: x[1], reverse=True)]

 

for i in s.split(',')를 사용해서 for문을 ','을 기준으로 잘라서 돌릴 수 있음을 알았다. 

그리고 숫자 이외의 문자들을 모두 제거(replace())한 다음 리스트에서 숫자가 가장 많은 순으로 출력하면 된다. 

저렇게 하는 방법 보고 나는 아직 더 학습을 해야 함을 느꼈다ㅠㅠ

 

 

 

---

문제 출처

코딩테스트 연습 - 튜플