BOJ 25955 - APC는 쉬운 난이도 순일까, 아닐까? (Python3)

어제 출제된 2022 아주대학교 프로그래밍 경시대회 APC A번 문제였다.

다행히 A번이 가장 쉬운 난이도를 가진 문제라서 풀었지, 아니었으면 A번 문제에서 막혔다가 튕겨져 나갈 뻔 했다.

네 번 도전해서 겨우 통과했는데, 할 수 있는 모든 에러를 한 번씩 다 저질러 본 느낌이다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

선우는 APC 문제를 만들기 위해 고민하며 역대 APC들을 둘러보던 와중, 이 대회들의 문제가 난이도가 쉬운 순으로 배치되어 있는 경향을 발견했다! 문제 출제가 완료되고 올해도 이러한 기조를 지키려고 한 선우는 출제하기로 한 문제들에 예상 난이도를 매겨놓았다.

난이도는 브론즈 티어, 실버 티어, 골드 티어, 플래티넘 티어, 다이아몬드 티어 순으로 어려워지며, 동일 난이도가 없도록 엄밀한 구별을 위하여 각각의 티어에 1에서 1000 사이의 수를 매겨놓기로 하였다. 동일 티어에서는 수가 작을수록 어려운 것을 의미한다. 예를 들어서 브론즈 티어 1단계의 문제는 브론즈 티어 1000단계의 문제보다 어렵고, 실버 티어 1000단계의 문제는 브론즈 티어 1단계의 문제보다 어렵다. 이후 선우는 문제를 난이도의 오름차순으로 정렬해놓았다.

그러나 각각 작년과 올해에 아주대학교 소프트웨어 학과 알고리즘 소학회인 A.N.S.I. 회장을 하며 지쳐있었던 또 다른 APC 출제자 의찬이와 지수는 정신적으로 힘들었던 나머지 합심하여 트롤링을 저지를 계획을 세운다.

¶ 의찬, 지수: 헤헷

그 트롤링 계획은 바로 둘이서 잘 정렬되어 있었던 문제 중 랜덤하게 두 개를 골라 순서를 바꾸어놓는 것이었다! 둘이서 이를 계획했다는 것을 눈치채어 머리가 지끈지끈해진 선우는 빨리 이를 복구하고자 한다. 선우를 도와주는 프로그램을 만들어주자.

 

입력

첫째 줄에 문제의 수 N이 주어진다. (2 ≤ N ≤ 1000)

둘째 줄에 배치되어 있는 문제의 난이도 N개가 공백을 사이에 두고 주어진다. 문제의 티어는

• 브론즈: B
• 실버: S
• 골드: G
• 플래티넘: P
• 다이아몬드: D 

표기되며, 난이도는 [티어][단계]로 주어진다. 예를 들어서 브론즈 티어 1000단계의 문제는 B1000, 다이아몬드 티어 1단계의 문제는 D1로 표기된다.

모든 문제의 난이도는 서로 다르게 주어진다.

 

예제 입력)

# 예제 입력 1
6
B50 S999 S1 G5 P3 D1

# 예제 입력 2
2
D1 B1

# 예제 입력 3
5
B1 P1 G1 S1 D1

 

출력

의찬이와 지수가 계획을 실행에 옮기지 않아 문제들의 난이도가 쉬운 순으로 잘 배치되어 있다면 OK를 출력한다.

그렇지 않다면 첫째 줄에 KO를 출력하고, 잘못 배치된 문제 2개의 난이도를 난이도가 쉬운 순서대로 출력한다.

3개 이상의 난이도가 뒤섞여 있는 경우는 없다. 즉, 순서 바꾸기는 최대 한 번만 발생한다.

 

예제 출력)

# 예제 출력 1
OK

# 예제 출력 2
KO
B1 D1

# 예제 출력 3
KO
S1 P1

 

---

내 코드

n, li, data = int(input()), input().split(), ['B','S','G','P','D']
li2, x = [0]*n, []
for i in range(n):
    li2[i] = data.index(li[i][0])*1000+(1000-int(li[i][1:]))
if li2 == sorted(li2): print('OK')
else:
    print('KO')
    for i in range(n):
        if li2[i] != sorted(li2)[i]:
            x.append(li[i])
    print(' '.join(reversed(x)))

 

제출해서 정답을 맞았던 바로 그 코드가 이거다. 여러 모로 이해하기 힘들게 쓰여 있지만 사실은 별 것 아니다. 한 줄 한 줄 뜯어보며 설명하도록 하겠다.

1번 줄에서 n, li, data는 각각 첫 줄에 입력되는 문제 수, 둘째 줄에 입력되는 문제의 난이도들, 그리고 각 티어의 머리글자를 의미한다.

그리고 두 번째 줄에는 티어를 숫자화해서 정리할 li2라는 배열과, 답을 출력해 줄 x 배열을 넣었다.

그리고 첫 번째 for문 안에는, li[i]. 즉 i번째 문제의 티어를 숫자로 만들었다.

 

만약 i번째 문제, 곧 li[i]가 문자열 "G11"이라면, li[i][0]은 첫 번째 문자인 "G"를, int(li[i][1:])은 맨 앞 글자만 뺀 걸 숫자로 바꾼 11을 뱉을 것이다. 이제 G를 랭크 파트, 11을 티어 파트라고 하자.

또한 실제 난이도와 숫자의 크기는 반대로 되어 있다는 것을 고려하여, 1000에서 티어 파트를 뺀 수를 실제 난이도 측정 도구로 두자. 티어 파트가 11이면 실제 난이도는 989, 티어 파트가 1이면 실제 난이도는 999, 티어 파트가 1000이면 실제 난이도는 0인 식이다.

S1000 문제가 B1 문제보다 더 어렵다는 것을 가정해서, data.index(랭크 파트)*1000을 난이도 측정 도구에 더해 주도록 하자. 그러면 B1은 난이도가 999가 되고, S1000은 난이도가 1000이 되어 명확하게 난이도가 구별이 될 것이다.

그게 li2[i] 안에 들어갈 data.index(li[i][0])*1000+(1000-int(li[i][1:]))이 되는 것이다.

 

이제 li2라는 리스트에는 각 문제의 난이도를 숫자로 바꾸어서 저장이 되어 있을 것이다.

이게 난이도 순으로 정렬이 되어 있다면, sorted(li2)도 원본 리스트 li2와 차이가 없을 것이다. 그러면 OK를 출력해 주면 되는 일.

그렇지 않다면, 이제 li2[i]와 sorted(li2)[i]를 하나하나 비교해 가면서 서로 다른 게 있다면 x에 원본 리스트의 i번째 문제 li[i]를 집어 넣는 것이고.

이 때 주의해야 할 점. 원본 리스트는 이미 트롤링이 일어난 것이기 때문에, 난이도 역순으로 분류가 되어 있을 것이다.

그러니 reversed(x)를 이용해서 출력해 주면 그만이다.

 

이로서 25955번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.