[백준] 3985번 롤 케이크 파이썬 해설

출처 : https://www.acmicpc.net/problem/3985

3985번: 롤 케이크

시뮬레이션으로 알고리즘으로 분류된 문제이다.

개인적으로 시뮬레이션 문제가 익숙하지 않아서 많이 풀어보려고 하는 중이다.

 

그냥 한번 우리 대학교 랭킹을 봤는데 23등이었다. 프로그래밍을 시작한 지 이제 1년 9개월 정도 되는데 컴퓨터 공학과가 아니라는 점을 감안하면 꽤 좋은 성적이라고 생각한다 ㅎㅎ

그냥 기록을 남기고 싶었다..

 

풀이

---

이번 시뮬레이션 문제는 이 전에 풀었던 주사위 문제보다 훨씬 쉬웠다.

사실 훨씬 더 쉽게 푸는 방법이 있긴 한데 우선 내 풀이 코드를 먼저 정리해보자.

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n, m = int(input()), int(input())
    m_num = [0, 0]
    arr = [None for _ in range(n+1)]
    for i in range(1,m+1):
        s, e = map(int,input().split())

        if e - s > m_num[0] :
            m_num = [e - s, i]

        for j in range(s-1, e):
            if arr[j] == None:
                arr[j] = i

    cnt_dict = {}
    for v in arr:
        if v != None:
            cnt_dict[v] = cnt_dict.get(v,0) + 1
    print(m_num[1])
    print(max(cnt_dict,key= lambda x: cnt_dict[x]))

1. 출력에 사용할 길이가 2인 리스트를 선언한다.

2. 문제에서 주어지는 n과 m을 입력받고 길이가 n인 None리스트 arr을 선언한다.

3. 문제에서 주어지는 m개의 입력을 받으며 알고리즘을 진행한다

• 시작 번호와 끝 번호를 입력받아서 둘 사이의 구간을 계산한다. 해당 번호를 포함하는지 안 포함하는지는 사실 무의미하다. 그냥 제일 넓은 구간의 번호만 기억해해서 첫 번째 출력으로 사용하기 때문이다.
• 시작 번호와 끝 번호에 맞춰 arr의 값을 변경한다. 접근하려는 원소가 None일 때만 변경하는 것에 주의하자.

4. 임시 딕셔너리 cnt_dict를 선언한다.

5. 리스트 arr에서 None이 아닌 원소의 개수를 세는 알고리즘을 수행한다.

6. 정답을 출력한다. 첫 번째 출력은 시작 번호와 끝 번호의 차이가 가장 큰 사람의 번호이다. 두 번째 출력은 임시로 선언했던 딕셔너리에서 value값이 가장 큰 key값(번호)이다.

 

추천하는 풀이 방법

---

파이썬에서 제공하는 Counter모듈을 사용해보는 것을 추천한다. 아마 파이썬의 강력함을 몸으로 느낄 수 있을 것이다.

파이썬이 알고리즘을 공부할 때 가장 쉽다고 하는 이유는 여러 가지 유용한 모듈이 많아서 이다.

리스트 원소들의 개수를 셀 때 나처럼 딕셔너리를 이용하는 방법도 있지만, Counter모듈을 사용한다면 한 줄이면 해결되는 신기한 현상을 볼 수 있다.

 

* 주의 : 가장 잘 만들어진 모듈을 사용하는 것이 가장 효율적인 방법인건 맞다. 하지만 때로는 조금 돌아가는 방법이 시간이 오래 걸리긴 해도 실력은 향상되는 방법이라고 생각한다. 모듈만 사용하는 방법보단, 먼저 스스로의 힘으로 풀어본 뒤 모듈을 사용하는 방법을 추천한다!

 

결과

---

오늘도 한 방에 통과했다. ㅎㅎ

아주 조금씩 실력이 늘고 있는 것 같아서 기분이 좋다!

요즘 데이터베이스 공부에 푹 빠져있어서 이것저것 찾아보는 중이다.

사실 이 글을 포스팅하자마자 찾아보러 갈 계획이었다.ㅋㅋ