[백준22232] 가희와 파일 탐색기

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

 

 

문제설명

 

 

가희는 jo_test 폴더에 들어와 있습니다. 가희는 jo_test에 있는 파일 N개를 아래 기준에 따라 정렬하려고 합니다.

1. 파일명 (FILENAME) 사전순으로
2. 파일명 (FILENAME)이 같다면 가희가 설치한 OS에서 인식하는 확장자가 붙은 것이 먼저 나오게
3. 1과 2로도 순서를 결정할 수 없다면, 파일 확장자 (EXTENSION) 사전 순으로

파일 N개를 문제에서 설명하는 정렬 기준에 따라 정렬해 주세요. 사전순의 기준은 아스키 코드 순입니다.

 

문제 해결 방법

 

이름, 확장자 순으로 sorted 함수에서 lambda를 통해 키를 설정후 정렬했다. 

 

이 과정에서 이름이 같은 값 중에서 확장자가 없것에 대해서 (확장자 없는 이름, 확장자 있는 이름) 순일 경우에만 확장자 없는 이름을 확장자 있는 이름 뒤로 자리를 바꿔줬다. 이 조건이 아닐경우, 정렬이 흐트러질 수 있기때문이다. 

 

 

코드 구현

 

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

name = [input().rstrip() for _ in range(N)]
extent = set(input().rstrip() for _ in range(M))

tmpValue = []
for value in name:
    tmpValue.append(value.split('.'))
#print(extent)


tmpValue = sorted(tmpValue, key = lambda x: (x[0], x[1]))
# sorted함수에 key를 lambda함수로 정해줬다. 

#print('tmpValue', tmpValue)

for i in range(N-1):
    if tmpValue[i][0] == tmpValue[i+1][0]:
        if tmpValue[i][1] not in extent and tmpValue[i+1][1] in extent:
            tmp = tmpValue[i]
            tmpValue[i] = tmpValue[i+1]
            tmpValue[i+1] = tmp
        
#print('tmpValue', tmpValue)


for i in tmpValue:
    #strr, extt = i
    print(i[0]+'.'+i[1])

 

시간/공간 복잡도

 

 

O(N)

 

 

최적화 및 개선

 

input을 통해 하나의 변수가 아닌 여러 변수를 연속적으로 받을때는 입력에 input함수를 사용하면 시간초과가 걸릴 수 있

다. 이를 개선하기 위해 sys.stdin.readline을 사용하면 시간을 줄일 수 있다.  

 

특정 값이 순서와 관계없이 시퀀스 자료에서 존재하는지 확인만 하고 싶을 경우, 해당 시퀀스 자료의 자료형을 set으로 설정하는 것이 list나 다른 자료형 보다 시간을 확 줄일 수 있다. 

 

 

근거는 다음과 같다. 

 

Set은 List보다 더 빠른 탐색 속도를 가진다.
그 이유는 내부적인 데이터 구조와 탐색 알고리즘의 차이 때문입니다.

1. 데이터 구조: 
- Set은 해시 테이블(Hash Table)로 구현되어 있습니다. 해시 테이블은 값에 대한 고유한 해시 코드를 계산하고, 해당 해시 코드를 기반으로 값을 저장하고 검색합니다. 이렇게 함으로써 Set은 중복된 값을 허용하지 않으며, 값에 상수 시간(O(1))으로 접근할 수 있습니다.
- List는 배열(Array)로 구현되어 있습니다. 배열은 각 요소가 인덱스로 직접 접근되므로 인덱스를 알면 상수 시간(O(1))에 해당 요소에 접근할 수 있습니다. 하지만 List에서 값을 검색하기 위해서는 전체 리스트를 순회해야 하므로 최악의 경우 선형 시간(O(N))이 걸릴 수 있습니다. 

2. 탐색 알고리즘: 
- Set에서 값의 존재 여부를 확인하는 연산은 내부적으로 해시 함수와 버킷(bucket)을 사용하여 상수 시간O(1) 안에 처리됩니다. 
- List에서 값의 존재 여부를 확인하기 위해서는 순차적인 비교 연산을 수행해야 합니다. 따라서 최악의 경우 리스트의 모든 요소를 순회해야 하므로 선형 시간O(n)이 걸립니다. 따라서 Set은 내부적인 데이터 구조와 탐색 알고리즘을 통해 중복을 제거하고 빠른 탐색 속도를 제공합니다. 

그러나 Set은 순서가 보장되지 않으며, 인덱스 기반 접근이 불가능하기 때문에 특정 위치의 요소에 바로 접근하는 용도보다는 멤버십(Membership) 확인(=존재유무확인) 등을 위한 용도로 주로 사용됩니다.

출처: https://05-archives.tistory.com/232 [05의 개발 계발:티스토리]

 

 

어려웠던 점

 

로직적으로 맞게 코드를 짜도 입출력 함수나 자료형 설정에 따라 시간 초과되는 코드가 정답처리가 되다니 놀랍다!!

이제 이런 부분도 열심히 챙기면서 문제 풀어야겠다.