알고리즘 {먼데이} 챌린지 시즌1
    • 01
      난이도 맛보기
    • [예시] [문제] 1. 단어장 만들기
      [예시] [해설] 1. 단어장 만들기
      [예시] [문제] 2. 카드 교환하기
      [예시] [해설] 2. 카드 교환하기
    • 02
      1주차 챌린지 수학과 구현
    • [1주차] [문제] 1. 경로의 개수
      [1주차] [해설] 1. 경로의 개수
      [1주차] [문제] 2. 동명이인
      [1주차] [해설] 2. 동명이인
      [1주차] [문제] 3. 최장 맨해튼 거리
      [1주차] [해설] 3. 최장 맨해튼 거리
      [1주차] [문제] 4. 소수 찾기
      [1주차] [해설] 4. 소수 찾기
    • 03
      2주차 챌린지 구현과 문자열
    • [2주차] [문제] 1. 합격자 찾기
      [2주차] [해설] 1. 합격자 찾기
      [2주차] [문제] 2. 문자열 나누기
      [2주차] [해설] 2. 문자열 나누기
      [2주차] [문제] 3. 출석부
      [2주차] [해설] 3. 출석부
      [2주차] [문제] 4. 폭탄 구현하기
      [2주차] [해설] 4. 폭탄 구현하기
    • 04
      3주차 챌린지 그래프 이론
    • [3주차] [문제] 1. 0커플
      [3주차] [해설] 1. 0커플
      [3주차] [문제] 2. 폴더 폰 자판
      [3주차] [해설] 2. 폴더 폰 자판
      [3주차] [문제] 3. 구름이의 여행
      [3주차] [해설] 3. 구름이의 여행
      [3주차] [문제] 4. 순환하는 수로
      [3주차] [해설] 4. 순환하는 수로
    • 05
      4주차 챌린지 동적프로그래밍
    • [4주차] [문제] 1. 체크 카드
      [4주차] [해설] 1. 체크 카드
      [4주차] [문제] 2. 단풍나무
      [4주차] [해설] 2. 단풍나무
      [4주차] [문제] 3. 거리두기
      [4주차] [해설] 3. 거리두기
      [4주차] [문제] 4. 주차 구역 나누기
      [4주차] [해설] 4. 주차 구역 나누기
    • 06
      5주차 챌린지 기출 변형 문제
    • [5주차] [문제] 1. 개미와 진딧물
      [5주차] [해설] 1. 개미와 진딧물
      [5주차] [문제] 2. 모래섬
      [5주차] [해설] 2. 모래섬
      [5주차] [문제] 3. 수 이어 붙이기
      [5주차] [해설] 3. 수 이어 붙이기
      [5주차] [문제] 4. 구슬 게임
      [5주차] [해설] 4. 구슬 게임
    • 07
      6주차 챌린지 기출 변형 문제
    • [6주차] [문제] 1. 7게임
      [6주차] [해설] 1. 7게임
      [6주차] [문제] 2. 제곱암호
      [6주차] [해설] 2. 제곱암호
      [6주차] [문제] 3. 비밀 편지
      [6주차] [해설] 3. 비밀 편지
      [6주차] [문제] 4. 경쟁 배타의 원리
      [6주차] [해설] 4. 경쟁 배타의 원리
    • 08
      7주차 챌린지 실전 모의고사
    • [7주차] [문제] 1. UXUI 디자이너
      [7주차] [해설] 1. UXUI 디자이너
      [7주차] [문제] 2. 퍼져나가는 소문
      [7주차] [해설] 2. 퍼져나가는 소문
      [7주차] [문제] 3. 구름이의 여행 2
      [7주차] [해설] 3. 구름이의 여행 2
      [7주차] [문제] 4. 이상한 미로
      [7주차] [해설] 4. 이상한 미로
    • 09
      8주차 챌린지 실전 모의고사
    • [8주차] [문제] 1. 구름 숫자
      [8주차] [해설] 1. 구름 숫자
      [8주차] [문제] 2. 뒤통수가 따가워
      [8주차] [해설] 2. 뒤통수가 따가워
      [8주차] [문제] 3. 직사각형 만들기
      [8주차] [해설] 3. 직사각형 만들기
      [8주차] [문제] 4. 구름나라 청소하기
      [8주차] [해설] 4. 구름나라 청소하기
    [예시] [해설] 1. 단어장 만들기
    01 난이도 맛보기
    [예시] [해설] 1. 단어장 만들기

    알고리즘 (출제자 Benjamin)


    • 정렬
    • 문자열


    문제 해설


    알고리즘 문제를 해결하기 위해서 문제를 풀 때 무작정 문제를 읽고 코딩을 시작하는 것보다는, 무엇을 고려해서 문제를 해결해야 하는지를 먼저 파악하는 연습이 필요합니다. 이 문제의 요구 사항을 정리해보면 아래와 같습니다.

    • 단어들을 문제에서 주어진 기준에 따라서 정렬하기
    • 앞에서 번째에 위치한 단어를 찾기

    이렇게 항상 무엇을 해야 하는지를 먼저 파악한 다음, 어떻게 구현을 할 수 있을지를 고민해보는 것이 효율적으로 문제를 해결하는 데 많은 도움이 될 것입니다.


    여러 기준에 따라 정렬하기


    문제에서 요구하는 정렬의 기준이 다소 복잡합니다. 단어들을 길이 순으로 정렬한 뒤, 다시 사전 순으로 정렬을 하라고 합니다. 이렇게 여러 기준을 한 번에 고려해서 정렬을 하려면 어떻게 해야 할까요?  

    여기서 소개드릴 방식은 기본적으로 여러 개의 원소가 있는 배열을 정렬하는 방식을 활용하는 것입니다. 배열 단위로 정렬을 할 때는 우선 가장 앞에 있는 원소를 기준으로 오름차순으로 정렬한 뒤, 같은 원소가 있다면 그 다음 원소를 기준으로 정렬을 하는 방식을 사용합니다. 이전 조건(첫 번째 원소를 기준)을 만족하지 못하는 경우에만 다음 조건(그 다음 원소 기준)을 이용해서 정렬을 한다는 점에서, 문제의 정렬 방식을 적용해볼 수 있을 것 같습니다. 아래 코드와 같이 [단어의 길이, 단어] 의 배열을 만들어서 정렬을 해줄 수 있습니다.

    py3

    파이썬의 lambda 함수를 이용하면 조금 더 간결한 코드를 짤 수도 있습니다.

    py3

    위의 기준에 따라 정렬을 잘 했다면, 이제 앞에서 번째에 위치한 단어를 출력하는 것은 단순히 정렬된 문자열에서 번째 인덱스에 위치한 값을 출력하는 것만으로 가능합니다.

    단어의 최대 길이를 라고 했을 때, 총  시간에 문제를 해결할 수 있습니다. 이 100만으로 크므로,  시간에 동작하는 정렬을 사용해야 시간 안에 통과할 수 있다는 점을 유의합시다.


    코드(Python/C++)


    py3
    cpp
    js
    질문하기