[백준/Python] 6443번 애너그램

2023. 1. 6. 21:56· Koala - 9기/코딩테스트 준비 스터디
목차
  1. 문제
  2. 입력
  3. 출력
  4. 코드
  5.  
  6. 문제풀이

https://www.acmicpc.net/problem/6443

 

6443번: 애너그램

첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주

www.acmicpc.net


문제

씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다.

애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다.

입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다.  또한 출력할 때에 알파벳 순서로 출력해야 한다.

 

입력

첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주어진다.

 

출력

N개의 영단어에 대한 모든 가능한 애너그램을 출력한다. 각각의 영단어에 대한 애너그램을 출력할 때, 알파벳 순서로 중복되지 않게 출력한다.

 

코드

import sys
ssr = sys.stdin.readline


def backT(word, idx):
    if len(word) == len(words[idx]):
        print(''.join(word))
        return

    for k in wordD[idx]:
        if wordD[idx][k]:
            word.append(k)
            wordD[idx][k] -= 1

            backT(word, idx)

            word.pop()
            wordD[idx][k] += 1


N = int(ssr())
wordD = []
words = []

for i in range(N):
    inWord = sorted(ssr().strip())
    words.append(inWord)
    visited = {}

    for j in inWord:
        if j in visited:
            visited[j] += 1
        else:
            visited[j] = 1

    wordD.append(visited)


for i in range(N):
    backT([], i)

 

 

문제풀이

1. 입력한 영단어에 대한 "모든" 가능한 단어를 출력해야 하기 때문에 백트래킹을 이용한다.

2. "abc"를 입력 시 "aaa"와 같은 중복 사용 방지를 위해 사용된 알파벳이 재사용됐는지 확인해야 한다. (일명 visited를 사용한다.)

3. visited는 딕셔너리로 구현. key 값은 알파벳, value 값은 알파벳의 사용 가능한 횟수로 구현.

막혔던 부분

최초에 visited를 구현할 때 2중 배열을 이용하여 [사용 -> True, 미사용 -> False]로 구현하였고, 중복 방지를 위해 단어들을 리스트에 넣어 [not in]을 이용하여 체크하였다. 하지만 위와 같이 구현하니 [시간 초과] 혹은 [메모리 초과]가 발생하였다.때문에 위 코드와 같이 visited를 딕셔너리로 구현하여 key를 알파벳으로, value를 사용 가능한 횟수로 설정하여 해결하였다.

 

 

저작자표시 (새창열림)

'Koala - 9기 > 코딩테스트 준비 스터디' 카테고리의 다른 글

[백준/python] 6603번 로또  (0) 2023.01.07
[백준/JAVA]14501번 퇴사  (0) 2023.01.06
[백준/Python3] 17626번 Four Squares  (0) 2023.01.06
[백준/Python] 9207번 페그 솔리테어  (0) 2023.01.03
[백준/Java] 2468번 안전영역  (1) 2023.01.03
  1. 문제
  2. 입력
  3. 출력
  4. 코드
  5.  
  6. 문제풀이
'Koala - 9기/코딩테스트 준비 스터디' 카테고리의 다른 글
  • [백준/python] 6603번 로또
  • [백준/JAVA]14501번 퇴사
  • [백준/Python3] 17626번 Four Squares
  • [백준/Python] 9207번 페그 솔리테어
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1884)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (38)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (31)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • 백준
  • BOJ
  • dfs
  • C++
  • 파이썬
  • 백트래킹
  • dp
  • BFS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
[백준/Python] 6443번 애너그램
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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