[8주차_화요일] 염색체

[baexxbin]

• 사이트 : 백준(BOJ)
• 문제: 염색체
• 번호: 9342

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• 최대 200개의 알파벳 대문자
• 시간 제한사항이 2초이므로 따로 고려하지 않았음

💡 풀이 아이디어

• 조건에 맞는 정규표현식을 작성

  String regex = ^[ABCDEF]?A+F+C+[ABCDEF]?$

  • ^: 문자로 시작하는
  • [문자들]: 내부 문자들 중 아무거나
  • ?: 0개 혹은 1개
  • +: 1개 이상
  • $: 문자로 끝나는
• 정규표현식과 문자열이 매치되는지 확인

  boolean infected = Pattern.matches(regex, str);

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 문자열
• 시간복잡도: T ≤ 20, 최대 200개의 알파벳 대문자
• 완전탐색 가능 20*200*5

💡 풀이 아이디어

문제에서 제시한 5개의 조건을 모두 구현하고, 각 문자가 올바르게 배치되어 있는지 전역변수 order로 charAt(order) 문자를 하나씩 확인

• 문자열은 {A, B, C, D, E, F} 중 0개 또는 1개로 시작해야 한다.
  • {A, B, C, D, E, F} 에 포함되지 않는다면 GOOD
• 갯수에 상관없이 A - F - C 순서를 유지해야한다.
  • 순서가 유지되지 않는다면 GOOD
• 그 다음에는 {A, B, C, D, E, F} 중 0개 또는 1개가 있으며, 더 이상의 문자는 없어야 한다.
  • {A, B, C, D, E, F} 에 포함되지 않는다면 GOOD
  • 포함하지만 1개 이상의 문자가 있다면 GOOD
• "AFC" 는 예외케이스로 별도로 조건문 처리

[KodaHye]

🤔 시간복잡도 고려사항

• 테스트케이스 개수 <= 20
• 알파벳의 최대 길이: 200

시간 넉넉함!

💡 풀이 아이디어

• 정규식 사용
• 문자열 시작, 끝, 중간 문자열의 조건을 정규식을 사용한다면 복잡하게 구현하지 않아도 될 것이라 생각함

s.matches("^[ABCEDF]?A+F+C+[ABCDEF]?$"

정규식이 익숙해질 때까지 연습해봐야겠어요 ㅎㅎ!

[baexxbin]

🤔 시간복잡도 고려사항

• 테스트케이스 개수(T) <= 20
• 알파벳의 최대 길이: 200
• 완전탐색 가능

💡 풀이 아이디어

• idx: 현재 체크하는 알파벳 위치
• 처음 조건 check1()
  • lst에 포함되는 알파벳일 경우 idx++
  • 이때, A로 시작할 경우, 이미 앞에 A가 붙어있다고 생각하고 진행 (0이될 수도 있는 조건)
• 중간 조건 check2()
  • 특정 알파벳이 1개 이상 존재해야 함.
  • idx와 특정 알파벳이 같은 개수 세기 cnt++
  • cnt가 0보다 크다면 조건 만족

    idx는 전역변수로, 올바른 Idx값이 들어가도록 중간 조건들을 순차적으로 확인

• 마지막 조건
  • if (idx==chars.length || (idx==chars.length-1 && check1(chars[idx])))
  • 조건에 주어진대로 구현

[yeongleej]

🤔 시간복잡도 고려사항

• 테스트케이스 : T <= 20
• 문자열 길이: 200 => 완전탐색 가능

💡 풀이 아이디어

• 재귀로 각 조건 만족여부에 따라 순차 진행
• 첫번째 조건 : {A, B, C, D, F}으로 시작
  • A로 시작하면 인덱스 증가 X
• A, F, C로 시작하는 조건
  • 해당 알파벳과 다른 알파벳이 나올 때까지 탐색
  • 인덱스가 증가되어서 1개이상 존재한다면 계속 진행
• 마지막 조건 : {A, B, C, D, F} 0개 or 1개
  • 마지막 인덱스이거나 끝났다면 isOk = true

정규식으로 푸는 문제였군요!! 오늘 정규식 공부합니다! 진짜!! ㅎㅎㅎㅋㅋ

[icegosimperson]

🤔 시간복잡도 고려사항

• T(테스트 케이스) : 20, 문자열 길이 200
• 주어진 조건으로 구현 가능

💡 풀이 아이디어

• 정규식 : 특정 문자열 패턴을 쉽게 파악할 수 있는 도구
  • 문자열이 일정한 규칙을 따르는지 검사할 때 유용!
  • 조건 1) [ABCDEF] 중 0개 or 1개로 시작 : ^[ABCDEF]?
  • 조건 2) A, F, C 하나 이상 반복 : A+F+C
  • 조건 3) 문자열 끝이 [ABCDEF]?$ 중에 0개 or 1개

    String str = "^[ABCDEF]?A+F+C+[ABCDEF]?$"; 

    Stack으로 풀다가 정규식으로 푼다는 충격적인 사실을 발견했습니다 정규식 처음 보는데 신기하네요,,!!! 스터디의 순기능 ㅎㅅㅎ