수학과의 개발자 도전기

- 문제 : https://www.acmicpc.net/problem/2179

문제 이해 

- 문제 자체는 이해하기 어렵지 않았던 것 같다. 주어진 단어들 중에서 두 개의 단어의 접두사가 가장 긴 케이스를 찾고, 해당 단어 두 개를 출력하는 문제다. 

- 처음에는 3중 for문으로 일일히 가장 긴 접두사 찾고, 또 그거에 해당되는 단어들을 모두 찾았는데 그렇게 하니 메모리 초과가 발생했다. 

- 그래서 해시보다는 문자의 인덱스와 인덱스에 해당하는 최대 접두사 길이를 1차 배열에 저장해서 진행하면 된다.

풀이 로직

- enumerate를 이용해 입력된 단어들을 사전순으로 정렬하고, 인덱스도 같이 저장해준다. (인덱스, 단어) -> (1, 'for')

- 정렬된 단어를 순차 진행하면서 바로 옆에 있는 단어와 한글자씩 비교해 가면서 접두사의 길이가 최대인 경우를 찾는다.

   이때 접두사의 길이를 인덱스로 가지는 length 배열을 이용한다. (예시: length[3]은 인덱스 3 문자의 최대 접두사 길이를 의미한다)

- 접두사의 길이가 최대(max(length))이면서 가장 먼저 입력된 단어를 출력한다. 

  총 두 개의 문자열을 출력해야하는데, 첫번째 단어와 두번째 단어 구별은 first 변수로하고, 두번째 단어를 찾았을 때 첫번째 단어와 같은 접두사인지 확인하기 위해 pre 변수를 이용한다.

- 그래서 first == 0 인 경우는 첫번째 단어이므로, 바로 출력해주고, first와 pre를 출력한다.

- 두번째 단어는 first !=0 인 경우이고, 이때 최대 접두사의 길이를 가지고, 접두사가 일치할 때 해당 문자를 출력하고 끝내면 된다.

정답 풀이 

n = int(input())
a = [input() for _ in range(n)]

b = sorted(list(enumerate(a)), key = lambda x : x[1])

def check(a, b):
    count = 0
    for i in range(min(len(a), len(b))):
        if a[i] == b[i]:
            count += 1
        else:
            break
    return count

length = [0] * (n + 1)
max_length = 0

for i in range(n - 1):
    temp = check(b[i][1], b[i + 1][1])
    max_length = max(max_length, temp)
    
    length[b[i][0]] = max(length[b[i][0]], temp)
    length[b[i + 1][0]] = max(length[b[i + 1][0]], temp)
    
first = 0
for i in range(n):
    if first == 0:
        if length[i] == max(length):
            first = a[i]
            print(first)
            pre = a[i][:max_length]
    else:
        if length[i] == max(length) and a[i][:max_length] == pre:
            print(a[i])
            break

참고한 블로그 : https://lazypazy.tistory.com/26

- 문제 : https://www.acmicpc.net/problem/20437

문제 이해 

- 각 케이스마다 문자열과 숫자 k가 주어진다. 숫자 k는 부분 문자열에 하나의 문자가 k개 이상은 있어야 한다는 것을 의미한다. 

- 처음에 문제가 이해가 안되기도 했지만, 알파벳 종류에 상관없이 그럼 모든 문자에 대해서 모든 부분 문자열에 대해 k개 이상이 있는지 확인해야하는 건가? 싶은 생각이 들었다. 그렇다면 케이스가 너무 많아지고, 복잡해질 것 같았다. 

- 그래서 풀이를 확인했는데 브루트포스처럼 하지 않고 1) 각 알파벳의 개수를 구한 다음 2) 그 알파벳의 인덱스를 구한 뒤 3) 인덱스 간의 차이 중 최소값과 최대값을 구하면 된다. 

- 정답률이 꽤 높았던 골드5 문제이지만, 아직 문자열은 좀 어려운 것 같다,, 익숙해지기까지 시간이 좀 걸릴 듯 하다.

풀이 로직 

- 각 케이스마다 단어 w와 숫자 k를 입력 받는다. 

- Counter 라이브러리로 단어에 있는 알파벳의 개수를 count_char_dict 딕셔너리에 저장한다. (예시 : {'a' : 2, 'b' : 0,,,})

- check는 정답 확인용, max_answer는 조건을 만족하는 최대 문자열 길이, min_answer는 조건을 만족하는 최소 문자열 길이다.

  check_dict는 특정 문자의 index를 저장하는 딕셔너리이다.

- 단어 w를 순차적으로 탐색하면서 각 알파벳의 개수가 k개 미만이면 넘어가고, k개 이상인 경우만 check_dict에 {알파벳 : [인덱스1, 인덱스2,,,,]} 형태로 데이터를 저장한다. 

- check_dict를 다 완성했다면 각 item을 탐색하면서 key(알파벳, 문자 1개)가 k개일 때의 문자열 길이의 최대값을 max_answer, 최소값을 min_answer에 저장한다. 

-> 예를들어 value_list는 알파벳 'a'의 위치 값들이다. [1, 3, 5, 10,,] 그런데 연속된 문자열에서 알파벳 'a'가 k개 있어야 하므로 value_list에서 연속된 인덱스가 k개 만큼 필요하다. 그래서 value_list[i + k - 1] - value_list[i]이고, 문자열의 길이이므로 인덱스 차이값에 + 1을 해준다.

for key, value_list in check_dict.items(): # key(알파벳), value_list(인덱스 리스트)
    for i in range(len(value_list) - k + 1):
        max_answer = max(max_answer, value_list[i + k - 1] - value_list[i] + 1)
        min_answer = min(min_answer, value_list[i + k - 1] - value_list[i] + 1)

정답 풀이

from collections import Counter
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    w = input().rstrip()
    k = int(input())
    
    count_char_dict = Counter(list(w))
    
    check = False
    max_answer = -1
    min_answer = len(w)
    check_dict = {} # 특정 문자열의 index를 저장하는 딕셔너리 
    
    for i in range(len(w)):
        if count_char_dict[w[i]] < k:
            continue
            
        check = True
        check_dict[w[i]] = check_dict.get(w[i], []) + [i]
        
    for key, value_list in check_dict.items(): # 알파벳, 인덱스 리스트 
        for i in range(len(value_list) - k + 1):
            max_answer = max(max_answer, value_list[i + k - 1] - value_list[i] + 1)
            min_answer = min(min_answer, value_list[i + k - 1] - value_list[i] + 1)
            
    if check :
        print(min_answer, max_answer) 
    else:
        print(-1)

참고한 블로그 : Python백준-문자열-게임-2

- 문제 : https://www.acmicpc.net/problem/4659

문제 이해 

- 주어지는 각 단어마다 성공적인 비밀번호를 작성하는 방법에 맞는 경우는 acceptable, 맞지 않는 경우는 not acceptable을 출력하는 문제다.

- 생각보다 비밀번호 작성 조건이 많아서 그거를 맞추는 코드를 작성하는데 시간이 좀 들었던 문제다. 

- 각 비밀번호 조건은 다음과 같다.

  1. 모음(a, e, i, o, u)이 하나 이상 포함되어 있을 것

  2. 3개 이상의 자음 또는 모음이 연속적으로 있으면 안됨 (abc, oui 등)

  3. 같은 문자 2개 이상이 연속되면 안됨. 단, ee, oo는 가능함

- 정규 표현식 같은 걸로 간편하게 할 수 없을까 찾아봤는데 딱 맞는 거는 없었다. 결국 노가다로 일일히 하나씩 체크하는 방식으로 하니 정답이 떴던 문제다. 

풀이 로직 

- 각 비밀번호 조건에 맞는 로직을 작성해야하는데, 각 조건마다 일반 탐색으로 풀었다. 

  1. 모음(a, e, i, o, u)이 하나 이상 포함되어 있을 것 -> vowels 배열을 만들어 vowles의 원소 중 몇 개가 단어에 포함되어있는지 count로 확인한다. 만약 count == 0 이라면 모음이 없는 것이므로 실패 처리한다.

  2. 같은 문자 2개 이상이 연속되면 안됨. 

  -> 모음의 경우 : 모음을 탐색하면서 같은 모음 2개를 붙인 단어가 입력된 단어(word)에 있다면, 또 그 문자가 e 또는 o가 아니라면 실패 처리(flag = False)

  -> 자음의 경우 : 자음을 탐색하면서 같은 자음 2개를 분인 뒤 입력된 단어(word)에 있는지 확인하고, 있다면 실패 처리한다. 

  3. 같은 종류의 문자가 연속으로 3개 있는 경우는 주어진 단어(word)를 세 개씩 순차적으로 탐색한 다음 그 세 개의 문자가 모두 같은 vowels 또는 consonant에 포함된다면 실패한 경우이므로 flag = False를 한 뒤 반복문을 break 한다. 

- 위 과정에서 걸렸다면 실패 케이스이므로 바로 문장을 출력하면 되지만, 만약 위의 경우에 하나도 안 걸렸다면 성공 케이스이므로 성공 문장을 출력한다. 

정답 풀이

vowels = ['a', 'e', 'i', 'o', 'u']
consonant = ['b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 'y', 'z']

while True:
    word = input()
    
    if word == 'end':
        break
        
    arr = list(word)
    count = 0
    flag = True
    # 모음 없는 경우와 oo/ee 가 아닌 모음이 두 개 연속되는 단어 있는지 확인
    for vowel in vowels:
        if vowel in arr:
            count += 1
        two = vowel + vowel
        if two in word:
            if two != 'oo' and two != 'ee':
                flag = False
    
    if count == 0 or not flag:
        print('<' + word + '>' + ' is not acceptable.')
        continue

    # 같은 자음 연속으로 두 개 있는지 확인
    for each in consonant:
        if each + each in word:
            flag = False
            print('<' + word + '>' + ' is not acceptable.')
            break
            
    # 연속된 세 알파벳이 모두 자음에 포함되거나 모두 모음에 포함되는 경우 있는지 확인         
    for i in range(0, len(arr) - 2):
        first, second, third = arr[i], arr[i + 1], arr[i + 2]
        if first in vowels and second in vowels and third in vowels:
            flag = False
            print('<' + word + '>' + ' is not acceptable.')
            break
        if first in consonant and second in consonant and third in consonant:
            flag = False
            print('<' + word + '>' + ' is not acceptable.')
            break
            
    if flag : 
        print('<' + word + '>' + ' is acceptable.')

- 문제 : https://www.acmicpc.net/problem/9996

문제 이해 

- 중간에 ' * '가 하나 있는 문자열이 주이고, 시작  ~  '*'전, '*'후 ~ 끝의 문자가 같은 문자는 DA, 다른 문자는 NE를 출력하는 문제다. 

- 일단 스타(*)를 기준으로 first, second를 나눈다. 그 후 입력되는 글자의 앞부분은 first와 비교, 뒷부분은 second와 비교해서 두 개 모두 같다면 DA를 출력하고, 아니라면 NE를 출력하면 된다.

- 어렵지 않은 문제였지만, 25%에서 계속 틀리길래 무엇때문인지 몰라서 찾아봤다. 그런데 a*a인 키워드가 주어졌을 때 a인 경우는 틀린 경우지만, 따로 거르지 않으면 맞는 경우로 출력될 수 있어서 이 부분에 유의해서 진행했어야 했다. 

그래서 주어진 키워드의 문자부분보다 짧은 문자열은 실패 처리하는 로직을 추가하면 된다.

    # 키워드는 a*a인데 단어는 a인 경우를 거르기 위해서
    if first_length + second_length > length:
        print('NE')
        continue

정답 풀이 

n = int(input())
arr = input().rstrip().split('*')
first_length = len(arr[0])
second_length = len(arr[1])

for _ in range(n):
    word = input().rstrip()
    length = len(list(word))
    
    # 키워드는 a*a인데 단어는 a인 경우를 거르기 위해서
    if first_length + second_length > length:
        print('NE')
        continue
    
    if arr[0] == word[:first_length] and arr[1] == word[length - second_length : ]:
        print('DA')
    else:
        print('NE')