[SWEA 1242] 암호코드 스캔 (python)

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

SW Expert Academy

암호코드 스캔 문제

주어진 암호를 변환하여 원하는 형태로 바꾸고, 이를 통해 필요한 값을 구하는 문제

100% 내 생각으로 풀었는가?
→ △

16진 코드를 2진 코드로 바꾸는 과정 등에 대해 참고하여 풀었음

내가 푼 정답코드

ratio = {(2, 1, 1): 0, (2, 2, 1): 1, (1, 2, 2): 2, (4, 1, 1): 3, (1, 3, 2): 4, (2, 3, 1): 5,
         (1, 1, 4): 6, (3, 1, 2): 7, (2, 1, 3): 8, (1, 1, 2): 9} # 맨앞 0을 제외한 2번,3번,4번 칸의 비율

T = int(input())
for case in range(1,T+1):
    N, M = map(int, input().split())
    code = list(set([input() for _ in range(N)])) #겹치는 줄 지워버리자
    answer = 0 # 최종 결과 값
    temps = [] # 임시로 저장해줘야하는 값
    for i in code: # 코드 내용물들
        result = format(int(i, 16), 'b').lstrip('0') #16진법을 2진법으로 바꿔주자
        n1 = n2 = n3 = 0 # 비율 계산
        cnt = 0
        even = odd = 0 # 홀짝
        overlap = '' # 겹쳐지는 녀석
        for j in result: # 리스트 내용물에서
            if j == '1' and n2 == 0: # 1을 받았는데 n2=0이면
                n1 += 1 # n1에 1 더해
            elif j == '0' and n1 != 0 and n3 == 0: # 0을 받았는데 n1의 값이 0이 아니고 n3의 값이 0이면
                n2 += 1 # n2에 1 더해
            elif j == '1' and n2 != 0: # 다시 1을 받았는데 n2가 0이 아니면(n3이란 뜻)
                n3 += 1 # n3에 1 더해
            elif n3 != 0: # 위케이스 다 지났는데 n3가 0이 아니면 -> 즉 코드를 받았다면
                cnt += 1 #횟수 증가
                r = min(n1, n2, n3) #비율 나눠줘야 하니까 최소값을 구해서
                nums = ratio[(n1//r,  n2//r, n3//r)] #최소 값으로 나눠 비율을 맞춰주자
                overlap += str(nums) #이 때의 코드 번호 저장하자
                if cnt == 8: # 암호가 8자리가 됐다면
                    if (odd*3 + even + nums) % 10 == 0 and overlap not in temps: # 조건에 맞고, 겹치는 놈이 없으면
                        answer += odd+even+nums # 답에 지금 암호값 더하자
                    temps.append(overlap) # 나중에 겹치는놈 체크용
                    even = odd = 0 #홀수 짝수 초기화
                    cnt = 0 # 횟수도 초기화
                    overlap = '' #암호도 초기화
                elif cnt % 2 == 0 : # 8자리가 아니라면, 홀수 값을 모아주자
                    even += nums
                else:
                    odd += nums # 짝수 값을 모아주자
                n1 = n2 = n3 = 0 #비율도 초기화
    print(f'#{case} {answer}')

문제에 대한 요구사항을 잘 파악하고, 이를 통해 원하는 형태로 출력하는 전형적인 구현 문제였다.

요구사항은 크게 3가지다.

1. 주어진 케이스 안에 있는 16진수 숫자를 읽어서 2진수로 변환
2. 2진수로 변환한 값을 주어진 암호 조건의 맞게(비율에 맞게) 값을 찾기
3. 8자리 수의 짝수자리, 홀수자리 등을 구해서 검증코드와 비교

먼저 주어진 케이스를 읽는 과정에서 결국 같은 모양의 줄이 굉장히 많으므로 이걸 하나로 만들어주는 과정인 set함수를 이용하여 같은 케이스의 줄을 전부 지워버렸다.

그리고 앞에서부터 읽어가면서 내부에 있는 16진수를 2진수로 변경해주었고, 변경된 값을 기준으로 비율을 구해야 하므로 n1, n2, n3로 나누어 해당 갯수의 비를 구해주었다.

구해준 비를 토대로 다시 암호 기준에 맞게 숫자로 변환해주었고, 이 때의 암호를 overlap이란 형태로 모아주어 temps에 저장해주었는데, 이는 케이스가 커지면서 줄바꿈이 일어나는 과정에서 겹쳐지는 부분을 고려해줘야한다. (이부분 고려 안해줘서 2시간을 넘게 애먹었다..)

겹치는 부분을 고려해주는게 문제의 제일 큰 생각 포인트가 아닐까 싶다. 생각만 잘하면 구현할 수 있지만, 과정이 매우 험난한 문제

---

느낀 점

알고리즘에 대한 기술을 사용한다기보단(DFS라던지.. BFS라던지..) 거의 100% 구현 문제가 아니었나 싶다.

처음에 방향성을 잘못 잡아서 어떻게 해야할지 고민하면서 쓸대없이 앞에서부터 코드 56개를 뽑아서 계산하는 시도를 하고있었다가 이내 잘못 된걸 깨닫고 set으로 다 지워버리고 시작해버렸다.

비율 계산하는것도 어떻게 하면 좋을까 고민하다가, 그냥 말그대로 횟수 카운트로 넣어버리는게 낫겟다 싶어서 카운트로 넣어버려서 계산했더니 작은 크기의 케이스에선 통과됐다.

다만, 겹쳐지는 케이스가 발생하면서 해결을 못하고 있었고, 이를 해결하는 과정이 너무 골치아파서 2시간 가까이 생각해내는데 시간을 쓴거같다.

거진 3~4시간 소비해서 풀어낸 문제였고, 꽤나 도전적인 문제지 않았나 싶다. 그리고 느낀건 문제를 잘 읽어보고 문제에서 요구하는대로 따라가면 80%는 구현할 수 있다는 걸 다시 한번 크게 느꼈다