모각소 1주차 활동(SCPC 이진수 자바 풀이)

SCPC 7회 예선 이진수 문제
이진수 문제 바로가기

알고리즘: 그리디

아이디어

B 배열의 처음부터 t개, 끝에서부터 t개는 A 배열 1개만 관련된 부분이므로 0과 1이 확정되는 부분이 있는데 여기를 먼저 채워준다.

      for(int i = 1; i <= t; i++){
          //B 배열 끝에서부터 세는 변수 j
          int j = n - i + 1;
          if(i+t <= n){
              A[i+t] = B[j];
          }
          if(j-t >= 1){
              A[j-t] = B[j];
          }
      }

B 배열에서 0인 index는 A 배열의 index+t, index-t도 0으로 확정되므로 이 부분도 채워준다.

 		for(int i = 1; i <= n; i++) {
            	if(B[i] == 0) {
            		if(i-t >= 1) {
            			A[i-t] = 0;
            		}
            		if(i+t <= n) {
            			A[i+t] = 0;
            		}
            	}
       	}

B 배열을 처음부터 끝까지 순회하면서 i번 째 값이 1일 때 A 배열의 i-t, i+t 중 하나 이상이 1이 되야하고 A 값이 최소가 되야한단 점을 생각해서 채워준다.

	for(int i = 1; i <= n; i++) {
           	if(B[i] == 0) {
           		continue;
           	}
           	else {
           		if(i-t >= 1 && A[i-t] == 1) {
           			continue;
           		}
           		else if(i+t <= n && A[i+t] == 1) {
           			continue;
           		}
           		else {
           			if(i+t <= n && A[i+t] != 0) {
           				A[i+t] = 1;
           			}
           			else {
           				A[i-t] = 1;
           			}
           		}
           	}
    }

자바 스킬

• scanner 모듈의 nextLine 함수 이용할 때 전에 입력한 엔터나 스페이스 같은 것을 buffer로 처리해줘야 정상적으로 한 줄 입력받을 수 있다

	// 입력 버퍼 처리!
	 String buffer = Scanner.nextLine();
     String userInput = new String();
     userInput = Scanner.nextLine();

• 문자열을 입력받아서 숫자열로 만들고 배열에 넣기

	String userInput = Scanner.nextLine();
    for(int i = 0; i < userInput.length(); i++){
    	array[i] = userInput.charAt(i) - '0';
    }