5회차 - 알고리즘 기록 : 세 카드

2022. 7. 2. 18:59·TEAM STUDY/알고리즘 코딩 테스트 스터디
728x90
반응형
문제3I-세 카드

본 문제는 앞 문제를 조금 변형하면 해결 할 수 있는 숙제 입니다.

선택해야 할 카드가 세 장일 때에도 앞의 문제와 같은 방법을 적용할 수 있을까 고민해보세요.

힌트> 문제의 입력 사이즈가 작아졌다!

실습 내용

 지수가 살고 있는 이상한 나라에서는 독특한 복권제도가 존재한다. 이상한 나라에서는 매 주 당첨 될 자연수 번호를 정해두며, 복권을 구매한 사람은 그 자리에서 수 많은 카드들 중 하나를 뽑을 수 있는 기회가 세 번 주어진다. 즉, 똑같은 카드를 세 번 뽑을 수 도 있다. 이렇게 세 번에 걸쳐 뽑은 카드들에 적혀있는 세 자연수를 더하여 당첨 번호로 지정된 자연수와 일치한다면 그 사람은 당첨되는 것이다.

 복권 담당자인 미주는 이번 주에 복권에 사용 될 당첨 번호들을 정하려고 한다. 하지만 매 번 실제로 그 당첨번호가 세 카드에 적힌 숫자들의 합으로 만들어 질 수 있는지 (즉, 실제로 당첨될 수 있는 번호인지) 검사하는 과정이 너무 번거로워 고민을 하고 있다. 미주를 도와서 주어진 카드를 조합해 당첨 번호들을 만들 수 있는지 판단하는 프로그램을 작성해주자.

 

 

입력 형식

 첫 줄에는 사용할 카드의 수 N과 당첨 번호의 숫자 M이 공백으로 구분되어 주어진다. N은 1이상 1,000이하의 자연수이며 M은 1이상 100이하의 자연수이다.

두 번째 줄에는 N개의 카드에 적힌 숫자들이 공백으로 구분되어 1이상 1억 이하의 자연수로 주어진다. 

세 번째 줄에는 M개의 이번 주에 사용 될 당첨번호들이 공백으로 구분되어 주어진다. 당첨번호들은 모두 서로다른 1이상 3억 이하의 자연수이다. 

 

출력 형식

 M개의 당첨번호 들 중 실제로 세 카드에 적힌 숫자의 합으로 표현될 수 있는 당첨번호들을 모두 출력한다.

  • 실제로 만들 수 있는 당첨번호가 여러개라면, 오름차순으로 정렬하고 각 숫자는 공백으로 구분하여 한 줄에 출력한다.
  • 실제로 만들 수 있는 당첨번호가 존재하지 않는다면 NO를 출력한다.

 

결과 코드

package 알고리즘;
import java.io.*;
import java.lang.*;
import java.util.*;


public class 세카드 {
	public static final Scanner scanner = new Scanner(System.in);

	/**
	 * 중복을 포함해 세 카드의 합으로 만들 수 있는 당첨번호들의 리스트를 반환하는 함수
	 * @param n     카드의 수
	 * @param m     검사하려는 당첨번호의 수
	 * @param cards   각 카드에 적힌 숫자들
	 * @param target  검사하려는 각 당첨번호 리스트
	 * @return      세 카드의 합으로 표현될 수 있는 당첨번호들의 오름차순 리스트
	 */
	public static ArrayList<Integer> getPossibleTargets(int n, int m, int[] cards, int[] target)
	{
		ArrayList<Integer> possibleTargets = new ArrayList<>(); //만들 수 있는 당첨번호들

		Arrays.sort(cards);
		
		for(int k : target)
		{ //검사 할 모든 당첨 번호 k에 대하여

			boolean possible = false; // k를 세 숫자의 합으로 표현할 수 있는지 여부
			for(int i = 0 ; i < n ; i+= 1)
			{   // 카드 중 하나 x를 선택한다.
				int x = cards[i];
				for(int j = 0 ; j <= i ; j += 1)
				{   // 카드 중 하나 y를 선택한다
					int y = cards[j];
					int z = k - (x + y); // k = (x +  y )+ z 가 되는 z를 계산한다
					
					// z가 cards[]에 존재한다면?
					if( Arrays.binarySearch(cards, z) >= 0 ) {
						// k = x + y + z 가 가능한 <x, y, z>가 존재한다.
						possible = true;
						break;
					}
				}
				if(possible)
				{   // 이미 찾았다면 탈출한다
					break;
				}
			}
			if(possible)
			{	// 세 카드의 합으로 k를 만들 수 있다면, 추가한다.
				possibleTargets.add(k);
			}
		}

		Collections.sort(possibleTargets);
		return possibleTargets;
	}

	public static void main(String[] args) throws Exception {
		int n = scanner.nextInt();  // 카드의 수
		int m = scanner.nextInt();  // 검사 할 후보 당첨번호의 수

		int[] cards = new int[n];
		int[] targets = new int[m];

		// 각 카드 정보를 입력받는다
		for(int i = 0 ; i < n ; i ++)
		{
			cards[i] = scanner.nextInt();
		}

		// 각 당첨번호를 입력받는다
		for(int i = 0 ; i < m ; i ++)
		{
			targets[i] = scanner.nextInt();
		}

		ArrayList<Integer> answers = getPossibleTargets(n, m, cards, targets);

		if(answers.size() == 0)
		{
			System.out.print("NO");
		}else{
			for(int i = 0 ; i < answers.size() ; i++)
			{
				if( i > 0 )
				{
					System.out.print(" ");
				}
				System.out.print(answers.get(i));
			}
		}
	}
}
728x90
반응형
저작자표시 (새창열림)

'TEAM STUDY > 알고리즘 코딩 테스트 스터디' 카테고리의 다른 글

6회차 - 알고리즘 기록 : 과유불급 (어려웠던거 다시!)  (0) 2022.07.11
6회차 - 알고리즘 기록 : 네 카드 (어려웠던거 다시!)  (0) 2022.07.09
5회차 - 알고리즘 기록 : 네 카드  (0) 2022.06.13
5회차 - 알고리즘 기록 : 두 카드  (0) 2022.06.13
5회차 - 알고리즘 기록 : 팬미팅  (0) 2022.06.13
'TEAM STUDY/알고리즘 코딩 테스트 스터디' 카테고리의 다른 글
  • 6회차 - 알고리즘 기록 : 과유불급 (어려웠던거 다시!)
  • 6회차 - 알고리즘 기록 : 네 카드 (어려웠던거 다시!)
  • 5회차 - 알고리즘 기록 : 네 카드
  • 5회차 - 알고리즘 기록 : 두 카드
Binsoo
Binsoo
내 트러블 슈팅
  • Binsoo
    정수빈 기술블로그임.
    Binsoo
  • 전체
    오늘
    어제
    • 빈수 개발자 개발 일기 (932)
      • 개발중 (634)
        • Spring Boot (95)
        • Spring Security (2)
        • Spring Batch (6)
        • Spring Boot & Redis (13)
        • Java Persistence API (JPA) (28)
        • Web (42)
        • Rest Api (7)
        • Spring Concurrency Control (3)
        • Redis (8)
        • Kubernetes (k8s) (4)
        • MYSQL (35)
        • AirFlow (15)
        • Docker (2)
        • Git (22)
        • Linux (9)
        • JSON Web Tokens (JWT) (4)
        • Troubleshooting (87)
        • Swagger (0)
        • Vue.js (52)
        • Java (74)
        • html (12)
        • C (5)
        • jQuery (15)
        • JavaServer Pages (JSP) (17)
        • Arduino (1)
        • JavaScript (35)
        • Amazon Web Services (AWS) (11)
        • Algorithm (9)
        • 참고 기능 (18)
        • mongo (2)
      • PROJECT (27)
        • 스프링부트+JPA+몽고 API 개발 (3)
        • MINI (2)
        • 게시판 (3)
        • vue 프로젝트 (1)
        • JPA 사이드 프로젝트 기록 (17)
      • TEAM STUDY (156)
        • 가상 면접 사례로 배우는 대규모 시스템 설계 기초 (8)
        • 한 권으로 읽는 컴퓨터 구조와 프로그래밍 (12)
        • NAVER DEVELOPER (4)
        • LINUX (23)
        • PYTHON (19)
        • SERVER (8)
        • 알고리즘 코딩 테스트 스터디 (31)
        • 쿠버네티스 (40)
        • 대세는 쿠버네티스 [초급~중급] (11)
      • BOOK (0)
      • 자격증 (61)
        • 리눅스 1급 - 필기 기록 (19)
        • 네트워크 관리사 (2)
        • 네트워크 관리사 2급 - 실기 기록 (21)
        • 네트워크 관리사 2급 - 필기 기록 (16)
        • 정보처리 (2)
      • 직장인 대학원 (17)
        • 기록 (1)
        • 캐글 스터디 (3)
        • R (12)
  • 블로그 메뉴

    • 홈
    • 태그
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    VUE
    네트워크 관리사 2급
    리눅스 마스터 1급 요약
    네트워크 관리사 자격증
    redis
    파이썬 알고리즘
    알고리즘
    git
    Spring
    쿠버네티스
    네트워크 관리사
    BackendDevelopment
    리눅스 마스터
    네트워크 관리사 학점
    스프링
    네트워크 관리사 실기
    파이썬
    리눅스 1급 요약
    jpa
    REST API
    java
    네트워크 관리사 요약
    쿠버네티스 스터디
    docker
    리눅스 마스터 1급 정리
    리눅스 마스터 1급
    springboot
    리눅스 마스터 요약
    Git 저장소
    네트워크 관리사 2급 실기
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.4
Binsoo
5회차 - 알고리즘 기록 : 세 카드

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.