[BOJ][C++] 백준 1032번 명령 프롬프트
Updated:
1032번 명령 프롬프트
1. 문제 정보
백준 온라인 저지 [1032번 명령 프롬프트] 문제의 링크입니다.
문제
시작 -> 실행 -> cmd를 쳐보자. 검정 화면이 눈에 보인다. 여기서 dir이라고 치면 그 디렉토리에 있는 서브디렉토리와 파일이 모두 나온다. 이때 원하는 파일을 찾으려면 다음과 같이 하면 된다.
dir *.exe라고 치면 확장자가 exe인 파일이 다 나온다. “dir 패턴”과 같이 치면 그 패턴에 맞는 파일만 검색 결과로 나온다. 예를 들어, dir a?b.exe라고 검색하면 파일명의 첫 번째 글자가 a이고, 세 번째 글자가 b이고, 확장자가 exe인 것이 모두 나온다. 이때 두 번째 문자는 아무거나 나와도 된다. 예를 들어, acb.exe, aab.exe, apb.exe가 나온다.
이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야 그 결과가 나오는지를 출력하는 문제이다. 패턴에는 알파벳과 “.” 그리고 “?”만 넣을 수 있다. 가능하면 ?을 적게 써야 한다. 그 디렉토리에는 검색 결과에 나온 파일만 있다고 가정하고, 파일 이름의 길이는 모두 같다.
입력
첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 알파벳과 “.” 그리고 “?”로만 이루어져 있다.
출력
첫째 줄에 패턴을 출력하면 된다.
예제 입력1
3
config.sys
config.inf
configures
예제 출력1
config????
시간 / 메모리 제한
2초 / 128MB
2. 생각
-
여러 개의 문자열을 입력받아 같은 문자는 그대로 출력하고 다른 문자는 ‘?’로 출력하는 문제입니다.
-
문자열을 입력받고 문자끼리 비교하는 구문을 이중 for문을 사용하려고 합니다. O(n^2)의 시간이 걸리기 때문에 시간초과를 피하기 위해서는 입력의 크기를 고려해야합니다. 입력의 크기가 최대 50개의 문자열, 문자의 길이가 최대 50이므로 50*50 = 2500이므로 시간 초과를 피할 수 있습니다. (대략 1억 = 1초)
- 아래 표 처럼 여러 개의 문자열에서 공통된 config는 그대로 출력하고, 다른 부분인 나머지 네 글자는 ‘?’를 출력합니다.
i\j 0 1 2 3 4 5 6 7 8 9 0 c o n f i g . s y s 1 c o n f i g . i n f 2 c o n f i g u r e s 출력 c o n f i g ? ? ? ? i\j 0 1 2 3 4 5 6 7 8 9 0 c o n f i g . s y s 1 c o n f i g . i n s 2 c o n f i g u r e s 출력 c o n f i g ? ? ? s -
i는 한 문자열 단어를 나타내는 인덱스이고, j는 여러개의 문자열 하나하나를 나타내는 인덱스입니다. i와 j로 단어를 비교하면서 다른 단어가 나오면 bool flag를 두어 ‘?’를 출력하고 비교하는 것을 멈춥니다.
- 만약 모든 문자열의 i번 인덱스의 문자가 모두 같다면 반복문을 무사히 빠져나오고, 무사히 빠져나오면 문자를 출력합니다.
3. 소스코드 (C++)
