[Python] 백준 코테 연습 - 문자열

 

문제 참고한 사이트

https://codingdodo.tistory.com/94

백준 코딩테스트 초보 추천 문제 모음(브론즈~골드3)

 

 

---

복호화 - 브론즈2

 

https://www.acmicpc.net/problem/9046

original_text = "abcdefghijklmnopqrstuvwxyz"
encoding_text = "wghuvijxpqrstacdebfklmnoyz"

for i in range(int(input())):
    text = str(input()).replace(' ', '')
    num = 0
    word = ''
    for j in range(len(encoding_text)):
        if text.count(encoding_text[j]) > num:
            word = encoding_text[j]
            num = text.count(encoding_text[j])
        elif text.count(encoding_text[j]) == num:
            word = '?'

    print(word)

 

 

---

수 이어 쓰기 - 실버 2

 

https://www.acmicpc.net/problem/1515

n = input()
ans = 0 
while True:
    ans += 1  # 1씩 증가하면서 input()과 비교, 앞부터 순서대로 비교한다.
    num = str(ans)  # 문자열로 반환 후 비교
    while len(num) > 0 and len(n) > 0:  
        if num[0] == n[0]:  # 문자 앞 자리와 비교 숫자 앞자리가 일치하는 경우
            n = n[1:]  # 문자 앞자리 지우기
        num = num[1:]  # 비교할 숫자 앞자리 지우기
    if n == '':  # 전부 지워진 경우
        print(ans)
        break

• 두자리 이상의 숫자를 작성했을때, 그 중 하나의 숫자만 지울 수도 있다.
• 숫자를 늘려가면서 앞부터 비교해야 한다.

---

파일 정리 - 실버 3

 

https://www.acmicpc.net/problem/20291

n = int(input())
ans = {}
for _ in range(n):
    file = str(input()).split('.')[-1]
    if file in ans:
        ans[file] +=1
    else:
        ans[file] = 1
        
ans = dict(sorted(ans.items()))

for key in ans:
    print(key, ans[key])

 

---

단어 뒤집기 - 실버 2

 

https://www.acmicpc.net/problem/17413

S = str(input())
start = 0
end = 0

for i in range(len(S)):
    if S[i]=='<':
        end = i
        if end > 0 and start > 0:
            reverse_text = S[start+1:end].split(' ')
            text = ''

            for i in range(len(reverse_text)):
                reverse_text[i] = reverse_text[i][::-1]
                text += reverse_text[i]+' '

            S = S[:start+1]+text.rstrip()+S[end:]
        elif end > 0 and start == 0:
            reverse_text = S[start:end].split(' ')
            text = ''

            for i in range(len(reverse_text)):
                reverse_text[i] = reverse_text[i][::-1]
                text += reverse_text[i]+' '

            S = S[:start]+text.rstrip()+S[end:]
    elif S[i]=='>':
        start = i

if len(S) >= end-1:
    if start != 0:
        start += 1
    reverse_text = S[start:].split(' ')
    text = ''

    for i in range(len(reverse_text)):
        reverse_text[i] = reverse_text[i][::-1]
        text += reverse_text[i]+' '

    S = S[:start]+text.rstrip()
      
print(S)

• 추가 반례 : abc<tag>
• <> 의 여부 및 위치에 따라 if문으로 나누어서 작성. 비효율적
• stack을 이용한 방식
• https://edder773.tistory.com/86

[백준 17413] 단어 뒤집기 2 (python)

import sys
S = sys.stdin.readline().strip() + ' ' # 마지막에 공백을 더해주자
stack = [] # 저장해줄 스택
result = '' # 결과물 출력
cnt = 0 # 괄호 안에 있는지 여부
for i in S : # 받은 문자열 찾아보자
    if i == '<' : # <를 만나면
        cnt = 1 # 지금 괄호 안에 있음 표시
        for _ in range(len(stack)): #괄호 만나기 이전 stack 애들 비워주고 다 뒤집어서 더해!
            result += stack.pop()
    stack.append(i)
    
    if i == '>' : # >를 만나면
        cnt = 0 # 지금 괄호 빠져 나왔음 표시
        for _ in range(len(stack)): # 괄호 안에 있는 애들은 뒤집지 말고 더해!
            result += stack.pop(0)

    if i == ' ' and cnt == 0: # 공백을 만나고 괄호 밖에 있다면
        stack.pop() # 들어간 공백 뺴주고
        for _ in range(len(stack)): # 뒤집어서 더해!
            result += stack.pop()
        result += ' ' # 마지막에 공백 살려주기
print(result)
출처: https://edder773.tistory.com/86 [개발하는 차리의 학습 일기:티스토리]

 

 

---

문자열 교환 - 실버 1

https://www.acmicpc.net/problem/1522

S = input()
a = S.count('a')  # a의 갯수

S += S[0:a-1]  # 원형 문자열이므로 a-1
min_val = float('inf')  # 최솟값
for i in range(len(S)-(a-1)):
    min_val = min(min_val, S[i:i+a].count('b'))

print(min_val)

• 슬라이싱 인덱스 활용.
• 슬리이싱한 문자열(a의 개수)을 묶은 후, 묶은 문자열 내부의 b와 바깥의 a를 교환한다. 따라서 교환 횟수는 묶은 문자열 내부의 b의 갯수가 된다.
• 원형 문자열이므로 S += S[0:a-1] 을 이용해 이어준다.
• 문자열을 for문을 이용해 순서대로 묶어주며 b의 최솟값을 찾는다.
• https://da-y-0522.tistory.com/49

[백준] 1522 문자열 교환(Python)

 

---

문자열 게임2 - 골드5

https://www.acmicpc.net/problem/20437

T = int(input())

for _ in range(T):
    W = input()
    K = int(input())
    dic = {}

    answer1 = 10000
    answer2 = 0

    for i in W:  # 문자 갯수 세기
        if i in dic:
            dic[i] += 1
        else:
            dic[i] = 1

    dic = sorted(dic.items(), key=lambda x: x[1], reverse=True)  # 문자 갯수 정렬

    if dic[0][1] < K:  # 만족하는 연속 문자열이 없는 경우
        print(-1)
        continue
    else:
        for i in range(len(dic)):
            ans = []
            if dic[i][1] < K:  
                break
            for j in range(len(W)):  # K개 이상의 문자만 검사
                if W[j] == dic[i][0]:
                    ans.append(j)  # 문자 위치 저장

            for k in range(len(ans)-K+1):  # 문자 위치 비교

                answer1 = min(answer1, ans[k+K-1]-ans[k]+1)
                answer2 = max(answer2, ans[k+K-1]-ans[k]+1)
        print(answer1, answer2)

• ans 리스트에 검사할 문자의 위치 index를 저장한다.
• ans[k+K-1]-ans[k]+1 을 이용하여 문자를 정확히 K개 포함하는 문자열의 길이를 구한후, 최솟값 및 최댓값을 비교한다.

 

---

비슷한 단어 - 골드 4

 

https://www.acmicpc.net/problem/2179

N = int(input())
word_list = []
ans1 = ''
ans2 = ''
forword = 0

for _ in range(N):
    word = input()
    word_list.append(word)

for i in range(N-1):
    a = word_list[i]
    for j in range(i+1, N):
        b = word_list[j]
        for k in range(forword, len(a)):
            if a[:k+1] == b[:k+1]:
                if ans2[:k+1] != b[:k+1]:  # 중복되는 경우 제일 앞쪽에 있는 단어만 저장
                  forword = k  # 접두사 길이
                  ans1 = a
                  ans2 = b

print(ans1)
print(ans2)

• 시간 초과...아무래도 for문을 3개나 돌리니까....

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

# n = 9
# a = ["noon", "is", "for","lunch","most","noone","waits","until","two"]

# 입력받은 문자들을 인덱스와 함께 사전순으로 정렬한다.
b = sorted(list(enumerate(a)),key = lambda x: x[1])
# b = [(2, 'for'), (1, 'is'), (3, 'lunch'), (4, 'most'), (0, 'noon'), (5, 'noone'), (8, 'two'), (7, 'until'), (6, 'waits')]

# check 함수는 글자 하나하나가 서로 같은지 탐색
def check(a, b):
    cnt = 0
    for i in range(min(len(a), len(b))):
        if a[i] == b[i]: cnt += 1
        else: break
    return cnt

# 최장 접두사를 가진 문자열 담아둘 리스트 생성
length = [0] * (n+1)
maxlength = 0

for i in range(n-1):
    # 인접한 두개의 문자열을  check함수에 대입
    # tmp 값은 동일한 접두사의 길이
    tmp = check(b[i][1], b[i+1][1])
    # 최장 접두사 길이 갱신
    maxlength = max(maxlength, tmp)
    
    # b[i][0]은 문자가 입력된 순서, 즉 인덱스
    # length 에 입력된 순서에 자기 접두사 길이를 저장
    # max 함수로 이전 값하고 현재 값하고 비교하여 집어넣음
    length[b[i][0]] = max(length[b[i][0]], tmp)
    length[b[i+1][0]] = max(length[b[i+1][0]], tmp)
    # length = [4, 0, 0, 0, 0, 4, 0, 0, 0, 0]
    
first = 0
for i in range(n):
    # 입력된 순서대로 접두사의 길이 비교
    if first == 0:
        # 만약 현재 접두사의 길이가 최장접두사라면
        if length[i] == max(length):
            # 제일 먼저 입력된 문자 출력
            first = a[i]
            print(first)
            pre = a[i][:maxlength]
    else:
    	# 다음으로 입력되었된 값들 중 최장 접두사 출력후 종료
        if length[i] == max(length) and a[i][:maxlength] == pre:
            print(a[i])
            break

 

• 사전순으로 정렬하면 인접한 두 문자열만 비교하면 되므로 시간이 단축된다! 단, 중복 시 먼저 입력된 문자열을 출력해야하므로 입력받은 인덱스도 함께 정렬한다.
• 인접한 문자열들의 접두사를 계산 후 length 리스트 및 최장 접두사 길이(maxlenth)를 저장한다.
• 입력 인덱스 순으로 length 리스트에 접두사 길이를 저장한 후, 접두사의 길이와 최장접두사를 비교 후 출력한다.
• https://lazypazy.tistory.com/26

[백준] 2179번: 비슷한 단어

 

---

문자열 폭발  - 골드4

https://www.acmicpc.net/problem/9935

 

text = input()
bomb = input()

stack = []

for i in range(len(text)):
    stack.append(text[i])
    while len(stack) >= len(bomb) and ''.join(stack[-len(bomb):]) == bomb:
      # stack = stack[:-len(bomb)] # 시간 초과
      del stack[-len(bomb):]

if stack:
  print(''.join(stack))
else:
  print('FRULA')

• stack을 이용해서 해결.
• stack의 문자열을 제거할 때 del을 쓰는 것이 더 빠르다.

 

 

---

# 회고

 

코테 다시 연습중..