[알고리즘공부/이것이 코딩테스트다] 구현

 

구현: 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정

 

구현하기 어려운 문제란?

- 알고리즘은 간단하지만 코드가 지나칠만큼 길어지는 문제

- 특정 소수점 자리까지 출력해야하는 문제

- 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제

 

1. 완전탐색 유형

- 모든 경우의 수를 주저없이 다 계산하는 해결 방법

[예시 4-2] 시각 (난이도 하, 풀이시간 15분)

정수 N을 입력받아 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램

package CodingTest;
 
import java.util.Scanner;
 
public class implementation_113 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int hour = sc.nextInt(); //시간입력
        int count = 0;
 
        for(int h=0; h<hour+1; h++) {
            for(int m=0; m<60; m++) {
                for(int s=0; s<60; s++) {
                    if( (Integer.toString(h) + Integer.toString(m)+ Integer.toString(s)).contains("3") ) {
                        count++;
                    }
                }
            }
        }
        
        System.out.print(count);    
    }
}
 

 

2. 시뮬레이션 유형

- 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

[예시 4-1] 상하좌우 (난이도 하, 제한시간15분)

NxN 좌표에서 상하좌우(U/D/L/R)로 이동할 때 최종 좌표를 구하는 문제

package CodingTest;
 
import java.util.Scanner;
 
public class implementation_110 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt() ; //공간의크기
        sc.nextLine();
        
        //이동계획입력
        String move = sc.nextLine();
        String[] plan = move.split("");
        
        //좌표 초기화
        int x=1;
        int y=1;
        
        for(int i=0; i<plan.length; i++) {
            if("L".equals(plan[i])) {
                y -= 1;
                if(y==0) y+=1;
            }else if("R".equals(plan[i])){
                y += 1;
                if(y==N+1) y-=1;
            }else if("U".equals(plan[i])){
                x -= 1;
                if(x==0) x+=1;
            }else if("D".equals(plan[i])){
                x += 1;
                if(x==N+1) x-=1;
            }
        }
                
        System.out.printf("%d,%d", x,y);
         
    }
 
}
 

난이도 '하'에 15분 안에 풀어야하는데,,, 처음에 이차배열 + switch문으로 접근했다가 구현이 제대로 안되고...ㅠ 거의 한시간은 걸려서 풀었다 흑흑 ㅠㅠ