수학과의 개발자 도전기

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

문제 이해 

- 문제를 이해하는데는 그렇게 어렵지 않은데, 시간초과가 발생했어서 좀 어려웠던 문제다.

- 첫번째 문자열과 두번째 문자열이 주어지는데, 두번째 문자열이 첫번째 문자열에서 없어질 때까지 반복한 뒤 남은 문자열을 출력하는 문제다. 

- 처음에는 문자열 인덱싱으로 풀어보려했으나, 그러면 문자열 탐색이 계속 진행돼서 시간초과가 발생했다.

- 해결책은 스택을 이용하는 것인데, 정답을 출력하는 stack을 만들어 놓고, 오른쪽 끝에서 두번째 문자열 길이(n)의 문자열이 두번째 문자열과 동일하다면 stack에서 n번만큼 pop을 하는 방법이다. 

- 스택으로 풀어야 한다고 해서 첫번째 문자열에 stack을 사용한다고 생각했는데, 정답으로 출력한 배열을 stack으로 진행하면 되는 것을 배운 문제다. 

정답 풀이 

string = input()
target = input()
n = len(target)

stack = []

for i in range(len(string)):
    stack.append(string[i])
    if ''.join(stack[-n:]) == target:
        for _ in range(n):
            stack.pop()
            
if stack:
    print(''.join(stack))
else:
    print('FRULA')

- 문제 : 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.')