다메카솔

https://programmers.co.kr/learn/courses/30/lessons/12901

 

코딩테스트 연습 - 2016년

2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까

programmers.co.kr

문제

2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT

입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요.

제한 조건

• 2016년은 윤년입니다.
• 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다)

 

발상

윤년과 그 해의 요일이 모두 주어진 문제이다.

달력 문제는 윤년계산을 포함하여 수십, 수백년 후까지 계산하는 문제가 나오기도 하는데 경시대회가 아니면 수학적이고 다소 지엽적인 문제는 코딩테스트에서 출제되지 않을거라 생각하고 간단히 그 해의 월별 날짜와 요일 배열을 만들어 경과된 일수를 더해서 구하기로 하였다.

 

의사코드

1. 초기값 세팅(월별 날짜, 반환할 요일 배열)
2. 주어진 날짜를 바탕으로 2016/1/1부터 경과된 일수 계산
3. 7로 나누어 요일 비교
4. 요일값 반환

 

개선

다른사람들이 제출한 답을 보니 캘린더 함수를 사용하는 것도 있었는데, 국가별로 날짜가 다르기 때문에 국가코드도 설정하고 하는 부분이 다소 지엽적이라고 생각하였다.

 

https://programmers.co.kr/learn/courses/30/lessons/42840

문제

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

발상

문제 카테고리가 완전탐색인만큼 모든 경우의 수를 다 검색하면서 조건을 따지는 문제였다.

3명의 수포자가 같은 문제를 가지고 각각의 방식으로 문제를 푼다는 점에서 디자인패턴 전략패턴을 사용하면 확장성이 높고 깔끔한 코드가 나올 것 같았지만, 타임아웃이 걸릴 것 같아서 우선 반복문으로 풀어보고 다음에 리팩토링 해보기로 하였다.

의사코드

1. 초기값 세팅(각 수포자의 전략 템플릿)

2. 정답 확인(){

    1. a 정답 확인

    2. b 정답 확인

    3. c 정답 확인
}

3. 최고점 확인(스트림)
4. 최고점을 맞은 수포자 리스트 추출
5. 배열로 변환

개선

의사코드를 작성하고, 구현하고 제출하였더니 런타임에러가 발생하였다.

수포자들의 전략템플릿을 구현할 때 따로 메서드를 추출하여서 각각의 전략템플릿의 길이를 넘어가면 초기화하는 식으로 하였는데, 그 부분을 따로 계산하지 않고 나머지값과 전략템플릿 배열인덱스를 매칭하는 방법으로 리팩토링 하니 통과하였다.

단순히 전략패턴 업데이트만 함수로 재사용했는데도 런타임에러가 발생한 것을 보면, 추가적으로 리팩토링해서 전략 디자인패턴을 구현하면 더 호출이 복잡해지니 테스트케이스는 통과하지 못할 것 같다.

https://leetcode.com/problems/sliding-puzzle/

문제

2 x 3 보드에는 1에서 5까지 레이블이 지정된 5개의 타일과 0으로 표시되는 빈 사각형이 있습니다. 이동은 0과 4방향으로 인접한 숫자를 선택하고 교체하는 것으로 구성됩니다. 보드의 상태는 보드가 [[1,2,3],[4,5,0]]인 경우에만 해결됩니다. 퍼즐 보드 보드가 주어지면 보드의 상태가 해결되도록 필요한 최소 이동 횟수를 반환합니다. 보드의 상태를 해결할 수 없는 경우 -1을 반환합니다.

접근

어렸을때 가지고 놀던 슬라이딩퍼즐을 맞추는 가장 적은 횟수를 구하는 문제이다.

퍼즐의 풀이방법을 구현하여서 푸는 방법도 있을 것 같고https://namu.wiki/w/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9%20%ED%8D%BC%EC%A6%90

빈 공간을 기준으로 이동알고리즘을 작성하는 방법도 있을 것 같았는데, 절차가 잘 떠오르지 않았다.

퍼즐의 배열 상태를 하나의 노드로 보고,

빈공간(0)의 이동 가능 경로의 이동 후 배열상태를 자식노드로 연결하여

전체 경우의 수를 탐색하는 방법을 쓰는 것을 방향으로 잡고 접근하였다.

구현에 사용한 변수는 다음과 같다.

목표 퍼즐상태 String = "123450"

현재 상태 String

방문노드 캐시용 HashSet<String>

탐색노드 저장용 Queue

퍼즐의 위치 별 탐색 가능 방향 배열 int[][]

의사코드

1. 초기값 세팅

2. 탐색용 배열과 캐시에 현재상태 세팅

3. 노드 탐색(큐가 빌 때까지){

    1. 탈출조건 체크 ( 탐색깊이 반환 )

    2. 현재 0의 위치 확인

    3. 가능한 이동방향 퍼즐상태 저장(0 <-> 목표 스왑)

        1. 캐시확인, 방문노드면 큐에 저장X

        2. 미방문 노드면 큐에 저장

    4. 탐색깊이 ++

}

4. 탐색 실패 시 -1 반환