Nirsa

문제 링크 : https://www.acmicpc.net/problem/1100

[백준] 1100번: 하얀 칸 (브론즈2, JAVA)

하얀 칸 위에 말(F)이 있는 칸이 몇개인지 찾는 문제인데, 예제 출력을 보면 아래와 같습니다.

해당 문제에서 첫번째(왼쪽 맨 위 / 0,0)는 하얀 칸으로 시작하고 그 다음부터 검은 칸이 한번씩 반복되는데, 해당 칸을 기준으로 옆 칸과 아래칸은 검은 칸이 됩니다. 화살표로 표시하게 되면 아래 처럼 되는데, 파란색이 하얀 칸이나 빨간 색이 검은 칸입니다.

아래 코드로 시작하여 체스판을 입력받고, for문을 통해 로직을 작성합니다. for문의 tempChar는 하얀칸 위에 있는 말을 확인하기 위해 입력받은 체스판을 char 배열로 만들어 줍니다.

public class Main {

	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] chessBoard = new String[8];
        for(int i=0; i<8; i++) {
        	chessBoard[i] = br.readLine();
        }
        
        int count = 0;
        
        for(int i=0; i<8; i++) {
        	
            // 로직 작성
            
        }
        System.out.println(count);
	}
}

for문 안의 로직은 아래와 같이 작성하는데, 홀수 라인의 경우(검은색으로 시작되는 라인) 짝수 번째가 하얀칸이므로 j를 1부터 시작하고 2씩 증가시켜 하얀 칸만 'F'가 있는지 확인하고 카운트 값을 증가 시킵니다.

그 다음의 짝수 라인의 경우(하얀색으로 시작되는 라인) 홀수 번째가 하얀칸이므로 k를 0부터 시작, 2씩 증가시켜 마찬가지로 하얀 칸만 'F'가 있는지 확인하고 카운트 값을 증가 시킵니다.

// 홀수 라인의 경우 짝수 : 하얀색, 홀수 : 검은색
if(i%2 == 1) {
    for(int j=1; j<8; j+=2) {
        if(tempChar[j] == 'F') { // 해당 라인의 짝수가 하얀색이면 count 증가
            count ++;
        }
    }
}

// 짝수 라인의 경우 짝수 : 검은색, 홀수 : 하얀색
if(i%2 == 0) {
    for(int k=0; k<8; k+=2) {
        if(tempChar[k] == 'F') { // 해당 라인의 홀수가 하얀색이면 count 증가
            count ++;
        }
    }
}

합친 코드는 아래와 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] chessBoard = new String[8];
        
        for(int i=0; i<8; i++) {
        	chessBoard[i] = br.readLine();
        }
        
        int count = 0;
        
        for(int i=0; i<8; i++) {
        	char[] tempChar = new char[8];
        	tempChar = chessBoard[i].toCharArray();
        	
        	if(i%2 == 1) {
        		for(int j=1; j<8; j+=2) {
        			if(tempChar[j] == 'F') {
        				count ++;
        			}
        		}
        	}
        	
        	if(i%2 == 0) {
        		for(int k=0; k<8; k+=2) {
        			if(tempChar[k] == 'F') { 
        				count ++;
        			}
        		}
        	}
        }
        System.out.println(count);
	}
}

[Algorithm] 시간 복잡도 정리

입력 제한에 따라 어떠한 알고리즘을 사용할지 정할 수 있는데 이는 아래와 같습니다.

1. n <= 20  : 웬만한건 모두 통과
   →  브루트포스 알고리즘
   → O(n!), O(2^n)
2. n <= 100 : 삼중 루프 가능
   → 폴로리드 와샬 알고리즘
   → O(n^3)
3. n <= 1000  : 이중 루프 가능
   → 벨만포트 알고리즘
   → O(n^2)
4. n <= 10000 : 알고리즘을 이용하여 풀어야 함
   → 동적 프로그래밍, 이분탐색, 다익스트라 알고리즘, 유니언 파인드, 세그먼트 트리, 투포인터
   → O(n), O(nlogn)
5. n <= 10^8
   → 유클리드의 호제법
   → O(logn)

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/72410

[프로그래머스 Lv1] 신규 아이디 추천

아래와 같은 단계들의 유효성 검사를 통과하며 문자열을 다루는 문제입니다.

1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.
     만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.

1~4 단계

toLowerCase()를 사용하여 1단계를 넘기고, 그 다음부터 정규표현식을 사용하여 2~4단계가 제거, 치환 됩니다.

new_id = new_id.toLowerCase()
               .replaceAll("[^a-z0-9-_.]","")
               .replaceAll("[.][.]+", ".")
               .replaceAll("^[.]|[.]$", "");

5단계

new_id가 비어있을 경우 a를 대입합니다.

if(new_id.equals("")) {
    new_id = "a";
}

6단계

조건식을 통해  new_id의 길이가 16 이상일 경우 15자로 짜르고, 만약 마지막 글자가 . 으로 끝난다면 14로 자릅니다. 14로 자르게 되면 마지막에 있던 .이 제거됩니다.

if (new_id.length() >= 16) {
    new_id = new_id.substring(0, 15);
    if(new_id.charAt(new_id.length()-1) == '.') {
        new_id = new_id.substring(0, 14);
    }
}

7단계

마지막으로 new_id의 길이가 3 미만일 경우 현재 길이를 담은 후 반복문을 실행합니다. i는 현재 문자열의 길이로 시작하고 i가 3이 될때까지 반복하며 마지막에 있던 문자를 넣습니다.

if(new_id.length() < 3) {
    int length = new_id.length();
    for(int i=length; i<3; i++) {
        new_id += new_id.charAt(new_id.length() - 1);
    }
}

문제 링크 : https://www.acmicpc.net/problem/14916

[백준] 14916번: 거스름돈 (실버5, 그리디 알고리즘, JAVA)

count 변수를 선언하여 최종적으로 출력한 동전의 최소 개수를 구합니다. while true를 사용하여 무한루프를 실행시키고, 각각의 조건식은 다음과 같습니다.

1. N%5 == 0 && N != 0
   5로 나누어 떨어지고, N이 0이 아닐 경우에는 count를 증가시키고 N에서 5를 감소시킵니다.
2. N/2 >= 1
   N의 값에서 2를 나눳을 때 최소 1번 이상 나누어질 경우 count를 증가시키고 N에서 2를 감소시킵니다.
3. N != 0
   N의 값이 0이 아닐 경우 -1를 출력하고 반복문을 종료합니다.
4. 그 외의 경우에는 N에 대한 모든 계산이 끝나고 나누어 떨어지는 경우이므로 count를 출력하고 종료합니다.

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 count = 0;
    	
    	while(true) {
    		if(N%5 == 0 && N != 0) { // 5원 거스름돈이 1번이상 가능할 때
    			count++;
    			N = N-5; // 5로 나누고나서의 나머지값을 저장
    		} else if(N/2 >= 1) { // 2원 거스름돈이 1번 이상 가능할 때
    			count++;
    			N = N-2; // 2로 나누고나서의 나머지값을 저장
    		} else if(N != 0) {
    			System.out.println("-1");
    			break;
    		} else {
    			System.out.println(count);
    			break;
    		}
    	}
    }
}