백준 13377번
https://www.acmicpc.net/problem/13377

문제

후기

⏰ 풀이시간 30분 ++⏰

맞힌 사람이 많지 않은 문제를 풀기 위해 풀은 사람이 적은 순으로 정렬해서

찾은 문제의 10번째다.

문제는 (a,b,c,d,e,f,g,h,i) 로 이루어진 list가 있다고 했을때,

이 문자들로 만들 수 있는 모든 조합이 있다고 가정했을 때, 사전순으로 해당 문자조합이 몇 번째 인지

알아내는 것이다. abcdefghi는 1번째, abcdefgih는 2번째... 이런식으로 말이다.

메모리 제한도 512mb로 넉넉하고,

li라는 dictionary를 선언해서, permutations로 모든 조합을 찾은 뒤,

value값을 1씩 증가시키면서 저장시키면 된다. (dictionary의 Get을 이용하면 O(N)으로 찾을 수 있으므로..)

알파벳이 9개이기 때문에 O(N!)의 시간복잡도를 가지는 permutations는

9! 즉 362880번의 연산을 수행하게 되므로, 충분히 시간안에 가능할 것이라

생각하고 permutations를 사용했다.

import sys
input= sys.stdin.readline
import itertools
from itertools import permutations

alp = [ chr(i) for i in range(97,106)] #a부터 i까지 저장
alp_list = sorted(list(itertools.permutations(alp,9))) #모든 조합을 만들어서
li = dict()
cnt = 1 
for i in alp_list: #1씩 증가시키며 dictionary에 저장한다.
    k = "".join(map(str,i))
    li[k] = cnt
    cnt += 1
N = int(input())
for _ in range(N):
    word = input().rstrip()
    print(li.get(word)) #해당 입력된 문자열이 dictionary의 몇번째인지 출력한다.