[Algorithm] 백준 문자열 문제 - 염색체(9342) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 문자열 문제 - 염색체 자바 풀이를 진행하고자 합니다.

 

문제 출처: https://www.acmicpc.net/problem/9342

9342번: 염색체

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        Solution solution = new Solution();
        for (int i = 0; i < t; i++) {
            solution.setStr(br.readLine());
        }

        System.out.print(solution.getStr());
    }
}

class Solution {

    List<String> strs = new ArrayList<>(); // 문자열 저장 리스트

    void setStr(String str) {
        strs.add(str);
    }

    String getStr() {
        StringBuilder sb = new StringBuilder();
        boolean isInfected; // 조건에 맞는지 판단

        for (String str : strs) {
            isInfected = true;

            if (str == null || str.length() < 3) { // 문자가 null이거나 3개보다 작다면 조건 만족 불가능
                sb.append("Good!").append("\n");
                continue;
            }

            int flag = 0; // 0: A, 1: F, 2: C 3: C가 문자 한 개
            for (int i = 1; i < str.length(); i++) {
                char c = str.charAt(i);

                if (flag == 3) { // 만약 flag == 3인 조건이 true라면 끝에 문자가 하나가 아니라는 것
                    isInfected = false; // 조건 만족 불가
                    break;
                }

                else if (flag == 0) { // A 문자가 유지되는 중
                    if (c == 'F') { // F가 나왔다면 flag++
                        flag++;
                    }
                    else if (c != 'A') { // F와 A가 아니라면 조건 불만족
                        isInfected = false;
                        break;
                    }
                } else if (flag == 1) { // F 문자 유지되는 중
                    if (c == 'C') { // C가 나왔다면 flag++
                        flag++;
                    }
                    else if (c != 'F') { // C와 F가 아니라면 조건 불만족
                        isInfected = false;
                        break;
                    }
                } else if (flag == 2) {  // C 문자 유지 중
                    if (c != 'C') {
                        if (c == 'A' || c == 'B' || c == 'D' || c == 'E' || c =='F') flag++; // 마지막 문자 한 개가 되어야 함
                        else {
                            isInfected = false;
                            break;
                        }
                    }
                }
            }
            if (isInfected && (flag == 2 || flag == 3)) {
                sb.append("Infected!").append("\n");
            } else {
                sb.append("Good").append("\n");
            }

        }

        return sb.toString();
    }
}

 

2. 풀이 중점 사항

 

각 조건은

'첫 번째 문자 -> A -> F -> C -> 끝 문자 혹은 종료'의 순서로 순차적으로 진행되게 됩니다.

따라서, O(n)로 문제를 해결할 수 있었습니다.

flag를 int 타입으로 선언하여, 각 문자를 한 번 순회하면서 같은 문자라면 flag 유지하고,
조건에 맞도록 다음 문자가 이어지면 flag가 변경될 수 있도록 하였습니다.

 

다소 헷갈릴 수 있는 부분은 규칙을 지키는 경우에 Infected!를 출력해야 한다는 점입니다.!

이상으로 백준 염색체 자바 풀이를 마치도록 하겠습니다. 감사합니다!!