BOJ 25497. [Silver 5] 기술 연계마스터 임스

[hojongs]

Problem link

https://www.acmicpc.net/problem/25497

Problem abstraction

문제의 핵심을 요약한다. 체계적인 문제 접근을 위해, 문제를 추상화한다

적합한 자료구조를 생각한다

Design(Plan) algorithm

# 1

---
# 2

---
# 3

Algorithm idea

추상화한 문제 이해를 기반으로 알고리즘의 대략적인 구현 계획을 서술한다

Pseudo-code

idea를 수도 코드로 작성해본다

Validate algorithm

알고리즘의 유효 여부를 구현 전에 검증한다

예제 입력을 수도 코드로 계산해보고, 놓친 알고리즘 오류가 있는지 확인한다

Impl

import sys

readl = sys.stdin.readline

def f():
    n = int(readl())
    s = readl()
    lr  = []
    sk  = []
    cnt = 0
    for i in range(n):
        ch = s[i]
        if ch == 'L':
            lr.append(ch)
        elif ch == 'S':
            sk.append(ch)
        elif ch == 'R':
            if len(lr) > 0:
                lr.pop()
                cnt += 1
            else:
                break
        elif ch == 'K':
            if len(sk) > 0:
                sk.pop()
                cnt += 1
            else:
                break
        else:
            cnt += 1
    print(cnt) 

f()

Self-feedback

구조적 접근: 문제를 추상화하여 구조적으로 접근했는가?

https://colabear754.tistory.com/92

• 문제를 잘 읽고, 확실하게 문제를 이해한 후 알고리즘 설계를 시작하자

  • 상대방의 말을 끝까지 잘 듣고 확실하게 이해한 뒤 말하기와 동치라고 생각

• 경우의 수 분류를 확실하게 하자 (Edge case (반레) 찾기)

  • 처음에는 추상적으로 분류하지 말고, 가장 구체적인 방법으로 분류하자

• 1~9: 독립적

• l: push

  • l: push
  • r: pop & +1
  • s: push
  • l: push
  • r: ?
  • s: push
  • k: pop & +1
  • k: broken

• r: broken

• s

  • l: push
  • l: push
  • r: pop & +1
  • s: push
  • k: ?
  • r: broken
  • s: push
  • k: pop & +1

• k: broken

반드시 사전 기술을 사용한 직후에 본 기술을 사용할 필요는 없으며, 중간에 다른 기술을 사용하여도 연계는 정상적으로 이루어진다

LSRK -> 2가 되어야 한다는 의미

broken 이후에는 1~9가 와도 카운팅하지 않음

사고력: 알고리즘을 완전히 이해했는가? (충분한 사고력을 가졌는가?)

구현력: 알고리즘을 신속, 정확하게 구현했는가?