[백준] 27210. 신을 모시는 사당 JAVA

27210번: 신을 모시는 사당

---

💝 문제

신을 모시는 사당에는 신을 조각한 돌상 N개가 일렬로 놓여 있다. 각 돌상은 왼쪽 또는 오른쪽을 바라보고 서있다. 창영이는 연속한 몇 개의 돌상에 금칠을 하여 궁극의 깨달음을 얻고자 한다.

궁극의 깨달음을 얻기 위해서는 가능한 한 많은 금색 돌상들이 같은 방향을 바라보아야 한다. 방향이 다른 돌상은 깨달음에 치명적이다. 깨달음의 양은 아래와 같이 정의된다.

| (왼쪽을 바라보는 금색 돌상의 개수) - (오른쪽을 바라보는 금색 돌상의 개수) |

창영이는 궁극의 깨달음을 얻을 수 있을까?

---

💝 예시

---

💝 풀이 설명

• 이 문제는 제한시간이 존재하는 문제였다.
• 그래서 반복문을 중첩해서 사용하거나, 재귀를 사용하면 시간초과가 발생했다.
• 그래서 다른 방식으로 풀었다.
• 우선 시간을 조금이라도 단축시키고자 BufferedReader를 사용하였다.
• 돌상의 개수를 n에 넣어주었다.
• 양수를 더할 sum과 음수를 더할 sub을 선언하고 초기화 시켜주었다
• 가장 큰 양수값을 저장할 max와 가장 작은 음수값을 저장할 min을 선언하고 초기화 시켜주었다.

 

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

      int n = Integer.parseInt(br.readLine());
      int sum = 0;
      int sub = 0;

      int max = 0;
      int min = 0;
      
   }
}

---

• 불상이 바라보는 방향값을 받은 후, 계산이 편하도록 2를 -1로 바꾼 후 String 배열에 담아주었다.
• 불상의 개수만큼 반복문을 돌면서 값들을 더해주었다.
• 그리고 가장 작은 값의 절댓값과 가장 큰 max 값을 비교하여 큰 값을 출력시켜주었다.

 

public class Main {
   public static void main(String[] args) throws IOException {
      
      ...
      
      String[] arr = br.readLine().replaceAll("2", "-1").split(" ");

      for (int i = 0; i < n; i++) {
         sum = Math.max(sum, 0) + Integer.parseInt(arr[i]);
         sub = Math.min(sub, 0) + Integer.parseInt(arr[i]);

         max = Math.max(sum, max);
         min = Math.min(sub, min);
      }

      max = Math.max(max, Math.abs(min));

      System.out.println(max);
   }
}

---

🦄 최종 풀이

 

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

      int n = Integer.parseInt(br.readLine());
      int sum = 0;
      int sub = 0;

      int max = 0;
      int min = 0;
      String[] arr = br.readLine().replaceAll("2", "-1").split(" ");

      for (int i = 0; i < n; i++) {
         sum = Math.max(sum, 0) + Integer.parseInt(arr[i]);
         sub = Math.min(sub, 0) + Integer.parseInt(arr[i]);

         max = Math.max(sum, max);
         min = Math.min(sub, min);
      }

      max = Math.max(max, Math.abs(min));

      System.out.println(max);
   }
}​

---