개요
유형 - 구현, 문자열
풀이날짜: 2025.03.15
풀이방법 한줄 요약
파일 이름을 모두 리스트에 저장한 뒤, list[i][j]와 같은 2차원 리스트 조작 형식으로 리스트 내 파일 이름들을 char 단위로 글자 하나씩 비교한다.
💡Github URL
💡문제에서 구해야 할 것
- 문제 조건 :
- cmd의 dir 명령어는 'dir 패턴'을 쳤을 때 패턴에 맞는 파일만 검색 결과로 나온다.
(ex. dir a?b.exe라고 검색: 파일명의 첫 번째 글자가 a, 세번째 글짜가 b, 확장자가 exe인 것이 모두 나온다. 두 번째 문자는 ?이므로 아무거나 나와도 된다. => acb.exe, aab.exe, ...) - 검색 결과가 먼저 주어졌을 때, 어떤 패턴으로 검색해야 검색 결과들이 모두 나올 수 있는지 패턴을 출력하는 문제이다.
- 패턴에는 알파벳과 ".", "?"만 사용할 수 있고, 가능한 ?를 적게 사용해야 한다.
- cmd의 dir 명령어는 'dir 패턴'을 쳤을 때 패턴에 맞는 파일만 검색 결과로 나온다.
- 입력
- 첫 줄에는 파일 이름의 개수 N이 주어진다. (N<= 50, N은 자연수)
- 둘째 줄부터는 N개의 줄에 파일 이름이 주어진다.
- 파일 이름의 길이는 모두 같고, 길이는 최대 50이다.
- 파일 이름은 알파벳 소문자와 "."로만 이루어져 있다.
- 출력
- 첫째 줄에 패턴을 출력한다.
💡알고리즘 설계
- 정수형으로 N 값을 입력받음.
- N개의 줄로 주어지는 파일 이름을 하나의 리스트
file[]로 저장한다. - 이중 for을 설계한다.
- 첫 번째 for문은 i를
range(len(file[0]))의 범위로 반복하도록 한다. - 두 번째 for문은 j를
range(1, N)의 범위로 반복하도록 한다. file[j][i]들 중 기준이 되는file[0][i]과 하나라도 다른게 있다면answer[]에 "?"를 저장하고, 모두 동일하다면file[0][i]를answer[]에 저장한다.
- 첫 번째 for문은 i를
answer[]를 하나의 문자열 형태로 한 줄로 출력한다.
💡코드
메모리: 32544 KB, 시간: 48 ms
import sys
input = sys.stdin.readline
N = int(input())
file = [str(input()) for _ in range(N)]
answer = []
for i in range (len(file[0])):
flag = 1
tmp = file[0][i]
for j in range(1, N):
if file[j][i] != tmp:
flag = 0
if flag == 1:
answer.append(tmp)
else:
answer.append("?")
print("".join(answer))💡시간복잡도
- 외부 반복문 시간복잡도
- for 문 → O(N)
- 내부 반복문 시간복잡도
- for 문 → O(N)
- 최종 시간복잡도: O(N^2)
💡 틀린 이유 & 틀린 부분 수정
(맞았으므로 생략)
💡 다른 풀이 or 기억할정보
- 입력 방식 최적화
file = [str(input()) for _ in range(N)]1) input(), 즉 sys.stdin.readline()은 기본적으로 문자열을 반환하므로 str()로 감쌀 필요가 없다.
2) sys.stdin.readline()은 개행 문자(\n)을 포함하므로, 문자열을 다루는 이 문제에서는 안전하게 strip()을 통해 제거하는 것이 좋다.
수정 코드:
file = [input().strip() for _ in range(N)]all()사용
flag = 1
tmp = file[0][i]
for j in range(1, N):
if file[j][i] != tmp:
flag = 01) flag 변수를 통해 if file[j][i] != tmp를 체크하는 방식을 사용하고 있다. 그러나 all()를 사용한다면 조금 더 깔끔하게 작성할 수 있다.
수정 코드:
tmp = file[0][i]
if all(file[j][i] == tmp for j in range(1, N)):all()은 모든 값이 True, 즉 file[j][i] == tmp일 때만 True를 반환하므로 flag 변수가 필요 없어진다.
cf) if flag == 1은 if flag:로 사용할 수 있음
최종 수정 코드:
import sys
input = sys.stdin.readline
N = int(input())
file = [input().strip() for _ in range(N)] # 개행 문자 제거
answer = []
for i in range(len(file[0])):
tmp = file[0][i]
if all(file[j][i] == tmp for j in range(1, N)): # all() 사용
answer.append(tmp)
else:
answer.append("?")
print("".join(answer)) # 리스트를 문자열로 변환하여 출력- 메모리: 변화 없음 (32412KB)
- 시간: 단축 (48 ms → 40 ms)
💡 느낀점 or 기억할정보
sys.stdin.readline()이str타입으로 들어오고, 개행 문자(\n)가 포함된다는 것을 기억하자.
all()함수에 대해 잘 알아두자.
all(): 리스트, 튜플과 같은 반환 가능한(iterable) 객체의 모든 요소가 True일 경우 True를 반환하는 내장 함수. 시간 복잡도: O(N)
print(all([True, True, True])) # ✅ 모든 값이 True → True 반환
print(all([True, False, True])) # ❌ False가 포함 → False 반환
print(all([])) # ✅ 빈 리스트는 기본적으로 True 반환리스트의 모든 요소가 특정 조건을 만족하는지 검사할 때 사용하면 좋음.
nums = [2, 4, 6, 8]
print(all(num % 2 == 0 for num in nums)) # ✅ 모든 숫자가 짝수 → True 반환
nums = [2, 3, 6, 8]
print(all(num % 2 == 0 for num in nums)) # ❌ 홀수(3) 포함 → False 반환
개발자 지망생