백준 [자바 java] 2138 : 전구와 스위치

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

처음에는 bfs로 풀어야하나 했는데 그렇게 하니까 너무 경우의 수가 많았다.

알고보니 그리디를 사용하는 문제였다.

앞에서부터 천천히 조건에 부합하기 위한 선택을 해나가면 된다.

 

그런데 0번 전구 스위치를 누르냐 마냐를 미리 결정하지 않으면 많이 복잡해진다.

따라서 나는 0번 스위치를 누르는 경우, 누르지 않는 경우를 나눠서 진행했다

 

풀이

char[] ori = br.readLine().toCharArray();
char[] com = br.readLine().toCharArray();

char[] nowOri = Arrays.copyOf(ori,n);

먼저 원래의 문자열과 바뀐 후의 문자열을 입력받는다.

처음에는 nowOri = ori 이런식으로 카피를 했는데 이렇게하면 두 배열의 주소가 같아져 결국 이름만 같은 하나의 배열이 된다.

따라서 배열을 복사하려면 Arrays.copyOf(배열명, 배열길이)를 사용하면 된다.

 

//0번 안누름
int cnt = 0;
for(int i = 1;i<n;i++){
  if(nowOri[i-1] != com[i-1]){
    for(int j = i-1;j<=i+1;j++){
      if(j >= n) break;
      if(nowOri[j] == '0'){
        nowOri[j] = '1';
      }
      else{
        nowOri[j] = '0';
      }
    }
    cnt++;
  }
  if(Arrays.equals(com,nowOri)){
    System.out.println(cnt);
    return;
  }
}

0번을 누르지 않는 경우이다.

현재 탐색중인 스위치의 바로 왼쪽 전구를 보고, 이 전구가 만들고자 하는 문자열과 같다면 스위치를 누르지 않고, 다르다면 스위치를 누른다.

 

여기서 원래는 원본과 완성해야하는 char배열을 둘 다 string으로 변환해서 비교했는데 그렇게 하니까 메모리초과가 났다.

Arrays.equals(1,2) 이 함수를 사용해서 하면 메모리 초과가 나지 않고 효율적이다

 

//0번 누름
cnt = 1;

nowOri = ori;
for(int j = 0;j<=1;j++){
  if(nowOri[j] == '0'){
    nowOri[j] = '1';
  }
  else{
    nowOri[j] = '0';
  }
}

for(int i = 1;i<n;i++){
  if(nowOri[i-1] != com[i-1]){
    for(int j = i-1;j<=i+1;j++){
      if(j > n-1) break;
      if(nowOri[j] == '0'){
        nowOri[j] = '1';
      }
      else{
        nowOri[j] = '0';
      }
    }
    cnt++;
  }

  if(Arrays.equals(com,nowOri)){
    System.out.println(cnt);
    return;
  }

}

0번을 눌렀을 때도 마찬가지의 방법으로 구현하였다.

System.out.println(-1);

나는 원본과 목표하는 배열이 같으면 바로 return을 통해 프로그램을 종료하도록 설계했기 때문에 만약 모든 코드를 다 돌고도 프로그램이 종료되지 않았다면 -1을 출력하도록 하였다.

 

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

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());

    char[] ori = br.readLine().toCharArray();
    char[] com = br.readLine().toCharArray();

    char[] nowOri = Arrays.copyOf(ori,n);

    //0번 안누름
    int cnt = 0;
    for(int i = 1;i<n;i++){
      if(nowOri[i-1] != com[i-1]){
        for(int j = i-1;j<=i+1;j++){
          if(j >= n) break;
          if(nowOri[j] == '0'){
            nowOri[j] = '1';
          }
          else{
            nowOri[j] = '0';
          }
        }
        cnt++;
      }
      if(Arrays.equals(com,nowOri)){
        System.out.println(cnt);
        return;
      }
    }
  

    //0번 누름
    cnt = 1;

    nowOri = ori;
    for(int j = 0;j<=1;j++){
      if(nowOri[j] == '0'){
        nowOri[j] = '1';
      }
      else{
        nowOri[j] = '0';
      }
    }

    for(int i = 1;i<n;i++){
      if(nowOri[i-1] != com[i-1]){
        for(int j = i-1;j<=i+1;j++){
          if(j > n-1) break;
          if(nowOri[j] == '0'){
            nowOri[j] = '1';
          }
          else{
            nowOri[j] = '0';
          }
        }
        cnt++;
      }
 
      if(Arrays.equals(com,nowOri)){
        System.out.println(cnt);
        return;
      }

    }

    System.out.println(-1);

  }
}

 

전체 코드이다.