수테크📱⌚️👀

문제 😵‍💫

독일 로또는 {1, 2,...,49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1, 2, 3, 5, 8, 13, 21, 34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다.

{[1, 2, 3, 5, 8, 13], [1, 2, 3, 5, 8, 21], [1,2,3,5,8,34], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램ㅇ을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 이싿. 각 테스트 케이스는 한 줄로 이루어져 있다, 첫 번째 수는 k(6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

내 풀🦷

# 6603. 로또
def backtracking(depth, beginwith):
    if depth == 6:
        print(*result)
        return

    for i in range(beginwith, k):
        if not visited[i]:
            result[depth] = nums[i]
            backtracking(depth+1, i+1)
            visited[i] = False


while True:
    lotto = list(map(int, input().split()))
    k = lotto[0]
    nums = lotto[1:]
    result = [0] * 6
    visited = [False] * k
    backtracking(0, 0) // 깊이, 어디서 부터 시작할건지

    if k == 0:
        quit()
    print()

N과 M으로 다진 백트래킹 개념을 다른 문제에도 적용시키고 싶어서 로또라는 문제를 풀어보았습니다!!!!

어려웠던 점....

1. 테스트 케이스마다 한줄 뛰우는걸 어떻게 하지....

2. 마지막 0이 나왔을 때 종료를 어떻게 하지...

3. 테스트 케이스의 수가 안주어졌는데 어떻게 하지...

백트래킹 개념적인부분 보다는 다른것들에 더 시간을 많이 잡아먹었다....

순,조에 대한 개념은 👇👇👇

https://jeniffer0812techstory.tistory.com/94

참고하면 좋을 개념들 ✍️

• exit() : 프로그램 강제 종료

for i in range(100):
    if i == 5:
        quit()
    print(i)
    
/* 
0
1
2
3
4
*/

이번주 자바 비전공 강의 + 프로그래머스 문제 풀면서 헷갈리고 잘 모르는것들 정리 해보았습니다😂😂

1. 문자열 정수 변환 (파이썬은 정말 간단한데요...ㅜㅜ 사실 자바도 그리 복잡하진 않음 )

• Interger.valueOf() 메서드 사용 

// 프로그래머스. 이어붙인 수
// new_정수 = Integer.valueOf(문자열) 

class Solution {
    public int solution(int[] num_list) {
        int answer = 0;
        String even = "";
        String odd = "";
        for (int i = 0; i < num_list.length; i ++){
            if (num_list[i] %2 == 1) {
                even += num_list[i];
            }else {
                odd += num_list[i];
            }
        }
        answer += Integer.valueOf(even) + Integer.valueOf(odd);
        return answer;
    }
}

• Integer.parseInt() 메서드 사용

  String str ="30";

  int i = Integer.parseInt(str);  

  System.out.println(i); // 30

둘의  차이점은...
valueOf() 메소드는 문자열의 값을 정수형으로 변환한 뒤 참조 자료형(Reference Type)인 Integer 객체로 만들어서 반환합니다.
parseInt() 메소드는 결과값을 기본 자료형(Primitive Type)인 int 로 반환합니다.

결과를 기본 자료형으로 받아오고 싶을 때는 parseInt() 를, 참조 자료형 Integer 객체로 받아오고 싶을 때는 valueOf() 를 사용하면 됩니다

아직 객체를 못 배워서 그런거라고 생각하고 정진... 하지만 그래도 아시는 자바 고수님 덜 좀 알려주세요...

2. 정수를 문자열로 변환(많음 주의...;;;;!!!)

• Integer.toString()

// 1. Integer.toString() 메서드 사용하기 
// 문자열 = Integer.toString(정수)

public class IntToString {
    public static void main(String[] args) {
        int intValue1 = 0812;
        int intValue2 = 8888;
 
        String str1 = Integer.toString(intValue1);
        String str2 = Integer.toString(intValue2);
 
        System.out.println(str1);
        System.out.println(str2);
    }
}

• String.valueOf()

// 2. String.valueOf()
// 문자열 = String.valueOf(정수)

public class IntToString {
    public static void main(String[] args) {
        int intValue1 = 0812;
        int intValue2 = 8888;
 
        String str1 = Integer.valueOf(intValue1);
        String str2 = Integer.valueOf(intValue2);
 
        System.out.println(str1);
        System.out.println(str2);
    }
}

• int + ""

// 3. int + "" (제일 간단하고 좋네요^^"")
// 문자열 : int + ""

public class IntToString {
    public static void main(String[] args) {
        int intValue1 = 0812;
        int intValue2 = 8888;
 
        String str1 = intValue1 + "";
        String str2 = intValue2 + "";
 
        System.out.println(str1);
        System.out.println(str2);
    }
}

3. for each(개선된 for 문)

: 장점 : 간편성, 가독성 좋은 코드... 배열 인덱스 문제 해결

: 단점 : 인덱스를 사용하지 못한다.. 수정 노우 ㅜ

// for each

// 동작
for(자료형 변수명 : 배열명) {
	문장
}

// 예시
int nums = [1, 2, 3, 4]
for (int num : nums) {
	System.out.println(num);
}
// 1
// 2
// 3
// 4

언젠가 for문 을 쓰는게 능숙해지면 이 방법으로도 써봐야겠다 😊

4. charAt() 메서드

: 문자열에서 문자 하나하나를 추출할 수 있는 메서드!!

// .charAt()
// .charAt(인덱스)

String str = "안녕하세우";
char ch1 = str.charAt(0);
char ch2 = str.charAt(1);
char ch3 = str.charAt(2);

System.out.println(ch1); // 안
System.out.println(ch2); // 녕
System.out.println(ch3); // 하

5. == 과 .euqlas()의 차이

•  == 연산자 : 비교하고자 하는 두개의 대상의 주소값을 비교
• equals 메소드 : 비교하고자 하는 두개의 대상의 값 자체를 비교
  
  

아직 클래스, 상속 파트를 안 배워서 정확한 차이 구별이 안된다...

프로그래머스 문제를 풀다가 ==으로 아무리 해도 문제가 안 풀리길래 구글링을 했는데 다들 equals를 사용하셨다..

equals()가 값을 비교하니까 문자열을 비교할 때 만큼은 == 연산자보다는 나을것이라 생각하기로 했다 일단은.. 

다른분 블로그에서 퍼왔다... 주소 남깁니다...

https://sudo-minz.tistory.com/93

6. 자바 문자열 한글자씩 배열에 저장하기

// Split 함수를 활용하여 단어를 배열에 저장하기

class Solution {
    public int solution(String number) {
        int answer = 0;
        int sum_number = 0;
        
        String[] nums;                // String을 담을 배열 만들어주기
        nums = number.split("");      // 배열에 한글자씩 저장하기
        for (int i = 0; i < number.length(); i++){ // for문으로 하나씩 돌리면서 값 저장하기
            sum_number += Integer.parseInt(nums[i]);
        }
        answer = sum_number % 9;
        return answer;
    }
}


// charAt 함수를 활용하여 단어를 char 배열에 한글자씩 저장하기

char[] num = new char[number.length()]; // String을 담을 배열 만들기
for (int i = 0; i < num.length; i++) {
	num[i] = numver.charAt(i);
}

7. 문자열 만들기(+연산이 많아진다면 성능적으로 좋지 않다) => StringBuilder

// 문자열 만드릭 :StringBuilder

public class Main {
	public static void main(String[] args) {
    	StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append('문자열").append("연결"); // 한번에 두개 append 가능
        // String str = stringBuilder; // String에 StringBuilder를 그대로 넣을 수는 없은  toString()을 붙여야 한다
        String str = stringBuilder.toString();
        System.out.println(stringBuilder); // 문자열연결
        System.out.println(str); // 문자열연결
    }
}

1. if 문

1) if 문과 else 문의 기본 구조

- if 문 : 주어진 조건이 참일 때 실행되는 코드

- else 문: if 문의 조건이 거짓일 때 실행되는 코드

if (조건문) {
	<수행할 문장>;
    <수행할 문장2>;
} else {
	<수행할 문장3>;
    <수행할 문장4>;
}

2) 비교 연산자

// 돈이 3000원 이상 있으면 택시, 아니면 걷기
int money = 2000;
if (money > 3000) {
    System.out.println("택시");
} else {
    System.out.println("걷기");
}
 // 걷기

3) and, or, not 연산자

// 카드가 있거나 돈이3000원 이상 있으면 택시, 아니면 걷기
int money = 2000;
boolean card = true;
if (money > 3000 || card) {
    System.out.println("택시");
} else {
    System.out.println("걷기");
}

// 택시

4)  contains

- 해당 아이템이 있는지 조사하는 메서드 / 조건문에 많이 활용된다

import java.util.ArrayList;

public class money {
	public static void main(String[] args) {
	ArrayList<String> pocket = new ArrayList<String>();
	pocket.add("paper");
	pocket.add("cellphone");
	pocket.add("money");
	
	if (pocket.contains("money")) {
		System.out.println("택시를 타고 가라");
	} else {
		System.out.println("걸어가라");
	}
	
	}
}

// 택시를 타고 가라

5) else if

- 있다와 없다중에 없을 경우 다시 경우를 나누어주는 조건문에 해당한다

(if, else가 여러번 사용되어 한 번에 이해하기가 쉽지 않고 산만한 느낌이드느데... 이를 보완하기 위해서... 자바는 여러 조건을 판단할 수 있게 하는 else if 문이 있다)

package test;
import java.util.ArrayList;

public class money {
	public static void main(String[] args) {
	boolean hasCard = true;
	ArrayList<String> pocket = new ArrayList<String>();
	pocket.add("paper");
	pocket.add("cellphone");
	
	if (pocket.contains("money")) {
		System.out.println("택시를 타고 가라");
	} else {
		if (hasCard) {
			System.out.println("택시를 타고 가라");
		}else {
			System.out.println("걸어가라");
		}
	}
	
	}
}

// 택시를 타고 가라

아래 else if 부분들을 수정하면 조금 간단하게 나타내면 아래로 나타내질 수 있다 / else if는 개수제한 없이 사용 가능

	if (pocket.contains("money")) {
		System.out.println("택시를 타고 가라");
	}else if (hasCard) {
		System.out.println("택시를 타고 가라");
	}else {
		System.out.println("걸어가라");
	}

2. switch / case 문

: if 문과 비슷하지만 좀 더 일정한 형식이 잇는 조건문..

=> 입력 변수의 값과 일치하는 case 입력값(입력값1, 입력값2,....) 이 있다면 해당 case 문에 속한 문장들이 실행된다...

  break 문 또한 존재(해당 case문을 실행한 뒤 swirch 문을 빠져나가기 위함), break 문이 없다면, 다음 case로 이동

package test;
import java.util.ArrayList;

public class money {
	public static void main(String[] args) {
		int month = 8;
		String monthString = " ";
		switch(month) {
		case 1: monthString = "January";
		break;
		case 2: monthString = "February";
		break;
		case 3: monthString = "March";
		break;
		case 4: monthString = "April";
		break;
		case 5: monthString = "May";
		break;
		case 6: monthString = "June";
		break;
		case 7: monthString = "July";
		break;
		case 8: monthString = "August";
		break;
		case 9: monthString = "September";
		break;
		case 10: monthString = "October";
		break;
		case 11: monthString = "November";
		break;
		case 12: monthString = "December";
		break;
		default: monthString = "Invalid month";
		break;
		}
		System.out.println(monthString);
	}
}

해당하는 숫자에 대한 case가 실행되었다!!

만약 month가 1에서 12사이의 숫자가 아닌 다른 값이 저장되어 있다면 defaul: 문장이 수행된다!

값이 정형화되어 있는 경우 if 문보다는 switch/case 문을 쓰는 것이 코드의 가독성이 좋다!!

3. while 문

: 조건문이 참인 동안 수행할 문장들을 반복해서 수행한다

package test;

public class tree {
	public static void main(String[] args) {
		int treeHit = 0;
		while (treeHit < 10) {
			treeHit++; // treeHit += 1; 로도 표현가능
			System.out.println("나무를 " + treeHit + "번 찍었습니다.");
			if (treeHit == 10) {
				System.out.println("나무 넘어갑니다.");
			}
		}

	}
}

/*
나무를 1번 찍었습니다.
나무를 2번 찍었습니다.
나무를 3번 찍었습니다.
나무를 4번 찍었습니다.
나무를 5번 찍었습니다.
나무를 6번 찍었습니다.
나무를 7번 찍었습니다.
나무를 8번 찍었습니다.
나무를 9번 찍었습니다.
나무를 10번 찍었습니다.
나무 넘어갑니다.
*/

while문의 조건문 : treeHit < 10 (10보다 작은 동안 수행) / +1 커지면서 수행하고 / 10이 되면서 종료.. while 문 빠져나옴

1) 무한 루프

: 무한하게 while 문 내의 문장들을 수행... 빠져나오지 못한다...

package test;

public class loop {
	public static void main(String[] args) {
		while (true) {
			System.out.println("Ctrl-C를 눌러야 while문을 빠져나갈 수 있습니다.");
		}
	}
}

/*
Ctrl-C를 눌러야 while문을 빠져나갈 수 있습니다.
Ctrl-C를 눌러야 while문을 빠져나갈 수 있습니다.
Ctrl-C를 눌러야 while문을 빠져나갈 수 있습니다.
...
*/

[Ctrl] + [c] : 종료

2) while 문 빠져나가기 - break

: while 문을 강제로 멈춰야 할 때 사용한다

package test;

public class loop {
	public static void main(String[] args) {
		int coffee = 10;
		int money = 300;
		
		while (money > 0) {
			System.out.println("돈을 받았으니 커피를 줍니다.");
			coffee--;
			System.out.println("남은 커피의 양은 " + coffee + "입니다.");
			if (coffee == 0) {
				System.out.println("커피가 다 떨어졌습니다. 판매를 중지합니다.");
				break;
			}
		}
	}
}

/*
돈을 받았으니 커피를 줍니다.
남은 커피의 양은 9입니다.
돈을 받았으니 커피를 줍니다.
남은 커피의 양은 8입니다.
돈을 받았으니 커피를 줍니다.
남은 커피의 양은 7입니다.
돈을 받았으니 커피를 줍니다.
남은 커피의 양은 6입니다.
돈을 받았으니 커피를 줍니다.
남은 커피의 양은 5입니다.
돈을 받았으니 커피를 줍니다.
남은 커피의 양은 4입니다.
돈을 받았으니 커피를 줍니다.
남은 커피의 양은 3입니다.
돈을 받았으니 커피를 줍니다.
남은 커피의 양은 2입니다.
돈을 받았으니 커피를 줍니다.
남은 커피의 양은 1입니다.
돈을 받았으니 커피를 줍니다.
남은 커피의 양은 0입니다.
커피가 다 떨어졌습니다. 판매를 중지합니다.
*/

돈이 0보다 클때동안 진행하다... 0이 되어버리면 출력후 break가 호출되어 while 문을 빠져나간다

3) while 문으로 돌아가기 - continue

: while 문 안의 문장을 수행할 때 어떤 조건을 검사해서 참이 아닌 경우 while 문을 빠져나가는 대신 while 문의 맨 처음, 즉 조건문으로 돌아가게 하고 싶은 경우 continue를 사용(빠져나가지 않고 다시 올라가서 진행)

package test;

public class loop {
	public static void main(String[] args) {
		int a = 0;
		while (a < 10) {
			a++;
			if (a % 2 == 0) {
				continue; // 짝수인 경우 조건문으로 돌아간다.
			}
			System.out.println(a); // 홀수만 출력된다
		}
	}
}

/*
1
3
5
7
9
*/

a가 짝수이면 continue문이 실행되어 while 문의 맨 처음으로 돌아가게 한다!! 

그러므로 a가 짝수이면 System.out.println(a)는 수행되지 않기 때문에 홀수만 출력될 것이다!!!!

4. for 문

: 문장을 반복해서 수행해야 할 경우에 사용

1) for 문의 기본 구조

// 기본 구조
for (초깃값; 조건문; 증갓값) {
	...
}

/////
String[] numbers = ["one", "two", "three"]
for (int i = 0; i < numbers.length; i++) :
	System.out.println(numvers[i]);
}
/*
one
two
three
*/

i의 초깃값은 0, 조건문은 i < numbers.length, 증갓값은 i++이 된다!!

=> i 값이 numbers의 개수보다 작은 동안 계속 i 값을 1씩 증가시키며 for 문의 문장들을 수행

2) for 문으로 돌아가기 - continue

: while 문과 마찬가지로 적용!

int[] marks = {90, 25, 67, 45, 80};
for (int i = 0; i < marks.length; i++) {
	if (marks[i] < 60) {
    	continue; // 조건문으로 돌아간다.
    }
    System.out.println((i+1)+"번 학생 축하합니다. 합격입니다.");
}

/*
1번 학생 축하합니다. 합격입니다.
3번 학생 축하합니다. 합격입니다.
5번 학생 축하합니다. 합격입니다.
*/

점수가 60점 미만이면 continue문이 실해되어 축하메시지를 출력하는 부분이 수행하지 않고, 

for 문의 첫부분으로 돌아갑니다!!!

=> 반복문을 수행할 때, 특정 조건에서는 수행하지 않고 건너뛰어야 할 때 사용합니다!!!!

3) 이중 for 문

: for 문을 두번 사용한 것..

// 구구단 만들기
package test;

public class gugudan {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for (int i=2; i < 10; i++) {
			for (int j=1; j <10; j++) {
				System.out.print(i*j+" ");
			}
			System.out.println(""); // 줄을 바꾸어 출력하는 역할을 한다
		}
	}
}

/*
2 4 6 8 10 12 14 16 18 
3 6 9 12 15 18 21 24 27 
4 8 12 16 20 24 28 32 36 
5 10 15 20 25 30 35 40 45 
6 12 18 24 30 36 42 48 54 
7 14 21 28 35 42 49 56 63 
8 16 24 32 40 48 56 64 72 
9 18 27 36 45 54 63 72 81 
*/

단이 바뀔때 println을 사용하여 줄바꿈하여 문자를 출력하였다!!

5. for each 문

: 이전에 배웠던 for문을 활용한 예제(첨봄)

// for each 문의 구조
for (type 변수명: iterate) {
	body-of-loop
}

iterate는 루프를 돌릴 객체이고 iterate 객체에서 한 개씩 순차적으로 변수명에 대입되어 for 문이 수행된다...

iterate에 사용할 수 있는 자료형은 루프를 돌릴 수 있는 자료형(배열이나 ArrayList등)만 가능하다...

+ 변수명의 type(자료형)은 iterate 객체에 포함된 자료형과 일치해야한다!!!

String[] numbers = {"one", "two", "three"};
for(int i = 0; i < numbers.lengh; i++) {
	System.out.println(numbers[i]);
}

// for each 문을 사용한다면...
String[] numbers = {"one", "two", "three"};
for(String number: numbers) {
	System.out.println(number);
}

문제...

1. everywhere

2. i % 3 == 0

3. i >5 / int j=0; j <5; j++;

4. int i = 1; i < 101; i++;

5. int mark: marks / total / marks.length;

문제 😵‍💫

수빈이는 동생과 숨바꼭질을 하고있다. 수빈이는 현재 점N에 있고 동생은 점 K에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다, 순간이동을 하는 경우에는 1초 후에 2 * X의 위치로 이동하게 된다

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력!

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력!

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.4

내 풀🦷

# 1697. 숨바꼭질
from collections import deque
def bfs(start, depth):
    visited = [0] * 100001
    q = deque()
    q.append((start, depth))
    visited[start] = 1
    while q:
        s, d = q.popleft()

        if s == K:
            return d

        for nxt_s in [s-1, s+1, s*2]:
            if 0 <= nxt_s <= 100000 and (not visited[nxt_s] or visited[nxt_s] > d+1):
                q.append((nxt_s, d+1))
                visited[nxt_s] = d+1

N, K = map(int, input().split())
visited = [0] * K
result = dfs(N, 0)
print(result)

 처음에 도대체가 어떻게 접근해야할지도 모르겠고 dp나 while문으로 풀어야겠다 싶었는데 알고보니 bfs 문제였다ㅜㅜ

시작점과 깊이를 넣어서 시작점이 끝점과 같아지면 return으로 깊이를 받아주면 최소값을 구할 수 있다!!

어려웠던 부분은 방문 했던 곳 또는 깊이가 더 깊은곳과 그전까지의 깊이에 해당하는 값이 같았을때는 배제해 주어야 한다는 것이었다... 다른 분들 코드를 보았을때는 이미 방문한곳을 continue로 넘겨서 간단히 해결해 주는것을 볼 수 있었다...어떻게 풀어야할지까지 고민한 문제는 오랜만이라 더욱 힘들었다 😂😂😂😂

유튜버 딩코딩씨 보고 정리해보는 순열과 조합...

재귀, 백트래킹, dfs... 등등 정말 많이 연관되어있어서 정리하면 좋을것 같아 올려봅니다...

##### permutation(순열)

'''
순열 : permutation(포함되어 있는 수가 같은 수여도 순서가 다르면 다른걸로 친다)
dfs 트리와 체크리스트 사용

3개의 공 중에 2개를 뽑는 경우(3P2)
사용한 경우 넣으면 안되므로 체크리스트 사용하는 것임....
깊이 + 1 한후 길이에 맞는 값을 리턴을 하고나면
다시 체크리스트에 빼줘서 다시 넣을 수 있도록 해준다..

1 2
1 3
2 1
2 3
3 1
3 2
6가지
'''

def dfs(L):
    # 종료 조건
    # 리스트의 길이가 찾아야 할 개수(r)가 된다면 종료
    if L == r:
        print(result)
    else:
        for i in range(len(n)):
            # 체크리스트에 해당하는 값이 없다면
            if checklist[i] == 0:
                # result 리스트에 값을 추가
                result[L] = n[i]
                # 체크리스트에 값이 생겼다고 표시해주기
                checklist[i] = 1
                # 다음 깊이로 이동
                dfs(L+1)
                # 다음 번에 다시 사용하기 위해서 빼준다고 그냥 생각하셈 ^^;;;
                checklist[i] = 0

n = [1, 2, 3]
r = 2
result = [0] * r
checklist = [0] * len(n)
dfs(0)

이해도 이해지만 어느정도 외울만큼은 외우라고 하심...

이해해야 외우지 싶다가도 이러다가 진도가 영 안나갈거 같아서 적당히 이해시켜서 외우는것이 좋을 듯...

'''
조합 : 같은 숫자가 포함되어 있으면 같은 걸로 인정....
순열보다 경우의 수가 훨씬 작음...
순열보다 더 간단...
한번 썼으면 다시 쓰지를 않으니까 체크리스트도 필요없음...
DFS 트리를 이용해서 푼다

3C2

1 2
1 3
2 3

3가지
'''
def dfs(L, BeginWith):
    # 종료 조건
    if L == r:
        print(*result)
    else:
        for i in range(BeginWith, len(n)): # 시작하는 값부터 끝까지
            result[L] = n[i] # 해당하는 값을 넣어주기
            dfs(L+1, i+1) # 다음 깉이 다음 숫자로 이동하여 전 값을 들어오지 못하도록


n = [1, 2, 3]
r = 2
result = [0] * r

dfs(0, 0) # level, begin(어디서 시작할지)