[SWEA] 1221. GNS - Python

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14jJh6ACYCFAYD 

SW Expert Academy

 

< 📝 문제 >
숫자 체계가 우리와 다른 어느 행성이 있다. 아래는 이 행성에서 사용하는 0 ~ 9의 값을 순서대로 나타낸 것이다.

"ZRO", "ONE", "TWO", "THR", "FOR", "FIV", "SIX", "SVN", "EGT", "NIN"

0 ~ 9 의 값을 나타내는 단어가 섞여 있는 문자열을 받아 작은 수부터 차례로 정렬하여 출력하는 프로그램을 작성하라.

예를 들어 입력 문자열이 "TWO NIN TWO TWO FIV FOR" 일 경우 정렬한 문자열은 "TWO TWO TWO FOR FIV

 

NIN" 이 된다.

< ❓ 생각 >
1.

행성의 숫자 체계를 순서대로 반복문을 돌려 같을 때 값을 출력 

반복

 

2-1. Bubble Sort

 1) 인접한 요소 2개씩 비교해서 큰 것 뒤로 보내기

 2) 1번 모든 요소에 대해서 다 실행하면 가장 큰 수가 제일 뒤

 3) 1~2번을 N-1번 반복하면 전체가 순서대로 정렬됨

------------단점 : 오래 걸림

 

2-2. Select Sort

 1) 0~N-1까지 자리에 들어갈 요소를 순서대로 찾아서 넣기

 2) i번째 들어갈 요소 찾아서 i번째 넣기

 3) i번보다 인덱스가 큰 것은 비교하지 않는다.(이미 자리를 찾았기 때문에)

----------- Bubble 보다는 빠름

 

2.3 Counting Sort

 1) 각 요소가 몇개씩 나왔는지 개수를 세기

 2) 각 요소가 들어갈 자리를 계산하기 위해 누적합 구하기
    ex)

    ONE이 들어갈 index는 (count[0]+1)~(count[1])

 3) count의 값을 하나씩 빼면서 각 요소가 들어갈 자리에 넣어주기

------------가장 빠름

 

< 💻 코드 >
1.

# T : 테스트 케이스의 개수
TC = int(input())
for _ in range(TC):
    # tc : 테스트 케이스의 번호, N : 문자열의 길이
    tc, N = input().split()
    # TEXT : 문자열
    TEXT = list(input().split())
    print(tc)
    for c in ['ZRO', 'ONE', 'TWO', 'THR', 'FOR', 'FIV', 'SIX', 'SVN', 'EGT', 'NIN']:
        for t in TEXT:
            if c == t:
                print(c, end=' ')
    print()

 

2-1.

GNS_dict = {'ZRO':0, 'ONE':1, 'TWO':2, 'THR':3, 'FOR':4, 'FIV':5, 'SIX':6, 'SVN':7, 'EGT':8, 'NIN':9}

def bubble_sort(target,N):
    for j in range(N-1):
        for i in range(N-1-j):
            # 내 뒷 요소랑 비교해서 크면 뒤로 보내기
            if GNS_dict[target[i]] > GNS_dict[target[i+1]]:
                target[i], target[i+1] = target[i+1], target[i]
	return target
    
# T : 테스트 케이스의 개수
TC = int(input())
for _ in range(TC):
    # tc : 테스트 케이스의 번호, N : 문자열의 길이
    tc, N = input().split()
    # 테스트 케이스
    target = input().split()
    
    result = bubble_sort(target,N)
    
    print(tc)
    print(*result)

2-2.

def select_sort(target,N):
    # 0번부터 N-1번까지 자리에 들어갈 요소를 순서대로 찾아서 넣어주기
    for i in range(N-1):
        # i번째 들어갈 요소 찾아서 i번째 넣어주기
        min_idx = i
        # i번보다 인덱스가 빠른 것은 비교하지 않는다(이미 자리를 찾았기 때문)
        for j in range(i+1,N):
            if GNS_dict[target[j]] < GNS_dict[target[min_idx]]:
                min_idx = j
        target[i], target[min_idx] = target[min_idx], target[i]
    return target
    
# T : 테스트 케이스의 개수
TC = int(input())
for _ in range(TC):
    # tc : 테스트 케이스의 번호, N : 문자열의 길이
    tc, N = input().split()
    # 테스트 케이스
    target = input().split()
    
    result = select_sort(target,N)
    
    print(tc)
    print(*result)

2-3.

def counting_sort(target,N):
    # 요소 중 최대값 만큼의 길이
    count = [0] * 10
    # target의 요소를 순서대로 넣어 줄 배열
    new_arr = [None] * N
    # 각 요소가 몇개씩 나왔는지 개수를 세고
    for i in range(N):
        count[GNS_dict[target[i]]] += 1
    # 각 요소가 들어갈 자리를 계산하기 위해서 누적합을 구함
    for i in range(1,len(count)):
        # count[i] = count[i-1] + count[i]
        count[i] += count[i-1]
    # 각 요소가 들어갈 자리에 넣어줌
    for i in range(N):
        count[GNS_dict[target[i]]] -= 1
        new_arr[count[GNS_dict[target[i]]]] = target[i]
    return new_arr


# T : 테스트 케이스의 개수
TC = int(input())
for _ in range(TC):
    # tc : 테스트 케이스의 번호, N : 문자열의 길이
    tc, N = input().split()
    N = int(N)
    # 테스트 케이스
    target = input().split()

    result = counting_sort(target, N)

    print(tc)
    print(*result)

< ❗ >

여러 가지 방법 중에 모든 것을 비교하는 Bubble이 가장 느리다