구름톤 챌린지 Week 2 - Day 6

한 줄 요약: 나아진 부분은 있지만, 심해진 부분도 있다.

 

'완전 탐색'을 주제로 한 2주차 구름톤 챌린지가 끝이 났다.

이번 다섯 문제는 각각 "문자열 나누기", "구름 찾기 깃발", "통증", 폭탄 구현하기 (2)", "GameJam"이란 이름을 갖고 있다.

문자열 나누기, 구름 찾기 깃발, 폭탄 구현하기는 문제를 풀 때 필요한 재미가 충분히 충족했다고 생각한다.

 

재밌다고 표현한 것은 단순히 쉬운 문제라는 뜻이 아니다.

문제를 해석하고 구현하고 해결하는 과정에 있어서, 다양한 효과적인 방법을 찾을 수 있다는 것이다.

같은 완전 탐색이라도 누군가는 아래에서부터, 누군가는 위에서부터 문제를 풀어갈 수 있다.

누구는 index를 사용할 수도, 혹은 다른 조건문을 활용하여 풀어갈 수 있다.

같은 측면에서 이 문제 해설에 대해서도 상당히 구체적으로, 효율적으로 작성하여 만족스러웠다.

완전 탐색이라는 주제에 걸맞는 문제였으며, 모르는 사람이 있었다면 새롭게 공부할 수 있는 개념이 다수 존재했다.

조합이라든가, dxy를 활용한 계산이라든가 말이다.

 

하지만 통증과 GameJam 문제에 대해서는 정말 실망스러웠다.

솔직히 이게 뭐지? 싶은 생각이 들었다. 특히 통증 문제에서 그 느낌은 극에 달했다.

우선 완전 탐색이라는 문제 취지에 어긋난다.

통증 문제 설명에도 대놓고 박혀있다. "해당 문제는 그리디의 기초가 되는 문제입니다."

GameJam도 마찬가지다. "해당 문제는 시뮬레이션 문제로, (중략) 구현해야 합니다."

 

통증은 그리디 문제 중에서도 완전 기초 중의 기초 문제이다.

그러니까 수능으로 따지면 수학 (나)형 1번 문제 같은 느낌이다.

이 문제를 내고 싶었다면, 그리디와 완전 탐색을 섞은 형태의 뉘앙스라도 했어야 했다. 

자세한 사항은, 해당 문제 해설 작성 시 이야기하겠다.

 

GameJam도 해당 문제 해설을 작성할 때, 적겠지만 출제에서 상당히 많은 실수가 있었다.

문제 해설을 적는 현재(20230825, 18:30)를 기준, 참여자 178명 좋아요 11개 싫어요 54개가 있다.

물론 이 수치가 절대적인 척도를 나타내지 않는다. 하지만 사람들의 생각 여부는 충분히 판단할수 있다. 

GameJam은 출제 실수를 제외하고 문제 자체는 훌륭한 구현 문제라고 생각한다.

그럼 진작에 이 문제를 구현 주차에 넣었으면 됐지 왜 여기다 넣었는지 이해할 수 없다.

대체 왜.

설마 문제를 그날그날 만든다거나 그런 건 아니겠지?

 

https://level.goorm.io/exam/195688/문자열-나누기/quiz/1

어떤 문자열 S가 있다고 할 때, 부분 문자열 3개로 나누는 모든 경우를 탐색하는 문제다.

나눈 부분 문자열들은 특정 방식에 따라 채점하는데, 이때 가장 높은 점수를 묻는 문제다.

 

from itertools import combinations
result = 0

length = int(input())
text = input()

sub_str = sorted(set(text[i:i+L]
              for L in range(1, len(text)-2+1)
              for i in range(len(text)-L+1)))

for line1, line2 in combinations([i for i in range(1, length)], 2):
    fir = sub_str.index(text[:line1]) + 1
    sec = sub_str.index(text[line1:line2]) + 1
    thi = sub_str.index(text[line2:]) + 1
    
    result = max(result, fir + sec + thi)
    
print(result)

최대한 깔끔하게 코드를 작성하려고 노력했다. 

이 문제를 해결하기 위해서는 파이썬 조합 라이브러리, combinations을 알아야 한다.

그리고 약간의 아이디어가 필요하다.

부분 문자열은 어떻게 나눌 것인지? 채점하는 특정 방식은 어떻게 구현할 것인지? 

 

from itertools import combinations

우선 파이썬에서 자주 사용하는 라이브러리, itertools와 collections가 있다.

그중 itertools는 말그대로 iter(순회 가능한)에 대한 라이브러리이다.

순회 가능한 객체에 대해 지원하는 count, zip_longest, pairwise 등이 있고,

내부 요소들을 순회하는 permutations, combinations, product 등이 있다.

그 중 combinations을 사용하면 쉽게 풀 수 있는 문제이다.

 

수학 시간 때, 순열 조합 등에 대해서 배운 기억이 있을 것이다.

combinations은 말그대로 조합을 뜻하며, 서로 다른 N개에서 순서에 상관없이 R개를 고르는 것이다.

순서에 상관없다는 말이 중요하다.

 

예를 들어 [1, 2, 3]이라는 list에서 2개씩 순서에 상관없이 골라보자.

(1, 2), (1, 3), (2, 3)으로 3개가 나올 것이다.

순서를 고려한다면? (1, 2)와 (2, 1)은 다르므로 6개가 나올 것이다.

보다시피 combinations을 사용하기 위해서는, 나눌 객체와 나눌 숫자가 필요하다.

그래서 combinations(*iterable, *num)의 형태로 사용한다.

 

length = int(input())
text = input()

sub_str = sorted(set(text[i:i+L]
              for L in range(1, len(text)-2+1)
              for i in range(len(text)-L+1)))

우선 채점하는 특정 방식에 대해 구현하기로 했다.

부분 문자열을 모두 나누어 중복하지 않고, 사전 순으로 나열해야 한다.

그래서 생각한 것이 set()이다.

set()은 순서가 존재하지 않아(unordered), 마지막에 sorted()로 정렬해야 한다.

sorted()의 return 값은 list이기 때문에 set()을 굳이 list()로 감싸지 않아도 괜찮다.

 

아이디어는 이렇다. 3개의 부분 문자열로 이루어진다고 하면, 가장 긴 경우는 뭘까?

1개짜리, 1개짜리, 나머지 전부. 그러니까 가장 긴 부분 문자열은 Length - 2다. (for L in range(1, len(text)-2+1))

예를 들어 1글자면 처음부터 끝까지, 2글자면 처음부터 한 칸 앞까지 탐색을 해야 겠네? (for i in range(len(text)-L+1))

그럼 탐색하면서 i부터 L 길이만큼 문자열을 자르면 되겠다. (text[i:i+L])

그런 다음 중복을 없애기 위해 set에 넣고 정렬하면 끝이네. (sorted(set()))

이 과정을 거치면 모든 부분 문자열을 중복 없이 사전 순으로 정렬한 sub_str을 얻는다.

 

result = 0

for line1, line2 in combinations([i for i in range(1, length)], 2):
    fir = sub_str.index(text[:line1]) + 1
    sec = sub_str.index(text[line1:line2]) + 1
    thi = sub_str.index(text[line2:]) + 1
    
    result = max(result, fir + sec + thi)

 

모든 부분 문자열을 구했으니, 3개의 부분 문자열로 나눌 차례다.

이 친구도 잘 생각해보자. 3개의 부분 문자열로 나눈다는 것은 2개의 기준이 있다는 것이다.

이 2개의 기준은 combinations을 사용하여 추출할 수 있다.

가장 처음이 0과, 가장 마지막은 안 된다. 고로 1부터  length까지 범위에서 2개를 얻으면 된다.

 

이렇게 얻은 line1과 line2를 사용하여 문자열을 자른다.

[:line1], [line1:line2], [line2]로 자르면 된다.

처음부터 혹은 끝까지 자를 때는 굳이 index를 적지 않아도 상관없다.

자른 문자열의 점수를 구한 뒤 각각 더해주고 비교하면, 최댓값 탐색이 끝난다.