🏄‍♀️ 코딩테스트/🐍 Python

[ 백준 20437 해설 ] ( python ) 문자열 게임 2

Po_tta_tt0 2022. 9. 7. 10:06
반응형

 

📚 문자열 게임 2

 

 

문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

  1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
  2. 양의 정수 K가 주어진다.
  3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
  4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

 

입력

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)

다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000) 

 

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

 

예제 입력 1 복사

2
superaquatornado
2
abcdefghijklmnopqrstuvwxyz
5

예제 출력 1 복사

4 8
-1

첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다.

두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다.

예제 입력 2 복사

1
abaaaba
3

예제 출력 2 복사

3 4

 

 

✍ 접근

  • 문제 : 양쪽이 포함되는 for문 잘 돌려? dict 잘 쓸줄 알아?
  • 라고 물어보는 듯한 문제였다
  • 처음에는 간단하게 생각하고 for문 안에 cnt,length를 넣고 그 안에 다시 for문을 돌리면서 길이를 계산하려고 했는데, 예제 2번을 생각하지 못한 코드여서 바로실패

 

 

 

 

 

정답코드 

# ✨ 입력
import sys
input = sys.stdin.readline
T = int(input())

for _ in range(T):
    word = input().rstrip()
    K = int(input())
    set_word = list(set(word))
    
    dict = {}
    g3 = 2147000000
    g4 = -2147000000
    
    # ✨ dict에 위치 배열로 저장하기
    for i in range(len(set_word)):
        if word.count(set_word[i])>=K:
            dict[set_word[i]] = []
            for j in range(len(word)):
                if set_word[i] == word[j]:
                    dict[set_word[i]].append(j)
    if dict == {}:
        print(-1)
        continue
        
    # ✨ 가장 긴 길이 / 짧은 길이 계산하기
    for w,pos in dict.items():
        for i in range(len(pos)-K+1):
            length = pos[i+K-1]-pos[i]+1
            g3 = min(g3,length)
            g4 = max(g4,length)
            
            
    print(g3,g4)

해설

입력

  • 문제에서 나온 값을 입력받는다

dict에 위치 배열로 저장하기

  • 중복을 제거한 문자열을 상위 for문,
    • 만약 문자가 원래 문자열 안에 K개 이상 존재한다면(필수조건을 충족한다면)
    • dict에 배열을 만들어준다
  • 원래 문자열을 하위 for문으로 돌린다
    • 중복을 제거한 문자와 원래 문자열을 비교하면서
      두 문자가 같으면
    • dict에 만들어둔 배열에 append해준다
  • 만약 dict가 비어있으면 (필수조건을 충족하지 못했으면)
    더 볼 필요도 없이 -1을 출력하고 다음 Test로 넘어간다

가장 긴 길이 / 짧은 길이 계산하기

  • dict에서 items를 꺼내와 (사실 value만 꺼내와도 된다 다시 보니 보이네 💦)
  • 안에 for문을 len(pos) == value값 -K(최소 문자의 개수) + 1 
    • 문제에서 말하는 문자 2개 == 첫 문자와 마지막 문자가 포함되어 2개라는 말
    • 따라서 첫 문자와 마지막 문자를 포함시켜주고
    • length에도 1을 더해줘야 한다 (5-3 == 2로 만약 5와 3이 다 포함되었다면 5-3+1 == 3을 해줘야 하니까)

 

 

 

⭐ 배움

  • 문자열.. 언제 손에 익을까?
반응형
저작자표시