KB IT’s Your Life 4기 - Java 알고리즘 6일차

시간복잡도: 연산횟수

  • 빅오메가: 최선
  • 빅세타: 보통
  • 빅오: 최악

보통 수행 시간은 1억 번의 연산을 1초의 시간으로 간주

시간복잡도 설명

코딩테스트 연습

  1. 정올
  2. 백준
  3. SWEA +) 프로그래머스, 코드트리

배열

  • 배열이란? 연속적인 메모리 공간 (삽입, 삭제가 어려움)
  • 리스트란? 값과 포인터를 묶은 노드 (검색이 느림)

디버거

  • 소스작성 완료
  • break point 설정 (줄번호 dbClick): 디버거 실행 중단점
  • 디버거 실행(F11)
  • 입력값 넣고 엔터
  • 브레이크 포인트에서 중지(실행할 줄)
  • F5: Step Into(메서드인 경우, 메서드 안으로 들어가서 한 줄씩 실행)
  • F6: Step Over(메서드 실행할 경우 메서드실행하고 다음줄로 이동)
  • 우측의 Variables 탭에서 변수명과 값을 확인

구간 합 구하기

(합배열S, 배열A)

  • 합배열을 만든다.: S[i] = S[i-1] + A[i]
  • 구간합공식 : S[j] - S[i-1]
package b11659;

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

/** 구간 합 구하기 */
public class Main {

	public static void main(String[] args) throws IOException {
		//숫자 입력 받기
		//		Scanner scanner = new Scanner(System.in);
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		//숫자 개수
		//int N = scanner.nextInt();
		int N = Integer.parseInt(stringTokenizer.nextToken()); 
		//합을 구해야하는 횟수
		//int M = scanner.nextInt();
		int M = Integer.parseInt(stringTokenizer.nextToken()); 
		//N개를 담는 숫자 배열
		//int[] arr = new int[N+1]; //문제에서 배열이 1부터 시작하기 때문에
		long[] arr = new long[N+1];
		stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		for(int i = 1; i<arr.length; i++) {			
			//arr[i] = scanner.nextInt();
			//합배열저장
			arr[i] = arr[i-1]+Integer.parseInt(stringTokenizer.nextToken());
		}	
		//M개의 i~j받아오기
		for(int q=0; q<M; q++) {
			stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			int i = Integer.parseInt(stringTokenizer.nextToken());
			int j = Integer.parseInt(stringTokenizer.nextToken());			
			System.out.println(arr[j]-arr[i-1]);
		}	
	}
}

BufferedReader

  • S.in은 입력마다 처리한다. > 느려진다.
  • BufferedReader는 내부에 버퍼를 가짐. byte배열로 되어있고 내부적으로 버퍼링해서 처리횟수가 줄어든다.

BufferedReader의 readline이 한 줄을 통째로 읽는다. (ns단위로 움직임. 아주 빠름)

  • StringTokenizer가 공백문자를 기준으로 문자를 분할한다. (공백, 탭, 엔터,,,)
  • nextToken으로 잘라 놓은 애들 전달
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer - new StringTokenizer(bufferedReader.readLine());

int N = integer.parseInt(stringTokenizer.nextToken());
int M = integer.parseInt(stringTokenizer.nextToken());

// 다음 저장할 때,
stringTokenizer - new StringTokenizer(bufferedReader.readLine());

int i = integer.parseInt(stringTokenizer.nextToken());
int j = integer.parseInt(stringTokenizer.nextToken());

한 줄씩 모두 처리해주어야함!!!

예외

  • public static void main(String[] args) throws IOException
  • 자바 예외(Exception) - 예외 발생시 메서드 실행 종료 오류
    • 가벼운 오류: Exception 전처리를 통해 예방가능(if…) NullPointerException(변수에 null이 있을 때 객체의 메서드를 호출하는 경우)
    • 심각한 오류: 전처리로 예방 불가능한(Error StackOverFlowError…)
  • 일반적인 예외 (Exception)
  • 실행시 예외 (RuntimeException)
public void a(){
   new FileReader("a.txt") // 1. 파일 존재, 2. 파일 없음
   //1. 오류 발생 시 호출 메서드에게 안 알려주고 내부 처리. (try{...}catch(Exception){...})
   //2. 호출한 메서드에게 오류 발생을 알림. public void a() throws Exception{...}

br.readLing(); // 이 아이때문에 throws IOException이 발생할지도 모른다는 선언을 해주는 것이 필요함. (try catch로 처리해도됨)
}

이차원 배열 - 지뢰찾기 게임

package 배열리뷰;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class 지뢰빨리찾기 {
	public static void main(String[] args) throws IOException {
		/*
		 * 10*10 좌표에 10개 임의의 위치에 지뢰를 매설 사용자는 행, 열 좌표를 입력 (1~10, 1~10) 해당 좌표가 지뢰이면 X표시
		 * 아미녀 주위 8칸 내 지뢰개수 표시 열리지 않은 좌표는 + 표시
		 */

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		// 1. 12*12 정수 배열 생성
		// 10*10인데 12*12 배열을 만드는 이유? 좌표0이 없기 때문에 size를 1 키우고, 좌표 10에서 무언가를 할 때, 버퍼가 필요해서
		// size를 1 키워서 총 2씩 키워야한다.
		int[][] mine = new int[12][12];
		boolean[][] open = new boolean[12][12]; // +) 좌표의 오픈 여부 지정

		// 2. 중복되지 않는 10개 좌표 생성
		ArrayList<Integer> nums = new ArrayList<Integer>();
		for (int i = 0; i < 100; i++) {
			nums.add(i + 1); // 1~100까지를 더함.
		}
		// 3. 각 좌표에 9 저장. 주위 8개에 1씩 증가
		// 4. 반복
		for (int i = 0; i < 10; i++) {
			int r = (int) (Math.random() * nums.size()); // 0~99 난수
			int num_r = nums.remove(r); // r을 지움과 동시에 num_r에 넣는다.
			int x = num_r / 10 + 1; // 만약 r(=num_r)이 88이라면, x는 9이다.
			int y = num_r % 10 + 1; // 만약 r(=num_r)이 4라면, y는 5이다.

			mine[x][y] = 9; // 지뢰 10개를 세팅함. (뽑아낸 좌표에 9를 입력)

			mine[x - 1][y]++;
			mine[x - 1][y + 1]++;
			mine[x][y + 1]++;
			mine[x + 1][y + 1]++;
			mine[x + 1][y]++;
			mine[x + 1][y - 1]++;
			mine[x][y - 1]++;
			mine[x - 1][y - 1]++;
		}

//		for(int i = 0; i<12; i++) {
//			for(int j =0; j <12; j++) {
//				System.out.print(mine[i][j]+" ");
//			}
//			System.out.println();
//		}
//		

		// 9. 지뢰 10개를 다 찾으면 종료. 아니면 5번부터 반복
		int count = 0;
		
		while (count != 10) {
			// 5. 사용자로부터 좌표 입력(행, 열)
			StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine()); //해당 코드도 while문 안에 두어야 오류가 발생하지 않음.

			int userX = Integer.parseInt(stringTokenizer.nextToken());
			int userY = Integer.parseInt(stringTokenizer.nextToken());

			// 6. 해당좌표의 값이 9 이상이면 "지뢰찾음" 출력
			// 7. 해당좌표가 9미만이면 "지뢰아님" 출력
			open[userX][userY] = true;

			if (mine[userX][userY] >= 9) {
				System.out.println("지뢰찾음");
			} else {
				System.out.println("지뢰아님");
			}

			// 8. 전체 배열 출력( +: 오픈 안한 좌표, 숫자: 지뢰아닌곳, X: 지뢰)
			for (int i = 1; i < 11; i++) {
				for (int j = 1; j < 11; j++) {
					if (open[i][j]) {
						System.out.print((mine[i][j] >= 9) ? "X " : mine[i][j] + " ");
						count += (mine[i][j] >= 9) ? 1 : 0;
					} else {
						System.out.print("+" + " ");
					}
				}
				System.out.println();
			}

		}
	}
}