[Java]goorm test(구름TEST) 알고리즘 algorithm 사다리 타기

안녕하세요 Leo 입니다.

 

이번 소개해줄 알고리즘 사이트는 구름TEST 라는 사이트 인데요,

 

NHN에서 투자 받아 개발한 사이트 사이트 입니다.

 

회사면접 코딩테스트를 하는 유명한 사이트죠...

 

저는 IOS (Object-c , Swift) 위주로 개발을 하고 가끔 안드로이드 개발을 하는데요...

 

 

회사에서 Java 로 코딩테스트를 하라고 해서 ... 하라면 해야죠... 풀어봤습니다.

 

제가 20문제 이상 푼것 같은데 이걸 공유 해드리도록 하죠...

 

 

이 글이 누군가에겐 "약"이 되고 누군가에겐 "독"이 될 것이다.

개발자라면 적어도 기본 알고리즘 정도는 스스로 학습하여 풀어봐야 한다.참고로 코딩테스트 문제를 제출 한 심사위원 분도제 블로그에서 답을 확인 한다는 것을 역으로 알아두고 보세요!! ㅎㅎ

 

 

 

알고리즘 문제

 

문제 : 모두가 한 번쯤은 해봤을 사다리 타기 게임과 관련된 문제입니다.



이 사다리 게임을 조작해서 구름이가 원하는 모양으로 만들고자 합니다.

사다리를 가로 모양만 추가 또는 제거할 수 있으며 제거할 때 A, 추가할 때 B 만큼의 비용이 든다고 합니다.

이 경우에 출발점(a)에서 도착점(b)에 도착할 수 있도록 모양을 바꿀 때 필요한 최소 비용을 구하는 프로그램을 작성하십시오.



입력

첫 줄에 상하(세로) 사다리의 개수(n), 좌우(가로) 사다리의 개수(m)

다음 줄에 출발점, 도착점

다음 줄에 비용 A, B

다음 줄부터 위에서부터 가로 사다리에 대한 정보를 나타내는 정수(T)가 입력

*T는 T번과 T + 1번의 세로 사다리를 입력하는 가로 사다리

*위의 그림에 제시된 사다리는 n = 3, m = 6, T = 1, 1, 2, 2, 2, 1 인 사다리 입니다.

출력

최소 비용




입/출력 예시
⋇ 입출력 형식을 잘 지켜주세요.
␣ : 공백
↵ : 줄바꿈
−⇥ : 탭
보기 입력 1
3 6
1 1
3 1
1
1
2
2
2
1
출력 1
1

 

======================================================================================================

풀이

======================================================================================================

 

//Please don't change class name 'Main'

import java.util.Scanner;

class Main {

  public static void main(String[] args) {
		
		// n = 세로 사다리 Line 갯수
		// m = 가로 사다리 Line 갯수
		// T = 첫번째(1) 줄 개수만큼  두번째(2) 줄 개수만큼
		
		//도대체 어디가 출발(a) 고 도착(b)인걸까?....
		
		//첫번째 줄은 (n)세로 (m)가로 개수
		//두번째 줄은 출발(a) / 도착(b) 지점
		//세번째 줄은 A,B의 비용 (A:제거  B는:비용) 가로 사다리 그릴때 비용이 드는것!!
		//다음 줄 부터는 
		//1 : T + 1 첫번째 가로 사다리
		//2 : T + 2 두번째 가로 사다리
		
// 		3 6 (세로, 가로)
// 		1 1 (첫번째시작해서 첫번째로 끝나는 지점) 3개중에 1 2 3
// 		3 1 제거할때 3 / 추가할때 1비용이 든다
		// 여기 밑으로는 가로 줄 T + 1 / T + 2 첫번째 두번째 세로줄 연결시
// 		1
// 		1
// 		2 
// 		2
// 		2
// 		1
		
		//논리적으로 생각하면
		//전체라인은 6개 이다. 
		//규칙을 찾아냈다.
		//라인을 타는 횟수 마다 목표지점이 정해져있다
		//일단 총 6개라고 하면
		//1번시작 라인을 1번 타면 = 2
		//1번시작 라인을 2번 타면 = 3
		//1번시작 라인을 3번 타면 = 2
		//1번시작 라인을 4번 타면 = 1
		//1번시작 라인을 5번 타면 = 2
		//1번시작 라인을 6번 타면 = 3
		
		//계산 완료!!
		//계산방법!!
		//사다리 타기 조건 
		//첫번째 1 을 만나기 전 2는 무조건 삭제...
		//두번째 1 을 만나면 내가 초기화 1번째로 시작 1 + 1
		//세번째 1+1 = 2 / 2번 위치에 있음 1,2를 만나면 1을 만나면 -1 2를 만나면 +1
		//조건 현재 값보다 크면 +1 작으면 -1 
		
		//첫번째는 무조건 1로 시작 2는 다무시 1+1 2포시젼으로이동
		//두번째는 3포지션일때는 1로 점프를 못함.
		//세번째는 첫번째1이 아닌 1포지션은 2포지션을 못만남.
		
		//현재 포지션이 1,2,3 -> 1 + 1 = 2
		// 2 < 1 {
		// 	-1	
		// }else{
		// 	+1
		// }
		
		//결과가 1 이면 무조건 1을 만나야함
		//결과가 2 이면 1또는 2를 만남 1은 -1 2면 +1 
		//모든계산식이 끝나면 마지막 포지션 위치가 나옴 1,2,3 중에 
		
		Scanner scan = new Scanner(System.in);
		
		String size = scan.nextLine(); //세로, 가로
		String position = scan.nextLine(); //라인의 시작, 끝
		String payment = scan.nextLine(); //라인추가 비용 (제거,추가)에 대한 비용
		
		String[] sizeArr = size.split(" ");
		String[] positionArr = position.split(" ");
		String[] paymentArr = payment.split(" ");
		
		int  vertical = Integer.parseInt(sizeArr[0]);
		int  horizontal = Integer.parseInt(sizeArr[1]);
		
		int startPosition = Integer.parseInt(positionArr[0]);
		int endPosition =Integer.parseInt(positionArr[1]);
		
		int payDelete = Integer.parseInt(paymentArr[0]);
		int payInsert =Integer.parseInt(paymentArr[1]);
		
		//포지션 2이면 1이 들고 3이면 2가 든다 추가 비용
		//첫번째 줄은 (n)세로 (m)가로 개수
		//두번째 줄은 출발(a) / 도착(b) 지점
		//세번째 줄은 A,B의 비용 (A:제거  B는:비용) 가로 사다리 그릴때 비용이 드는것!!
		//다음 줄 부터는 T 값은 T + 1 값 계산 여기서 현재 포지션을 갖는게 중요하다.
		int thisPoint = 1;
		for(int j=0; j< horizontal; j++){//가로 라인을 그린다.
					
				int line = scan.nextInt();
				if(line > vertical - 1) return; //입력값이 세로줄이 3개인데 2보다 크면 프로그램 종료.
			
				if(j == 0){ //무조건 첫번째 값에 대한 공식 시작지점과 다르면 라인을 못그리고 내려간다.
					if(line != startPosition){ //첫번째는 StartPosition이 아니면 라인을 그릴 수 없다. startPosition 1 이면 무조건 1을 만나야함
						continue;	 //시작은 무조건 1부터 
					}else{
						thisPoint++; //postion 2로 이동
					}
				}else{
					
					//2중간이면 어디든 갈 수 있다 1 / 2
					//1또는 3일때는 같은 값만 이동 가능하다.
					if(thisPoint == 2){ //가운데 2이면 어느 방향이든 움직일 수 있다. 1 or 3
						if(thisPoint > line){ //입력된 라인이 1이면 -1 2이면 +1 움직인다
							thisPoint--;	
						}else{
							thisPoint++;	
						}
					}else if(thisPoint == line){ //만약 1,3 위치에 있다면 같은 라인을 만나야지만 라인을 탄다!!
							thisPoint++;
					}
					
					
				}

		}
		
		//도착 포지션을 구했다 이제 마지막 값을 구한다.
		//최소값을 구한다.
		//입력된 A,B 의 최소값을 구해서 제거 하는게 최소값이면 + 시켜버리고
		//추가하는게 최소값이면 - 를 한다!!
		
		//최소비용을 구한다. A, B 중에 더 싼걸 찾는다.
		int minPay = 0;
		if(payDelete < payInsert){
				minPay = payDelete;
		}else{
				minPay = payInsert;
		}
		int lineDistance = 0;
		//거리계산 라인으로 부터 도착지점의 거리!! 
		if(thisPoint < endPosition){
			lineDistance =  endPosition - thisPoint;
		}else{
			lineDistance = thisPoint - endPosition;
		}
			
		int totalPay = 0; //돈이 안들어가면 0원으로 찍힘
		if(lineDistance > 0){
				totalPay = lineDistance * minPay;
		}
		
		
		
		System.out.println(totalPay);
		
// 		for(int i=0; i < vertical; i++){ //세로를 그린다.
			
// 			System.out.println(" i : " + i);
			
			
// 		}
		
  }
}

 

 

참고로 저는 알고리즘 풀이 점수는 높은 점수는 아닙니다. 

 

일단 푸는 거에 집중했습니다.  알고리즘에 정답은 없습니다.

 

더 좋은 알고리즘을 만들어 내는게 목표 입니다.

 

 

알고리즘에 대하여 더 이야기 하실분은 댓글남겨주세요!

 

 

 

 

 

 

 

구름TEST 화면

 

 

 

 

https://codingtest.goorm.io/

구름TEST - 개발자 채용을 위한 코딩 테스트, 프로그래밍 시험

 

구름테스트, 구름TEST 가 지원하는 프로그래밍 언어

 

그 외 Scala, Pascal, Lua, Objective-C, Rust, Cobol, Clojure, Smalltalk, Dart, Haskell, Perl, Common Lisp, D, Erlang 등 

 

 

 

구름테스트, 구름TEST 를 2019년 현재 적용중인 회사