개인적으로 너무 재밌었던 문자열! upper, split, index, set 등 기본적인 함수만 잘 활용하는 것이 핵심인 주제라고 생각된다. 기초적인 문법과 함수를 돌아볼 수 있어서 좋았다.
1157 : 단어 공부
알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.
입력
첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다.
출력
첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.
풀이
알고리즘 문제는 코드를 얼마나 간단하고 직관적으로 구현하느냐도 중요하다. DP 문제도 먼저 top-down으로 구현하고 이를 참고하여 효율적인 bottom-up 방식으로 다시 작성하는 것처럼, 다른 분류에 속하는 문제들 또한 처음 작성한 코드에서 간단하고 쉽게 수정하는 과정이 필요하다.
시도 1
처음에는 단순히 입력값으로 받은 단어에서 알파벳의 개수를 일일이 세어 리스트의 값을 갱신해주는 방식으로 코드를 구현했다. 가장 많이 사용된 알파벳(들)은 max_list에 저장하고, 해당 리스트에 값이 두 개 이상이라면 ?를 출력하도록 했다.
하지만 코드가 전체적으로 반복문이 많이 사용되었기 때문에, 결국 시간 초과가 발생하였다.
시도 2
리스트를 정의하되 값을 갱신하는 것이 아니라 단순히 추가하는 방식을 이용하면 시간 단축이 될 것 같아, 두 번째 시도에서는 count의 값을 추가하는 방식으로 코드를 작성하였다.
upper메소드를 이용하여 입력값으로 받은 단어를 대문자로 변환한다.
: 문제에서 출력값으로 대문자를 요구하기 때문- 단어에서 중복된 알파벳을 제거하고
spell리스트에 저장한다. - 각 알파벳이 단어에 등장한 횟수를
dp리스트에 저장한다. dp의 최댓값이 2개 이상이라면?를 출력한다.dp의 최댓값이 하나라면, 최댓값의 인덱스를 찾아 해당 위치의 문자열을 출력한다.
위와 같은 방법으로 코드를 작성하였더니, 시간도 단축되고 전체적인 코드도 깔끔해진 것을 확인할 수 있었다.
코드
시도 1 (시간 초과)
spell = list(input().upper())
n = len(spell)
dp = [0] * n
for i in range(n):
if dp[i] == 0:
for j in range(i, n):
if spell[i] == spell[j]:
dp[i] += 1
max_list = [max(dp)==dp[i] for i in range(n)]
if max_list.count(True) > 1:
print("?")
else:
print(spell[max_list.index(True)])시도 2
word = input().upper()
spell = list(set(word))
dp = []
for i in spell:
dp.append(word.count(i))
if dp.count(max(dp)) > 1:
print("?")
else:
print(spell[dp.index(max(dp))])1764 : 듣보잡
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.
출력
듣보잡의 수와 그 명단을 사전순으로 출력한다.
풀이
- 듣지 못한 사람 n명을
no_listen리스트에 저장해준다. - 보지 못한 사람 m명을
no_see리스트에 저장해준다. - 두 리스트의 교집합을 확인하기 위해 각 리스트를 집합(set)으로 변환해주고,
intersection함수를 이용하여 두 집합이 모두 가지고 있는 값을bothno라는 새로운 변수로 정의해준다. 이 과정에서sorted함수를 이용해 사전순으로 정렬해준다. - 문제에서 요구한 대로, 듣보잡의 수를 먼저 출력하고 명단을 사전순으로 한 명씩 출력한다.
리스트 간의 교집합, 차집합, 합집합 등을 구하기 위해서는 집합(set)으로 변환하는 과정이 필요하다. set1 & set2 또는 set1.intersection(set2)을 이용해 교집합을 도출할 수 있다.
코드
n, m = map(int, input().split())
no_listen = []
no_see = []
for i in range(n):
no_listen.append(input())
for j in range(m):
no_see.append(input())
bothno = sorted(set(no_listen).intersection(set(no_see)))
print(len(bothno))
for k in bothno:
print(k)1541 : 잃어버린 괄호
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
출력
첫째 줄에 정답을 출력한다.
풀이
괄호를 이용하여 식이 가장 작은 값을 산출해내도록 만들기 위해서는, 더하기(+)를 먼저 계산한 뒤에 빼기(-)를 계산해주어야 한다. 예를 들어 80-70-100+20-90 이라는 식이 주어졌다고 했을 때, 원래대로 계산하면 -160이다. 하지만 80-70-(100+20)-90 이렇게 더하기에 괄호를 붙여 먼저 계산해준 뒤에 뺄셈을 해주면 -200이라는 최솟값을 도출할 수 있다.
이를 기반으로 생각한 문제 접근 방법은 다음과 같았다.
- 입력값으로 받은 식을
-를 기준으로 split 하여 리스트로 저장 - 리스트의 값 중
+를 포함한 값들은+를 기준으로 split 하여 덧셈 진행한 뒤, 결괏값으로 리스트를 갱신 - 리스트의 가장 첫 번째 원소를 제외한 나머지 원소들은 빼주어야 하기 때문에,
total이라는 변수에 첫 번째 원소를 저장하고 리스트에서는 해당 값을 삭제 - 나머지 원소들을
total값에서 모두 빼줌으로써 괄호를 이용해 만들 수 있는 최솟값 도출
여기서 주의할 점은 input 값 자체가 문자열이기 때문에, split을 하고 난 뒤에는 map 함수를 이용하여 각 숫자들을 정수값으로 변환해주어야 한다.
또한 + 포함 여부를 확인할 때 index가 아닌 find를 사용한 이유는 find는 찾고자 하는 값이 없을 때 -1을 반환하는 반면에, index는 찾고자 하는 값이 없을 때 오류를 발생시키기 때문이다.
코드
split_str = input().split("-")
for i, str in enumerate(split_str):
if str.find("+") != -1:
plus_list = str.split("+")
plus_list_a = map(int, plus_list)
split_str[i] = sum(plus_list_a)
num_list = list(map(int, split_str))
total = num_list[0]
num_list.pop(0)
for num in num_list:
total -= num
print(total)9935 : 문자열 폭발
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.
출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
풀이
성공하기까지 다양한 생각과 고민을 할 수 있었던 문제였다. 굉장히 간단해 보이는 문제지만, 자료구조를 떠올리지 못하면 답이 안 보이는 문제랄까..
시도 1
먼저 문제에서 말한 문자열과 폭발 문자열을 각각 입력 받아 word와 bomb이라는 변수에 저장한다. 첫 번째 시도에서는 while 문을 사용하여 폭발 문자열이 모두 사라질 때까지 문자열을 비교하고, 삭제하고, 붙이는 과정을 반복시켜주었다.
하지만 while 문이 돌아갈 때마다 문자열 자체와 폭발 문자열을 비교한다는 것 자체가 상대적으로 시간이 많이 소요되었고, 결과적으로 시간 초과가 발생했다.
시도 2
문자열 전체가 아니라 알파벳 하나씩을 비교하면 시간이 단축되지 않을까 싶어 고민하던 중, 하나씩 쌓아 올리는 스택(stack)이 떠올랐다. 스택을 이용하면 매번 문자열 전체를 비교할 필요 없이 문자열의 맨 끝 문자 일치 여부만으로 폭발 문자열과의 비교 여부를 결정할 수 있으므로 불필요한 과정이 생략되고 속도를 향상시킬 수 있다.
- 문자열에 등장한 알파벳을
stack에 하나씩 저장 - 저장할 때마다 마지막으로 저장된 값이 그 값이 폭발 문자열의 맨 끝 문자와 일치하는지 비교
- 일치한다면, 스택의 맨 위부터 폭발 문자열의 길이까지와 폭발 문자열을 비교한 뒤 같으면 제거
- 이 과정을 반복하고 마지막으로 스택이 비어있다면
FRULA를 출력하고, 그렇지 않다면 스택 안에 있는 알파벳들을 공백 없이 출력
폭발 문자열 값을 제거할 때 pop이 아닌 del을 사용한 것은, pop을 사용하게 되면 또 다시 for 문을 이용해주어야 하기 때문이다. 알고리즘 문제를 풀면서 for 문이 필수적이지 않은 상황에서는 최대한 사용을 안 하는 것이 시간 초과를 발생시키지 않는 방법이라고 생각했다.
코드는 비교적 간단하지만, 스택을 떠올리지 못했다면 정말 많은 시간 고민을 했을 거 같은 문제였다. 자료구조의 중요성을 다시금 상기시켜주는 소중한 문제!
코드
시도 1 (시간 초과)
word = input()
bomb = input()
while word.find(bomb) != -1:
word = word[:word.find(bomb)] + word[word.find(bomb)+len(bomb):]
if word == "":
print("FRULA")
elif word.find(bomb) == -1:
print(word)
else:
pass시도 2
word = input()
bomb = input()
stack=[]
for i in word:
stack.append(i)
if stack and stack[-1] == bomb[-1]:
if ''.join(stack[-len(bomb):]) == bomb:
del stack[-len(bomb):]
if stack:
for p in stack:
print(p, end = '')
else:
print("FRULA")