[파이썬/Python] 백준 1283번: 단축키 지정

📌 문제 : 백준 1283번

---

📌 문제 탐색하기

N : 옵션 개수 $(1 ≤ N ≤ 30)$
strings : 문자열 $(1 ≤ 단어 개수 ≤ 5, 1 ≤ 알파벳 개수 ≤ 10)$

문제 풀이

⭐️ 단축기 지정 방법

• 왼쪽에서 오른쪽 순서로 단축키 지정 여부 확인
• 지정 X
  • 해당 알파벳 단축키로 지정
• 지정 O
  • 그 다음 순서대로 단어의 첫글자 키 지정
  • 다음 단어 첫글자도 지정O
    • 왼쪽에서부터 차례대로 지정할 수 있는 것 찾기
• 아무것도 지정 못한다면?
  • 그냥 놔두기
• 대소문자 구분 X

지정한 단축키를 저장할 리스트를 하나 만들어준다.
→ 소문자화된 단축키를 추가해준다.

for문으로 문자열에 하나씩 접근한다.

• 단어가 2개 이상인 경우, 아닌 경우 모두 존재
  • for문 내에서 각 단어의 첫글자 단축키 리스트에 존재하는지 확인
    • 단축키 추가 가능하면 추가 후 해당 문자열 값 탐색 중단
    • 단어 첫글자를 [첫글자] 형식으로 변경해 넣기
• 첫글자 모두 존재하면 처음부터 확인
  • 각 단어에 하나씩 접근
  • 인덱스 1부터 끝까지 있는지 단축키에 있는지 여부 확인
  • 없으면 추가, 있으면 추가 탐색

가능한 시간복잡도

입력 → $O(N * 단어 개수)$
첫글자 확인 → $O(N)$
나머지 글자 확인 → $O(N * 문자열 총 길이)$

최종 시간복잡도
$O(N * 문자열 총 길이)$로 최악의 경우 $O(30 * 5 * 10) = O(1500)$이 되어,
2초 내에 연산 가능하다.

알고리즘 선택

문자열, 단어, 문자 하나씩 접근하면서 단축키 추가 여부 파악

---

📌 코드 설계하기

1. 필요한 입력 받기
2. 단축키 저장 리스트 정의
3. 문자열 하나씩 접근
   3-1. 각 단어에 접근해 첫글자 확인
   3-2. 단축키 지정 시 값 변경
   3-3. 첫글자 모두 존재 시 문자 하나하나 접근해 확인
   3-4. 단축키 지정 시 값 변경
4. 결과 출력
   
   

---

📌 시도 회차 수정 사항

1회차

• 문제 이해를 잘못해서 제일 첫번째 글자가 단축키에 없으면 그 다음 문자를 넣는 식으로 구현했다.
• 문제 파악을 다시해서 처음부터 다시 구현했다.

2회차

• 단축키 지정한 값의 인덱스를 함께 저장해서 출력할 때 for문을 활용해 해당 인덱스를 출력할 때 괄호를 함께 출력하려고 했다.
• 구현하려니 반복문이 너무 많아졌고 차라리 값 자체를 바꾸는 것이 더 좋을 것이란 판단이 들어 문자열에서 단축키 지정된 값을 괄호로 감싸진 형태로 변경하였다.

---

📌 정답 코드

import sys

input = sys.stdin.readline

# N 입력
N = int(input())

# 문자열 입력
strings = [list(input().rstrip().split()) for _ in range(N)]

# 옵션 저장 리스트
options = []

# 단축키 생성
for string in strings:
    for i in range(len(string)):
        if string[i][0].lower() not in options:
            options.append(string[i][0].lower())
            # 문자에 괄호 추가
            string[i] = '[' + string[i][0] + ']' + string[i][1:]
            break

    # 첫글자 모두 존재
    else:
        for i in range(len(string)):
            # 첫 글자 이후의 문자 탐색
            for j in range(1, len(string[i])):
                if string[i][j].lower() not in options:
                    options.append(string[i][j].lower())
                    string[i] = string[i][:j] + '[' + string[i][j] + ']' + string[i][j + 1:]
                    break
            else:
                continue
            break

# 결과 출력
for string in strings:
    print(' '.join(string))

• 결과