수학과의 개발자 도전기

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

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

문제 이해 

- 처음 n개의 문자열을 메모장에 저장한 뒤 다음 m개의 문장이 주어지는데, 이때 메모장에 해당하는 단어들을 제거한 뒤 그때그때마다 메모장에 남은 단어 개수를 출력하는 문제다. 

- 메모장에 저장하는 단어들은 딕셔너리에 추가한 뒤 m개의 문장을 탐색하면서 아직 제거되지 않은 단어의 개수를 -1 하고, 케이스마다 메모장의 개수를 출력하면 되는 문제다. 

- 어렵지 않아서 코드를 작성했는데 계속 4%에서 틀렸다. 그래서 무엇이 문제인고 하니 입력 받는 단어들 중에 공백이 같이 주어지는게 있는데 그거를 제거하지 않아서 문제가 발생한 것 같다. 

문자열에서 공백 제거하는 방법은 .rstrip()을 이용하기!

word = input().rstrip()
temp = list(input().rstrip().split(','))

풀이 로직 

- n개의 단어를 words라는 딕셔너리에 추가한다. 메모장의 전체 개수는 total에 저장한다.

- 다음 m개의 문장들을 하나씩 입력받은 뒤 문장에서 ' , '로 단어들을 분리해 탐색한다.

- 각 단어가 words에 있고, 개수가 1개라면, 전체 개수를 하나 빼고, 메모장에서도 단어를 제거한다.(words[each] = 0)

- 각 문장마다 메모장에 있는 단어 개수(total)를 출력하면 된다.

정답 풀이 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

words = {}
total = n
for _ in range(n):
    word = input().rstrip()
    words[word] = 1
    
for _ in range(m):
    temp = list(input().rstrip().split(','))
    for each in temp:
        if each in words.keys():
            if words[each] > 0:
                total -= 1
                words[each] = 0
                    
    print(total)

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

문제 이해 

- 주어진 영어 단어를 대칭을 이루는 팰린드롬으로 만들 수 있는지 확인하는 문제다.

- 만들 수 있다면 사전 순으로 가장 먼저인 문자를 출력하고, 못 만든다면 'I'm Sorry Hansoo'를 출력하면된다.

- 어떻게 대칭인 단어를 만들 수 있을까 생각하다가 먼저 단어를 입력 받은 뒤 각 알파벳과 알파벳의 개수를 딕셔너리에 저장한다. 

- 딕셔너리를 순차적으로 진행하면서 first와 second 배열에 알파벳들을 append 한다.

(대칭을 이뤄야 하므로 first와 second에 하나의 알파벳을 하나씩 넣어주고 마지막에 합치면 대칭인 단어를 만들 수 있다)

- 이때 second는 그냥 순차적으로 first처럼 append를 해주고 마지막에 출력할 때만 뒤집어서 출력하면 된다.

- 좀 더 생각해 봐야할 부분은 한 알파벳의 개수가 홀수이거나 팰린드롬을 만들지 못하는 경우이다.

  1. 한 알파벳의 개수가 홀수인 경우는 하나만 나오면 괜찮지만, 알파벳 하나만 따로 저장(middle)한 뒤 마지막에 추가해 주면 된다.

  2. 만약 홀수 개수인 알파벳이 2개 이상이 된다면 그 즉시 팰린드롬을 만들지 못하기 때문에 바로 실패 케이스로 가야한다. 

풀이 로직

- 단어를 입력받아 리스트로 바꾼 뒤 정렬한다. (사전순으로 가장 먼저인 단어를 만들어야하기 때문)

- 단어의 리스트에 있는 알파벳의 개수를 세기 위해 Counter 라이브러리를 이용한다.

- 각 변수들을 초기화하는데, 목적은 다음과 같다.

  first : 왼쪽에 놓을 단어를 추가하는 배열

  second : 오른쪽에 놓을 단어를 추가하는 배열

  flag : 알파벳 개수가 홀수인 게 1개인 것을 확인하는 변수

  check :  팰린드롬 성공/실패 여부를 확인하는 변수

  middle : 홀수 개인 알파벳을 가운데 놓기 위해 따로 저장하는 변수

- 주어진 단어 배열을 탐색하면서 각 알파벳의 개수가 홀수인 경우와 짝수인 경우로 나눠서 진행한다.

  1. 홀수인 경우는 이전에 개수가 홀수인 알파벳이 없었는지 확인하고, 중간에 넣을 middle을 갱신한 뒤 flag를 False로 바꾼다. 

     개수도 하나 줄인 뒤 반복문을 통해 왼쪽과 오른쪽에 넣을 알파벳을 하나씩 넣는다.

  2. 만약 알파벳 개수가 홀수인데 이전에 이미 같은 유형의 알파벳이 있었다면 팰린드롬을 만들지 못하므로 반복문을 바로 break한다.

  3. 짝수인 경우에는 별도의 과정없이 반복문을 통해 왼쪽과 오른쪽에 알파벳을 하나씩 넣어주면 된다.

- check가 False인 경우는 바로 팰린드롬이 실패한 것이므로 실패 문장을 출력한다. 아니라면 first 끝에 middle을 추가한 뒤 first는 순서대로, second는 역순으로 붙여서 출력한다.

정답 풀이 

from collections import Counter

words = list(input())
words.sort()
words_dic = Counter(words)

first, second = [], []
flag = True
check = True
middle = ''
for each in words_dic.keys():
    
    if words_dic[each] % 2 == 1:
        if flag:
            middle = each
            flag = False
            words_dic[each] -= 1
            while words_dic[each] > 0:
                first.append(each)
                second.append(each)
                words_dic[each] -= 2
        else:
            check = False
            break
                
    else:
        while words_dic[each] > 0:
            first.append(each)
            second.append(each)
            words_dic[each] -= 2
            
           
           
if not check:
    print("I'm Sorry Hansoo")
else:
    first.append(middle)
    print(''.join(first) + ''.join(second[-1::-1]))

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

문제 이해 

- 단어 구성이 첫 번째 단어와 완전히 일치하거나 아니면 하나씩만 차이나는 단어의 개수를 반환하는 문제다.

- 딕셔너리를 이용해 첫 번째 단어와의 각 알파벳 개수 차이를 구한 뒤 딕셔너리 값이 0, 1, -1인 알파벳의 정보를 기록한다.

  1. 만약 딕셔너리 값이 모두 0이라면 두 단어의 구성이 일치(알파벳 종류, 개수)하는 것이므로 바로 정답 케이스에 포함된다.

  2. 여기서 주의해야하는데, 딕셔너리 값이 -1, 1인 알파벳의 개수를 세는데 각 숫자(1, -1) 합이 2개 이하이거나 각 숫자 값이 2이하인 경우도 연산 한번(알파벳 바꾸기 or 빼기 or 추가하기)을 통해서 첫 번째 단어로 바꿀 수 있으므로 정답 케이스에 포함된다.

- 풀이에서는 위 2번의 케이스를 만족하지 않는 것들을 거르는 방식으로 진행했다. 1번까지는 생각했는데 2번 케이스가 잘 되지 않아서 꽤 헤맸던 문제다. 

- 추가로 주의해야할 것은 첫 번째 단어와의 길이 차이가 2 이상이 나는 경우는 답이 될 수 없으므로 바로 넘겨줘야 한다. 

풀이 로직

- 입력 값 중에 첫번째 값은 따로 first, first_length, dic으로 입력 받는다

- 나머지 n - 1 개의 입력값을 받은 후, 단어의 길이(length)와 단어 구성을 딕셔너리(temp)에 저장한다.

- 길이 차이가 2 이상인 경우는 그냥 넘어가도록 한다. 

if first_length > length + 1 or first_length < length - 1:
        continue

- 두 단어의 딕셔너리를 subtract 해준 뒤 결과를 temp에 저장한다. (temp.subtrac(dic)하면 temp에 결과가 저장된다)

  이제 temp는 {'A' : 0, 'B': -1, ,,,}의 형태를 띤다 

- temp를 탐색하면서 값이 0, 1, -1인 key의 개수를 zero, one, minus_one에 저장한다. 이렇게 저장한 변수값으로 정답여부를 판별할 것이다.

- 만약 0, -1, 1 이 아닌 다른 값이 딕셔너리에 존재한다면 조건을 만족하지 않는 단어이므로 flag = False 처리를 해준 뒤 탐색을 break 한다.

    temp.subtract(dic)
    zero, one, minus_one = 0, 0, 0
    flag = True
    for each in temp.keys():
        # 다 0으로 이루어져 있거나, 나머지 0이고, 1이나 -1이 하나만 있으면 정답
        if temp[each] == 0:
            zero += 1
        elif temp[each] == 1:
            one += 1
        elif temp[each] == -1:
            minus_one += 1
        else:
            flag = False
            break

- 탐색이 끝난 후에는 one과 minus_one 변수 값을 기준으로 만족하지 않는 경우에 flag = False 처리를 한다.

    if one + minus_one > 2:
        flag = False
    if one > 2 or minus_one > 2:
        flag = False

- flag == True인 경우에만 개수를 센 후 마지막에 출력 해주면 된다.

    if flag :
        answer += 1

정답 풀이 

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

n = int(input())
first = input()
first_length = len(first)
dic = Counter(first) # 첫 번째 단어 구성

answer = 0
for _ in range(n - 1):
    name = input()
    length = len(name)
    temp = Counter(name)
    
    if first_length > length + 1 or first_length < length - 1:
        continue
    
    temp.subtract(dic)
    zero, one, minus_one = 0, 0, 0
    flag = True
    for each in temp.keys():
        # 다 0으로 이루어져 있거나, 나머지 0이고, 1이나 -1이 하나만 있으면 정답
        if temp[each] == 0:
            zero += 1
        elif temp[each] == 1:
            one += 1
        elif temp[each] == -1:
            minus_one += 1
        else:
            flag = False
            break
            
    if one + minus_one > 2:
        flag = False
    if one > 2 or minus_one > 2:
        flag = False
        
    if flag :
        answer += 1
        
print(answer)

- 참고한 블로그 : 백준 2608 비슷한 단어 - 파이썬